In number theory, Dixon's factorization method (also Dixon's algorithm) is a general-purpose integer factorization algorithm. The quadratic sieve is a modifications of the basic idea used in Dixon's method. Traditionally, number theory is that branch of pure mathematics concerned with the properties of integers. ... In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ... Flowcharts are often used to represent algorithms. ... The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known. ...

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² − 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 or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, 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. 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. ...

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.