A low-memory algorithm for finding short product representations in finite groups. (Q664395): Difference between revisions

A sequence \(S\) of elements of a group \(G\) of \(n\) elements is said to represent \(G\) if every element of \(G\) can be written as a product of a subsequence of \(S\). The authors describe an algorithm to find such a subsequence. This algorithm is based on Pollard's \(\rho\)-method. It is shown that if \(S\) is a random sequence of length \(d\log_2n\) with \(d>4\), then the expected number of group operations used by the algorithm does not exceed \(B(d)\sqrt n\log n\), storing only \(O(1)\) group elements. If one allows the storage of \(O(n^\varepsilon)\) elements, then the number of expected group operation reduces to \(O(\sqrt d)\), the implied constant depending on \(d\) and \(\varepsilon>0\). It is shown that this algorithm can be applied to the study of class-groups in imaginary quadratic fields as well as to the question of finding isogenies between elliptic curves defined over a finite field.