In number theory, Dixon's factorization method (also Dixon's algorithm) is a general-purpose integer factorization algorithm. The quadratic sieve is a modification of the basic idea used in Dixon's method. Number theory is the branch of pure mathematics concerned with the properties of numbers in general, and integers in particular, as well as the wider classes of problems that arise from their study. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). ...

The algorithm was designed by John D. Dixon, a mathematician at Carleton University, and was published in 1981. Carleton University is a co-educational, comprehensive university located in the Canadian capital, Ottawa. ...

Basic idea

Dixon's method is based on finding a congruence of squares. Fermat's factorization algorithm finds such a congruence by selecting random or pseudo-random x values and hoping one satisfies the congruence: In number theory, a congruence of squares modulo an integer n is an equality . Such a relationship carries information useful in trying to factor the integer n: finding a congruence of squares modulo n is something sought after in integer factorization. ... A pseudo-random number is a number belonging to a sequence which appears to be random, but can in fact be generated by a finite computation. ...

where n is the integer to be factorized. In practice, selecting random x values will take an impractically long time to find a congruence of squares. Dixon's method is based on satisfying a much weaker condition many times, and the results of these values can be combined into a congruence of squares.

Method

Firstly, a set of primes less than some bound B is chosen. This set of primes is called the factor base. Then, using the polynomial

p(x) = x²(mod n)

many values of x are tested to see if p(x) factors completely over the factor base. If it does, the pair (x,p(x)) is stored. Such a pair is called a relation. Then, once the number of relations collected exceeds the size of the factor base, we can enter the next stage.

The p(x) values are factorized (this is easy since we are certain they factorize completely over the factor base) and the exponents of the prime factors are converted into an exponent vector mod 2. For example, if the factor base is {2, 3, 5, 7} and the p(x) value is 30870, we have:

This gives an exponent vector of:

If we can find some way to add these exponent vectors together (equivalent to multiplying the corresponding relations together) to produce the zero vector (mod 2), then we can get a congruence of squares. Thus we can put the exponent vectors together into a matrix, and formulate an equation:

This can be converted into a matrix equation:

This matrix equation is then solved (using, for example, Gaussian elimination) to find the vector c. Then: In mathematics, Gaussian elimination (not to be confused with Gauss–Jordan elimination), named after Carl Friedrich Gauss, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ...

where the products are taken over all k for which c_k = 1. At least one of the c_k must be one. Because of the way we have solved for c, the right-hand side of the above congruence is a square. We then have a congruence of squares.

Optimizations

The quadratic sieve is an optimization of Dixon's method. It solves a quadratic congruence to find suitable x values much faster than simply by random selection. The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). ...

Other ways to optimize Dixon's method include using a better algorithm to solve the matrix equation. In practice, the Lanczos algorithm is often used. Also, the size of the factor base must be chosen carefully. If it is too small, it will be difficult to find numbers that factorize completely over it. If it is too large, more relations will have to be collected. The Lanczos algorithm is a popular method to find a zero vector in the process of the quadratic sieve. ...

The optimal complexity of Dixon's method is [1]

References

• J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comput., 36(1981), p. 255-260.