A - speedup for exponent one-fifth deterministic integer factorisation

DOI10.1090/MCOM/3708MaRDI QIDQ5070544zbMATH OpenOpenAlexFDO

Authors David I. Harvey, Markus Hittmeir

Publication date 13 April 2022

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

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

zbMATH Keywords

latticedeterministic algorithminteger factorization

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Factorization; primality (11A51)

Abstract: Building on techniques recently introduced by the second author, and further developed by the first author, we show that a positive integer $N$ may be rigorously and deterministically factored into primes in at most [ Oleft( frac{N^{1/5} log^{16/5} N}{(loglog N)^{3/5}} ight) ] bit operations. This improves on the previous best known result by a factor of $(loglogN{)}^{3/5}$.

Recommendations

• An exponent one-fifth algorithm for deterministic integer factorisation
• A deterministic algorithm for integer factorization
• Faster deterministic integer factorization
• Asymptotically Fast Factorization of Integers
• scientific article; zbMATH DE number 475434

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 611919 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• scientific article; zbMATH DE number 2206373 (Why is no real title available?)
• A babystep-giantstep method for faster deterministic integer factorization
• A deterministic algorithm for integer factorization
• A time-space tradeoff for Lehman's deterministic integer factorization method
• An LLL-reduction algorithm with quasi-linear time complexity, extended abstract
• An exponent one-fifth algorithm for deterministic integer factorisation
• Factoring Large Integers
• Faster deterministic integer factorization
• Integer factoring
• Integer multiplication in time \(O(n\log n)\)
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Mathematics of public key cryptography.
• Modern computer algebra
• Modern computer arithmetic
• Multiplicative number theory. I. Classical theory
• Prime numbers and computer methods for factorization.
• The Generalized Gauss Reduction Algorithm
• The joy of factoring

Cited in

(11)

• Explicit methods in number theory. Abstracts from the workshop held July 18--24, 2021 (hybrid meeting)
• Deterministic factorization of sums and differences of powers
• An exponent one-fifth algorithm for deterministic integer factorisation
• Elliptic-curve factoring, witnesses and oracles
• On oracle factoring of integers
• A generalization of Lehman's method
• Smooth subsum search a heuristic for practical integer factorization
• Integer factorization as subset-sum problem
• Faster deterministic integer factorization
• Deterministic factoring with oracles
• A deterministic algorithm for finding \(r\)-power divisors

This page was built for publication: A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation

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