Factoring Large Integers

Abstract

A modification of Fermat's difference of squares method is used for factoring large integers. This modification permits factoring n in <!-- MATH $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 <!-- MATH $n \leqq 1.05 \times {10^{20}}$ --> on the CDC 6400.