An exponent one-fifth algorithm for deterministic integer factorisation

DOI10.1090/MCOM/3658MaRDI QIDQ4956932zbMATH OpenOpenAlexFDO

Authors David I. Harvey

Publication date 2 September 2021

Published in Mathematics of Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Factorization (11Y05)

Abstract: Hittmeir recently presented a deterministic algorithm that provably computes the prime factorisation of a positive integer $N$ in $N^{2/9+o(1)}$ bit operations. Prior to this breakthrough, the best known complexity bound for this problem was $N^{1/4+o(1)}$, a result going back to the 1970s. In this paper we push Hittmeir's techniques further, obtaining a rigorous, deterministic factoring algorithm with complexity $N^{1/5+o(1)}$.

Recommendations

• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• A babystep-giantstep method for faster deterministic integer factorization
• A deterministic algorithm for integer factorization
• Faster deterministic integer factorization
• Deterministic factorization of sums and differences of powers

Cites work

• scientific article; zbMATH DE number 5532109 (Why is no real title available?)
• scientific article; zbMATH DE number 3460351 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 1113841 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• scientific article; zbMATH DE number 3353398 (Why is no real title available?)
• A Rigorous Time Bound for Factoring Integers
• A babystep-giantstep method for faster deterministic integer factorization
• A time-space tradeoff for Lehman's deterministic integer factorization method
• An introduction to the theory of numbers. Edited and revised by D. R. Heath-Brown and J. H. Silverman. With a foreword by Andrew Wiles
• Factoring Large Integers
• Faster deterministic integer factorization
• Integer multiplication in time \(O(n\log n)\)
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Modern computer algebra
• Modern computer arithmetic
• Monte Carlo Methods for Index Computation (mod p)
• On the complexity of integer matrix multiplication
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Some results on computational complexity

Cited in

(14)

• Deterministic factorization of sums and differences of powers
• Deterministic factoring with oracles
• Representing the integer factorization problem using ordered binary decision diagrams
• Supersingular j-invariants and the class number of ℚ(−p)
• A generalization of Lehman's method
• A babystep-giantstep method for faster deterministic integer factorization
• An integer factoring algorithm based on elliptic divisibility sequences
• Faster deterministic integer factorization
• On oracle factoring of integers
• Integer factorization as subset-sum problem
• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• A deterministic algorithm for integer factorization
• A Simple and Improved Algorithm for Integer Factorization with Implicit Hints
• Smooth subsum search a heuristic for practical integer factorization

This page was built for publication: An exponent one-fifth algorithm for deterministic integer factorisation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956932)