In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, Dixon's factorization method (also Dixon's random squares method
or Dixon's algorithm) is a general-purpose
integer factorization algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
; it is the prototypical
factor base In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.
Usage in factoring algorithms
A factor base is a ...
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
Carleton University is an English-language public research university in Ottawa, Ontario, Canada. Founded in 1942 as Carleton College, the institution originally operated as a private, non-denominational evening college to serve returning Wo ...
, and was published in 1981.
Basic idea
Dixon's method is based on finding a
congruence of squares modulo the integer N which is intended to factor.
Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:
:N = a^2 - b^2.
That difference is algebraically factorable as (a+b)(a-b); if neither factor equals one, ...
finds such a congruence by selecting random or
pseudo-random
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process.
Background
The generation of random numbers has many uses, such as for rando ...
''x'' values and hoping that the integer ''x''
2 mod N is a
perfect square (in the integers):
:
For example, if , (by starting at 292, the first number greater than and counting up) the is 256, the square of 16. So . Computing the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of and ''N'' using
Euclid's algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an ef ...
gives 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 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 there are many numbers
whose squares can be factorized as
for a fixed set
of small primes, linear algebra modulo 2 on the matrix
will give a subset of the
whose squares combine to a product of small primes to an even power — that is, a subset of the
whose squares multiply to the square of a (hopefully different) number mod N.
Method
Suppose the composite number ''N'' is being factored. Bound ''B'' is chosen, and the ''
factor base In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.
Usage in factoring algorithms
A factor base is a ...
'' is identified (which is called ''P''), the set of all primes less than or equal to ''B''. Next, positive integers ''z'' are sought such that ''z''
2 mod ''N'' is ''B''-smooth. Therefore it can be written, for suitable exponents ''a
i'',
:
When enough of these relations have been generated (it is generally sufficient that the number of relations be a few more than the size of ''P''), the methods of
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
can be used (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:
:
This yields a
congruence of squares of the form which can be turned into a factorization of ''N'', This factorization might turn out to be trivial (i.e. ), which can only happen if in which case another try has to be made with a different combination of relations; but a nontrivial pair of factors of ''N'' can be reached, and the algorithm will terminate.
Pseudocode
input: positive integer
output: non-trivial factor of
Choose bound
Let
be all primes
repeat
for
to
do
Choose