Dixon's factorization method

In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by polynomial. In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by polynomial. The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981. Dixon's method is based on finding a congruence of squares modulo the integer N which we intend to factor. Fermat's factorization method finds such a congruence by selecting random or pseudo-random x values and hoping that the integer x2 mod N is a perfect square (in the integers): For example, if N = 84923, we notice (by starting at 292, the first number greater than √N and counting up) that 5052 mod 84923 is 256, the square of 16. So (505 − 16)(505 + 16) = 0 mod 84923. Computing the greatest common divisor of 505 − 16 and N using Euclid's algorithm gives us 163, which is a factor of N. In practice, selecting random x values will take an impractically long time to find a congruence of squares, since there are only √N squares less than N. Dixon's method replaces the condition 'is the square of an integer' with the much weaker one 'has only small prime factors'; for example, there are 292 squares smaller than 84923; 662 numbers smaller than 84923 whose prime factors are only 2,3,5 or 7; and 4767 whose prime factors are all less than 30. (Such numbers are called B-smooth with respect to some bound B.) If we have lots of numbers a 1 … a n {displaystyle a_{1}ldots a_{n}} whose squares can be factorized as a i 2 mod N = ∏ j = 1 m b j e i j {displaystyle a_{i}^{2}mod N=prod _{j=1}^{m}b_{j}^{e_{ij}}} for a fixed set b 1 … b m {displaystyle b_{1}ldots b_{m}} of small primes, linear algebra modulo 2 on the matrix e i j {displaystyle e_{ij}} will give us a subset of the a i {displaystyle a_{i}} whose squares combine to a product of small primes to an even power — that is, a subset of the a i {displaystyle a_{i}} whose squares multiply to the square of a (hopefully different) number mod N. Suppose we are trying to factor the composite number N. We choose a bound B, and identify the factor base (which we will call P), the set of all primes less than or equal to B. Next, we search for positive integers z such that z2 mod N is B-smooth. We can therefore write, for suitable exponents ai, When we have generated enough of these relations (it's generally sufficient that the number of relations be a few more than the size of P), we can use the methods of linear algebra (for example, Gaussian elimination) to multiply together these various relations in such a way that the exponents of the primes on the right-hand side are all even: