In order to find integers 
and 
such that
 |
(1)
|
(a modified form of Fermat's factorization method), in which case there is a 50% chance that 
is a factor of 
, choose a random integer 
,
compute
 |
(2)
|
and try to factor 
. If 
is not easily factorable (up to some small trial divisor
),
try another 
.
In practice, the trial 
s are usually taken to be 
, with 
, 2, ..., which allows the quadratic
sieve factorization method to be used. Continue finding and factoring 
s until 
are found, where 
is the prime counting
function. Now for each 
, write
 |
(3)
|
and form the exponent vector
![v(r_i)=[a_(1i); a_(2i); |; a_(Ni)].](/images/equations/DixonsFactorizationMethod/NumberedEquation4.svg) |
(4)
|
Now, if 
are even for any 
, then 
is a square number and
we have found a solution to (◇). If not, look for a linear
combination 
such that the elements are all even, i.e.,
![c_1[a_(11); a_(21); |; a_(N1)]+c_2[a_(12); a_(22); |; a_(N2)]+...+c_N[a_(1N); a_(2N); |; a_(NN)]=[0; 0; |; 0] (mod 2)](/images/equations/DixonsFactorizationMethod/NumberedEquation5.svg) |
(5)
|
![[a_(11) a_(12) ... a_(1N); a_(21) a_(22) ... a_(2N); | | ... |; a_(N1) a_(N2) ... a_(NN)][c_1; c_2; |; c_N]=[0; 0; |; 0] (mod 2).](/images/equations/DixonsFactorizationMethod/NumberedEquation6.svg) |
(6)
|
Since this must be solved only mod 2, the problem can be simplified by replacing the 
s
with
 |
(7)
|
Gaussian elimination can then be used to solve
 |
(8)
|
for 
,
where 
is a vector equal to 
(mod 2). Once 
is known, then we have
 |
(9)
|
where the products are taken over all 
for which 
. Both sides are perfect
squares, so we have a 50% chance that this yields a nontrivial factor of 
.
If it does not, then we proceed to a different 
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 
.
