A one line factoring algorithm (Q2898887)

The paper proposes a variant of Fermat's factoring method (the original Fermat's method tries to write the number \(n\)\, to factor as a difference of two squares). Although the Quadratic Sieve and the Number Field Sieve, see for instance \textit{A. K. Lenstra} and \textit{H. W. Lenstra} (eds.) [The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)] are nowadays the best factoring methods, in some cases Fermat's like methods can be effective in some cases. The proposed algorithm is similar to a method due to \textit{S. R. Lehman} [Math. Comput. 28, 637--646 (1974; Zbl 0285.10006)].NEWLINENEWLINESection 2 describes the algorithm, Section 3 proposes some tricks to speed it up and Section 4 a heuristic analysis showing that the heuristic running time of the algorithm is \(O(n^{1/3+\varepsilon})\) (the same complexity of Lehman's method).NEWLINENEWLINESection 5 shows numerical results of an implementation and a comparison with the factor command in the Pari/GP package (Table 1) and Section 6 does the same (Table 2) for the Lehman's algorithm (in both cases for numbers \(n\) up to 40 bits. Finally Section 7 claims that the proposed method is very competitive for numbers \(n\) in a certain sparse class.