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

DOI10.1007/s10623-011-9527-8zbMath1246.20031arXiv1101.0564OpenAlexW2067109366MaRDI QIDQ664395

Andrew V. Sutherland, Gaetan Bisson

Publication date: 1 March 2012

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1101.0564

zbMATH Keywords

finite groupsisogenies of elliptic curvesrandom sequencesgeneralization of subset sum problemPollard \(\rho\)-methodproducts of subsequencesshort product representations

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Arithmetic and combinatorial problems involving abstract finite groups (20D60) Finite fields and commutative rings (number-theoretic aspects) (11T99) Curves over finite and local fields (11G20) Class numbers, class groups, discriminants (11R29) Special sequences and polynomials (11B83) Software, source code, etc. for problems pertaining to group theory (20-04)

Related Items (3)

Improved Information Set Decoding for Code-Based Cryptosystems with Constrained Memory ⋮ Improved algorithm for the isogeny problem for ordinary elliptic curves ⋮ Computational problems in supersingular elliptic curve isogenies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Expander graphs based on GRH with an application to elliptic curve cryptography
• Ordered sums of group elements
• Parallel collision search with cryptanalytic applications
• Counting points on elliptic curves over finite fields
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Probabilistic methods in group theory
• Efficient cryptographic schemes provably as secure as subset sum
• Computing endomorphism rings of elliptic curves under the GRH
• Explicit Bounds for Primality Testing and Related Problems
• A Rigorous Subexponential Algorithm For Computation of Class Groups
• New Generic Algorithms for Hard Knapsacks
• An improved Monte Carlo factorization algorithm
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A monte carlo method for factorization
• A space efficient algorithm for group structure computation
• Constructing Isogenies between Elliptic Curves Over Finite Fields
• Über die Classenzahl quadratischer Zahlkörper
• On Periods of Pseudo-Random Sequences
• Constructing elliptic curve isogenies in quantum subexponential time

This page was built for publication: A low-memory algorithm for finding short product representations in finite groups.