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)].](https://mathworld.wolfram.com/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)](https://mathworld.wolfram.com/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).](https://mathworld.wolfram.com/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 
.
