A time-space tradeoff for Lehman's deterministic integer factorization method

DOI10.1090/MCOM/3623MaRDI QIDQ4992239zbMATH OpenOpenAlexFDO

Authors Markus Hittmeir

Publication date 7 June 2021

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

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

Mathematics Subject Classification ID

Factorization (11Y05)

Abstract: Fermat's well-known factorization algorithm is based on finding a representation of natural numbers $N$ as the difference of squares. In 1895, Lawrence generalized this idea and applied it to multiples $kN$ of the original number. A systematic approach to choose suitable values for $k$ was introduced by Lehman in 1974, which resulted in the first deterministic factorization algorithm considerably faster than trial division. In this paper, we construct a time-space tradeoff for Lawrence's generalization and apply it together with Lehman's result to obtain a deterministic integer factorization algorithm with runtime complexity $O(N^{2/9+o(1)})$. This is the first exponential improvement since the establishment of the $O(N^{1/4+o(1)})$ bound in 1977.

Recommendations

• A deterministic algorithm for integer factorization
• Speeding Fermat’s factoring method
• Deterministic factorization of sums and differences of powers
• scientific article; zbMATH DE number 475434
• A babystep-giantstep method for faster deterministic integer factorization

Cites work

• A babystep-giantstep method for faster deterministic integer factorization
• Factoring Large Integers
• Faster deterministic integer factorization
• Faster integer multiplication using plain vanilla FFT primes
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• Integer factoring
• Linear Recurrences with Polynomial Coefficients and Application to Integer Factorization and Cartier–Manin Operator
• Prime numbers and computer methods for factorization.
• Some results on computational complexity
• The joy of factoring

Cited in

(13)

• 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
• The space complexity analysis in the general number field sieve integer factorization
• A babystep-giantstep method for faster deterministic integer factorization
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• An exponent one-fifth algorithm for deterministic integer factorisation
• A \(\log\)-\(\log\) speedup for exponent one-fifth deterministic integer factorisation
• Deterministic factoring with oracles
• Representing the integer factorization problem using ordered binary decision diagrams
• A generalization of Lehman's method
• Smooth subsum search a heuristic for practical integer factorization
• Lempel-Ziv factorization using less time \& space

This page was built for publication: A time-space tradeoff for Lehman's deterministic integer factorization method

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