A Rigorous Time Bound for Factoring Integers

DOI10.2307/2152702zbMath0770.11057OpenAlexW4247496269MaRDI QIDQ4019632

Hendrik W. jun. Lenstra, Carl B. Pomerance

Publication date: 16 January 1993

Full work available at URL: https://hdl.handle.net/1887/2148

zbMATH Keywords

probabilistic algorithmsmooth numbersnumber field sievefactoring algorithmsclass groups of binary quadratic formsrandom class groups method

Mathematics Subject Classification ID

Distribution of prime ideals (11R44) Distribution of integers with specified multiplicative constraints (11N25) Factorization (11Y05)

Related Items

Computation of lattice isomorphisms and the integral matrix similarity problem ⋮ Finding elliptic curves with a subgroup of prescribed size ⋮ On the distribution of balanced subgroups ⋮ Evaluating Igusa functions ⋮ Dirichlet’s proof of the three-square theorem: An algorithmic perspective ⋮ Algorithms in Algebraic Number Theory ⋮ -adic images of Galois for elliptic curves over (and an appendix with John Voight) ⋮ Efficient reductions and algorithms for subset product ⋮ Computing the endomorphism ring of an ordinary elliptic curve over a finite field ⋮ Explicit methods in number theory. Abstracts from the workshop held July 18--24, 2021 (hybrid meeting) ⋮ Torsion points on CM elliptic curves over real number fields ⋮ Modular polynomials via isogeny volcanoes ⋮ The Factorization of the Ninth Fermat Number ⋮ Rigorous analysis of a randomised number field sieve ⋮ Finding the group structure of elliptic curves over finite fields ⋮ Anatomy of torsion in the CM case ⋮ Computations of class numbers of real quadratic fields ⋮ There are infinitely many Perrin pseudoprimes ⋮ Efficient CM-constructions of elliptic curves over finite fields ⋮ A $p$-adic algorithm to compute the Hilbert class polynomial ⋮ Factoring with hints ⋮ An exponent one-fifth algorithm for deterministic integer factorisation ⋮ The number of solutions of the Erdős-Straus Equation and sums ofkunit fractions ⋮ Approximating rings of integers in number fields ⋮ Computing endomorphism rings of abelian varieties of dimension two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On distinguishing prime numbers from composite numbers
• An asymptotic formula for the Bergman projection on a certain class of domains in \({\mathbb{C}}\)
• On a problem of Oppenheim concerning Factorisatio Numerorum
• On the distribution in short intervals of integers having no large prime factor
• Factoring integers with elliptic curves
• A bound for the least prime ideal in the Chebotarev density theorem
• Modifications to the number field sieve
• The Factorization of the Ninth Fermat Number
• A Monte Carlo Factoring Algorithm With Linear Storage
• A Rigorous Subexponential Algorithm For Computation of Class Groups
• Solving sparse linear equations over finite fields
• A Probabilistic Factorization Algorithm with Quadratic Forms of Negative Discriminant
• Asymptotically Fast Factorization of Integers
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms
• Fast Multiple-Precision Evaluation of Elementary Functions
• Generation of Elements with Small Modular Squares and Provably Fast Integer Factoring Algorithms
• The NP-completeness column: An ongoing guide