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

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2067109366 / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: 1101.0564 / rank
 
Normal rank
Property / cites work
 
Property / cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators / rank
 
Normal rank
Property / cites work
 
Property / cites work: Explicit Bounds for Primality Testing and Related Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing endomorphism rings of elliptic curves under the GRH / rank
 
Normal rank
Property / cites work
 
Property / cites work: Computing the endomorphism ring of an ordinary elliptic curve over a finite field / rank
 
Normal rank
Property / cites work
 
Property / cites work: An improved Monte Carlo factorization algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing elliptic curve isogenies in quantum subexponential time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Probabilistic methods in group theory / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing Isogenies between Elliptic Curves Over Finite Fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4737234 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Rigorous Subexponential Algorithm For Computation of Class Groups / rank
 
Normal rank
Property / cites work
 
Property / cites work: New Generic Algorithms for Hard Knapsacks / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient cryptographic schemes provably as secure as subset sum / rank
 
Normal rank
Property / cites work
 
Property / cites work: Expander graphs based on GRH with an application to elliptic curve cryptography / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4349924 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4681162 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A monte carlo method for factorization / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4237380 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Counting points on elliptic curves over finite fields / rank
 
Normal rank
Property / cites work
 
Property / cites work: A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Über die Classenzahl quadratischer Zahlkörper / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Periods of Pseudo-Random Sequences / rank
 
Normal rank
Property / cites work
 
Property / cites work: A space efficient algorithm for group structure computation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallel collision search with cryptanalytic applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Ordered sums of group elements / rank
 
Normal rank

Revision as of 22:27, 4 July 2024

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
    0 references
    0 references
    0 references
    0 references

    Identifiers

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