Dixon's factoring method

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

The method was developed by the mathematician John D. Dixon at Carleton University and published in 1981. The purpose was the theoretical investigation of factor base methods and not the practical application, because at that time the continued fraction method already existed as a more efficient representative of this class of factorization methods .

Working principle

Let be the number to be factored. The Dixon method is based on a congruence of square numbers ${\displaystyle N}$

${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$

( 1)

${\displaystyle {\text{mit}}\;\;x\not \equiv y,\,x\not \equiv -y{\pmod {N}}}$

(2)

to investigate. Then the greatest common factors are and real factors of . Because (1) is divisor of , but because of (2) it is neither of nor of , so that the prime factors of divide up and . ${\displaystyle \operatorname {ggT} (x+y,N)}$ ${\displaystyle \operatorname {ggT} (x-y,N)}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle x^{2}-y^{2}=(x+y)(x-y)}$ ${\displaystyle x+y}$ ${\displaystyle x-y}$ ${\displaystyle N}$ ${\displaystyle x+y}$ ${\displaystyle x-y}$

It would be inefficient to search for a congruence (1) directly. Instead, you first choose a factor base that consists of all prime numbers to . Then you determine congruences ${\displaystyle p_{1}=2}$ ${\displaystyle p_{k}}$

${\displaystyle x_{i}^{2}\equiv a_{i}{\pmod {N}},}$

(3)

whose do not contain a prime factor greater than . Such numbers are called - smooth . Then one multiplies a suitable non- empty selection to get a congruence of squares (because it applies ): ${\displaystyle a_{i}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{k}}$ ${\displaystyle M}$ ${\displaystyle a\equiv b,c\equiv d\,\Rightarrow \,ac\equiv bd}$

${\displaystyle x^{2}=\prod _{i\in M}x_{i}^{2}\,\equiv \,y^{2}=\prod _{i\in M}a_{i}{\pmod {N}}}$

(4)

By restricting oneself to -smooth , one only needs a manageable number of congruences (3), namely, for example , so that there is a selection of whose product is a square number. In addition, the factors can be factored quickly enough, e.g. B. by trial division . Is their prime factorization ${\displaystyle p_{k}}$ ${\displaystyle a_{i}}$ ${\displaystyle k}$ ${\displaystyle M}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$

${\displaystyle a_{i}=\prod _{j=1}^{k}p_{j}^{e_{ij}}}$

known, one can efficiently determine a selection . In order for the product of the chosen to be a square, the multiplicity of each prime factor must be even. For this one uses methods of linear algebra modulo 2 on the matrix of the multiplicities . ${\displaystyle M}$ ${\displaystyle a_{i}}$ ${\displaystyle (e_{ij})}$

One can show: If it contains at least two different prime factors, i.e. is not a power of a prime number, then at least half of the congruences of squares with coprime to fulfill the condition . ${\displaystyle N}$ ${\displaystyle x^{2}\equiv y^{2}{\pmod {N}}}$ ${\displaystyle x,y}$ ${\displaystyle N}$ ${\displaystyle x\not \equiv \pm y{\pmod {N}}}$

Action

You choose a number and determine the factor base with the smallest prime numbers. It is recommended to include the prime numbers in the factor base up to a bound in the order of magnitude . ${\displaystyle k}$ ${\displaystyle \{2,3,5,\dotsc ,p_{k}\}}$ ${\displaystyle k}$ ${\displaystyle p_{k}\approx \exp \left({\tfrac {1}{2}}{\sqrt {\ln N\ln \ln N}}\right)}$

Then you create in the area and try to factorize. Dixons method provides that (pseudo) random numbers as are used, but this is not mandatory; you can z. B. also take the members of a regular sequence such as . ${\displaystyle x_{i}}$ ${\displaystyle \left\lceil {\sqrt {N}}\right\rceil \leq x_{i}<N}$ ${\displaystyle a_{i}=x_{i}^{2}{\bmod {N}}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i+1}=x_{i}+1}$

The pairs with -smooth are kept, together with the factoring in the form of the multiplicities . If one has a sufficient number of them available (preferably a little more than ), one tries to determine a selection of these pairs which, when multiplied with one another, result in a congruence of square numbers according to (4) . ${\displaystyle (x_{i},a_{i})}$ ${\displaystyle p_{k}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle e_{ij}}$ ${\displaystyle k}$ ${\displaystyle M}$

This can e.g. This can be done, for example, with Gaussian elimination : A binary matrix is ​​formed which contains a row for each of the pairs found and a column for each factor of the factor base. A 1 is entered in a matrix element if the relevant factor with an odd multiple is contained in this row, and otherwise a 0. The matrix can be brought with the operations "Swap columns" and "Add one column to another modulo 2 (i.e. XOR link) ”into a triangular shape, from which one can read off which (not empty) selection of the lines results in the zero vector . Then the product of these rows contains every factor with an even multiple and is a square. ${\displaystyle (x_{i},a_{i})}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$

If one has found such a selection, one calculates

