Dixon's Factorization Method

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

$$x^2\equiv y^2\ \left({{\rm mod\ } {n}}\right)$$ (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),$$ (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}},$$ (3)

and form the Exponent Vector

$${\bf v}(r_i)=\left[{\matrix{a_{1i}\cr a_{2i}\cr \vdots\cr a_{Ni}\cr}}\right].$$ (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)$$ (5)

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

Since this must be solved only mod 2, the problem can be simplified by replacing the $a_{ij}$s with

$$b_{ij}=\cases{ 0 & for $a_{ij}$\ even\cr 1 & for $a_{ij}$\ odd.\cr}$$ (7)

Gaussian Elimination can then be used to solve

$${\hbox{\sf b}}{\bf c}={\bf z}$$ (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),$$ (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$.

References

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.