A low-memory algorithm for finding short product representations in finite groups
A low-memory algorithm for finding short product representations in finite groups
We describe a space-efficient algorithm for solving a generalization of the subset sum problem in a finite group G, using a Pollard-rho approach. Given an element z and a sequence of elements S, our algorithm attempts to find a subsequence of S whose product in G is equal to z. …