An exponent one-fifth algorithm for deterministic integer factorisation

DOI10.1090/MCOM/3658zbMATH Open1472.11311arXiv2010.05450OpenAlexW3156290661MaRDI QIDQ4956932FDOQ4956932

Authors: David I. Harvey 

Publication date: 2 September 2021

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

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)}$.

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

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

Mathematics Subject Classification ID

Factorization (11Y05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Small solutions to polynomial equations, and low exponent RSA vulnerabilities
• Modern computer arithmetic
• 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
• Monte Carlo Methods for Index Computation (mod p)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A time-space tradeoff for Lehman's deterministic integer factorization method
• Modern computer algebra
• Faster deterministic integer factorization
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Title not available (Why is that?)
• A Rigorous Time Bound for Factoring Integers
• Some results on computational complexity
• Integer multiplication in time \(O(n\log n)\)
• On the complexity of integer matrix multiplication
• Factoring Large Integers
• A babystep-giantstep method for faster deterministic integer factorization
• Title not available (Why is that?)

Cited In (14)

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