${\displaystyle x=\prod _{i\in M}x_{i}{\bmod {N}};\quad y={\sqrt {\prod _{i\in M}a_{i}}}{\bmod {N}}=\prod _{j=1}^{k}p_{j}^{{\tfrac {1}{2}}\sum _{i\in M}e_{ij}}{\bmod {N}}}$

and then or . If this does not provide a real divisor of , then it is obvious and you have to try another combination of the , if necessary you have to collect more such pairs. ${\displaystyle \operatorname {ggT} (x-y,N)}$ ${\displaystyle \operatorname {ggT} (x+y,N)}$ ${\displaystyle N}$ ${\displaystyle x\equiv \pm y{\pmod {N}}}$ ${\displaystyle (x_{i},a_{i})}$

properties

With an optimal choice of the size of the factor base, Dixon's method has a time complexity in (see Landau symbols ). It is the only factor-based method for which a time complexity bound is known that does not depend on assumptions about the smoothness properties of the values ​​of certain polynomials. ${\displaystyle \operatorname {O} \left(\exp \left(2{\sqrt {2\ln N\ln \ln N}}\right)\right)}$

It is a general method of factoring; that is, it can be applied to almost any compound . Only when there is a prime power, i.e. of the form , does the procedure fail. However, this case can easily be checked in advance. ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N=p^{m}}$

The time it takes to factor a certain one depends only on the size of (with some variation), but not on the size of the prime factors it contains. There are much more efficient methods of finding small factors, e.g. B. the trial division or the Pollard-Rho method . This should be tried first, even if it contains or could contain small factors, in order to then possibly apply a factor base method such as Dixon's method to the unfactorized part of . ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle N}$

Improvements

You can calculate that too . This is a little more efficient because subtraction is usually faster than modulo division. But it is more important that the prime numbers , for which there is no quadratic remainder modulo  , do not have to be included in the factor base. Only if there is a are with , may by be divisible. ${\displaystyle a_{i}}$ ${\displaystyle a_{i}=x_{i}^{2}-N}$ ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle p}$ ${\displaystyle x}$ ${\displaystyle x^{2}\equiv N{\pmod {p}}}$ ${\displaystyle a_{i}}$ ${\displaystyle p}$

In addition, it is beneficial to limit yourself to those that are in the vicinity of and thereby yield a relatively small amount that is more likely to completely decay above the factor base. It can also be used that are less than when the factor is included in the factor base to represent the negatives . The exponent of must then also be even so that a positive product arises, i.e. that is, the factor can be treated the same as the prime factors in determining the selection . ${\displaystyle x_{i}}$ ${\displaystyle {\sqrt {N}}}$ ${\displaystyle a_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle {\sqrt {N}}}$ ${\displaystyle -1}$ ${\displaystyle a_{i}}$ ${\displaystyle -1}$ ${\displaystyle a_{i}}$ ${\displaystyle -1}$ ${\displaystyle M}$

They can also be used if they are smooth except for a single prime factor larger . If after dividing the factors until a part is larger and smaller , it must be prime and is thus completely factored. This results in significantly more congruences that can be combined according to (4) , with the same effort for the decomposition of the . The determination of the selection then becomes more complicated, however, because the additional factors must also be larger in the product of an even multiplicity. ${\displaystyle a_{i}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{k}}$ ${\displaystyle 1}$ ${\displaystyle p_{k+1}^{2}}$ ${\displaystyle a_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle M}$ ${\displaystyle p_{k}}$ ${\displaystyle a_{i}}$

Another possibility is to initially subdivide only the smallest prime factors and then to discard those whose unfactorized remainder is greater than a suitably chosen limit, because these are only with a low probability - smooth. Only the rest are then also divided by. ${\displaystyle a_{i}}$ ${\displaystyle 2,\dotsc ,p_{r}}$ ${\displaystyle p_{k}}$ ${\displaystyle p_{r+1},\dotsc ,p_{k}}$

There are also more efficient methods of determining the choice , e.g. B. the block Lanczos method , which uses the thin population of the matrix . This avoids the cubic complexity (in ) of Gaussian elimination. ${\displaystyle M}$ ${\displaystyle (e_{ij})}$ ${\displaystyle k}$

The principle of congruences (3) to collect and to a solution of (1) to be combined is used method factor base by other, more efficient, such as the quadratic filter , the number field sieve and the continued fraction method . These differ essentially only in the method of how they find congruences, which are then combined into a congruence of squares. Some of the improvements mentioned can also be applied to these methods. Dixon's method could be seen as a prototype of these methods in terms of functionality, even if the continued fraction method was the first to be developed.

Web links

• Eric W. Weisstein : Dixon's Factorization Method . In: MathWorld (English).

Individual evidence

1. ↑ Thorsten Kleinjung et al: Factorization of a 768-bit RSA modulus. Version 1.4, February 18, 2010, p. 3 ( PDF ).
2. ^ John D. Dixon, Asymptotically Fast Factorization of Integers. In: Mathematics of Computation. Volume 36, No. 153, January 1981, pp. 255-260 ( PDF ).