info prev up next book cdrom email home

Dixon's Factorization Method

In order to find Integers $x$ and $y$ such that

x^2\equiv y^2\ \left({{\rm mod\ } {n}}\right)
\end{displaymath} (1)

(a modified form of Fermat's Factorization Method), in which case there is a 50% chance that $\mathop{\rm GCD}\nolimits (n,x-y)$ is a Factor of $n$, choose a Random Integer $r_i$, compute
g(r_i)\equiv {r_i}^2\ \left({{\rm mod\ } {n}}\right),
\end{displaymath} (2)

and try to factor $g(r_i)$. If $g(r_i)$ is not easily factorable (up to some small trial divisor $d$), try another $r_i$. In practice, the trial $r$s are usually taken to be $\left\lfloor{\sqrt{n}}\right\rfloor +k$, with $k=1$, 2, ..., which allows the Quadratic Sieve Factorization Method to be used. Continue finding and factoring $g(r_i)$s until $N\equiv\pi{d}$ are found, where $\pi$ is the Prime Counting Function. Now for each $g(r_i)$, write
g(r_i)={p_{1i}}^{a_{1i}}{p_{2i}}^{a_{2i}}\dots {p_{Ni}}^{a_{Ni}},
\end{displaymath} (3)

and form the Exponent Vector
{\bf v}(r_i)=\left[{\matrix{a_{1i}\cr a_{2i}\cr \vdots\cr a_{Ni}\cr}}\right].
\end{displaymath} (4)

Now, if $a_{ki}$ are even for any $k$, then $g(r_i)$ is a Square Number and we have found a solution to (1). If not, look for a linear combination $\sum_{i} c_i{\bf v}(r_i)$ such that the elements are all even, i.e.,

c_1\left[{\matrix{a_{11}\cr a_{21}\cr \vdots\cr a_{N1}\cr}}\...
...matrix{0\cr 0\cr \vdots\cr 0\cr}}\right] \quad ({\rm mod\ } 2)
\end{displaymath} (5)

a_{11} & a_{12} & \cdots & a_{1N}\cr
a_{21} ...
...atrix{0\cr 0\cr \vdots\cr 0\cr}}\right] \quad ({\rm mod\ } 2).
\end{displaymath} (6)

Since this must be solved only mod 2, the problem can be simplified by replacing the $a_{ij}$s with
0 & for $a_{ij}$\ even\cr
1 & for $a_{ij}$\ odd.\cr}
\end{displaymath} (7)

Gaussian Elimination can then be used to solve
{\hbox{\sf b}}{\bf c}={\bf z}
\end{displaymath} (8)

for ${\bf c}$, where ${\bf z}$ is a Vector equal to ${\bf0}$ (mod 2). Once ${\bf c}$ is known, then we have
\prod_k g(r_k)\equiv \prod_k {r_k}^2\ \left({{\rm mod\ } {n}}\right),
\end{displaymath} (9)

where the products are taken over all $k$ for which $c_k=1$. Both sides are Perfect Squares, so we have a 50% chance that this yields a nontrivial factor of $n$. If it does not, then we proceed to a different ${\bf z}$ and repeat the procedure. There is no guarantee that this method will yield a factor, but in practice it produces factors faster than any method using trial divisors. It is especially amenable to parallel processing, since each processor can work on a different value of $r$.


Bressoud, D. M. Factorization and Prime Testing. New York: Springer-Verlag, pp. 102-104, 1989.

Dixon, J. D. ``Asymptotically Fast Factorization of Integers.'' Math. Comput. 36, 255-260, 1981.

Lenstra, A. K. and Lenstra, H. W. Jr. ``Algorithms in Number Theory.'' In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (Ed. J. van Leeuwen). New York: Elsevier, pp. 673-715, 1990.

Pomerance, C. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein