Factoring Large Integers
Robert S. Lehman · Mathematics of Computation · 1974
A modification of Fermat’s difference of squares method is used for factoring large integers. This modification permits factoring n in $O({n^{1/3}})$ elementary operations, where addition, subtraction, multiplication, division, or the extraction of a square root is considered as an elementary operation. A principal part is played by the use of a dissection of the continuum similar to the Farey dissection. This has been programmed for $n \leqq 1.05 \times {10^{20}}$ on the CDC 6400.