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

From MaRDI portal
Revision as of 00:55, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
A low-memory algorithm for finding short product representations in finite groups.
scientific article

    Statements

    A low-memory algorithm for finding short product representations in finite groups. (English)
    0 references
    0 references
    0 references
    1 March 2012
    0 references
    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.
    0 references
    short product representations
    0 references
    finite groups
    0 references
    generalization of subset sum problem
    0 references
    Pollard \(\rho\)-method
    0 references
    isogenies of elliptic curves
    0 references
    random sequences
    0 references
    products of subsequences
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references