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

Source abstract

Fermat’s well-known factorization algorithm is based on finding a representation of natural numbers N N as the difference of squares. In 1895, Lawrence generalized this idea and applied it to multiples k N kN of the original number. A systematic approach to choose suitable values for k 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 ) ) O(N^{2/9+o(1)}) . This is the first exponential improvement since the establishment of the O ( N 1 / 4 + o ( 1 ) ) O(N^{1/4+o(1)}) bound in 1977.