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 0(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 1.05 X 1020 on the CDC 6400. Introduction.Fermat's method for factoring an odd positive integer consists of finding = x2 -y2 where x and y are positive integers.We find in successionand determine whether the difference x2 -n is a square or not.If p and q are primes and = pq, then Fermat's method is quite efficient if p/q is near 1, but it requires a large number of trials if p/q is not near 1.Lawrence [2] used a method which is designed to be efficient if p/q is near a/b where a and b are small relatively prime integers.We consider x2 -y2 = 4kn, k = ab with 1 ^ H r. The idea we wish to use is to divide up the interval [0, 1] into parts.Each part will correspond to a fraction a/b, and these parts will fill the interval [0, 1].This means that, for each r, we find a sequence Sr which includes a/b when O^a^b, b>0 and ab ^ r.This is reminiscent of the Farey sequence of order r.We prove in Section 3 that many of the ideas go over to the new sequence ST.In particular, one obtains a dissection of the continuum similar to the Farey dissection of [0, 1].The main theorem is given in Section 2. Its proof is contained in Section 4. Numerical results were obtained by a computation on the CDC 6400 of the Computer Center of the University of California at Berkeley.An Algol program is also given in Section 5.2. The Theorem.We shall use gcd(a, b) for the greatest common divisor of a and b.Theorem.Suppose that n is a positive odd integer and r is an integer such that 1 r < n1/2.Ifn = pq where p and q are primes and (n/ir + 1))1/2 < p g nl/2,