Dixon's factorization method

Dixon's factorization method, also Dixon's random squares method is a factorization, that is, an algorithm for computing the prime factorization of a given composite natural number.

The method was developed by mathematician John D. Dixon at Carleton University and published in 1981.

Principle of operation

Be the number to be factored. The method of Dixon is based on a congruence of squares

To be determined. Then the greatest common divisor and proper divisors of. Because of ( 1) is a divisor of, but because of ( 2) either from or of, so that the prime factors of up and divide.

It would be inefficient to directly search for a congruence ( 1). Instead, one first chooses a factor base consisting of all prime numbers up. Then determined congruences

Which no prime factor greater than contain. One calls such numbers - smooth. Then you multiply a suitable non- empty selection to obtain a congruence of squares ( because it is ):

By limited to - smooth, one needs only a small number of congruences (3 ), namely about to make a selection from there, whose product is a square number. In addition, this are fast enough factorizable, eg by trial division. Is the prime factorization

Known, one can determine a selection efficiently. Thus, the product of a square is selected, the multiplicity of its prime factors must be all straight. Are used for methods of linear algebra modulo 2 to the matrix of the multiplicities.

One can show that if at least two different prime factors contains, ie is not a power of a prime number, then fulfilled at least half of congruences of squares with prime to the condition.

Procedure

One chooses a number and determines the factor base with the smallest primes. It is recommended that the prime numbers up to a limit in the order of the base factor.

Then, generated in the area and tries to factoring. Dixon's method provides that ( pseudo-) random numbers are as used but this is not mandatory; you can, for example, how to take the links of a regular sequence about.

The pairs with smooth - kept, together with the factorization of the form of the multiplicities. When a sufficient number of them appearing at its disposal (preferably a little more than), one tries to determine a selection of these pairs, which multiplies a congruence of squares corresponding to ( 4) together yield.

This can be done for example with the Gaussian elimination: forming a binary matrix containing a column for each of the pairs found a row and for each factor, the factor basis. In a matrix element is a 1 is entered when the relevant factor with odd multiplicity in which this line is included, otherwise a 0 Bring the matrix with the operations " column swap " and " one column to another modulo 2 add (ie XORing ) " into a triangle shape, where you can see which ( non-empty ) selection of rows is the zero vector. Then the product of this line contains any factor straight multiplicity and is a square.

If you have found such a selection, we can calculate

If now provides no proper divisors of, then obviously, and you have a different combination of taste, if necessary, you have to collect more such pairs.

Properties

Dixon's method has at optimum choice of the size of the factor base a time complexity (see Landau symbols). It is the only factor based method, for a known time complexity barrier, which does not depend on assumptions about the smoothness characteristics of the values ​​of certain polynomials.

It is a general factorization, ie it can to ( almost ) all compound to be applied. Only when a Primpotenz is so of the mold, the method fails. This case can also be easily checked in advance, which you can also find the prime factors and thus has factored.

The time for factoring a given depends essentially only on the size of from, and not by the size of the prime factors contained. Locating small factors, there are much more efficient method, such as the trial division or Pollard 's Rho- method. These should be tried first, albeit small factors contain or could contain, and then apply any one factor based methods such as Dixon's method to the unfaktorisierten part of.

Improvements

One can also calculate. This is slightly more efficient, since the subtraction is usually faster than the modulo division. More important though is that you then do not take the primes for which is not a quadratic residue, in the factor base. Only if there is one with, may be divisible by. In addition, it is advantageous to limit themselves to near, which provide a relatively small amount, the completely disintegrates more likely over the factor base. It can also be used when the factor is added to the base factor to represent the negative.

They can also be used if they are smooth except for a larger single prime factor. If after Abdividieren the factors to the remaining portion is less than it should be a prime, and is fully factored. This gives much more congruences, which can be combined according to (4 ), wherein the natural effort for the disassembling of the.

Another option is to first abzudividieren of which only the smallest prime factors, then those whose unfaktorisierter residual is greater than a suitably chosen limit, reject, because they are only with low probability - smooth. Only the remaining are then divided by.

There is also more efficient method for determining the selection, such as the block - Lanczos method, which uses the thin cast the matrix. This avoids the cubic complexity ( in ) the Gaussian elimination.

To collect the principle congruences (3) and combine them into a solution for ( 1), is also used by other, more efficient factor based method, as it were for the Dixons method is the prototype, such as the Quadratic sieve, the continued fraction method and the number field sieve. This essentially differ only in the method, as they are congruences, which are then combined into a congruence of squares.

Credentials

• Factorization