A one line factoring algorithm
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.
- Integer factorization as subset-sum problem
- scientific article; zbMATH DE number 5117572 (Why is no real title available?)
- scientific article; zbMATH DE number 1302464 (Why is no real title available?)
- Speeding Fermat’s factoring method
- The improvement of initial value closer to the target for Fermat's factorization algorithm
- Efficient implementation of the Hardy-Ramanujan-Rademacher formula
- On finding Fermat’s pairs
- One approach to factorization of positive integers
This page was built for publication: A one line factoring algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2898887)
