A log-log speedup for exponent one-fifth deterministic integer factorisation

DOI10.1090/mcom/3708zbMath1491.11110arXiv2105.11105OpenAlexW3165388365MaRDI QIDQ5070544

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

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

Related Items

Deterministic factoring with oracles, Explicit methods in number theory. Abstracts from the workshop held July 18--24, 2021 (hybrid meeting), On oracle factoring of integers, Integer factorization as subset-sum problem, A deterministic algorithm for finding \(r\)-power divisors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Prime numbers and computer methods for factorization.
• Integer factoring
• Integer multiplication in time \(O(n\log n)\)
• A deterministic algorithm for integer factorization
• Faster deterministic integer factorization
• Modern Computer Algebra
• Mathematics of Public Key Cryptography
• Modern Computer Arithmetic
• A babystep-giantstep method for faster deterministic integer factorization
• The Generalized Gauss Reduction Algorithm
• Factoring Large Integers
• An exponent one-fifth algorithm for deterministic integer factorisation
• A time-space tradeoff for Lehman’s deterministic integer factorization method
• An LLL-reduction algorithm with quasi-linear time complexity
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator