Dixon,s Factorization Method
المؤلف:
Bressoud, D. M
المصدر:
Factorization and Primality Testing. New York: Springer-Verlag
الجزء والصفحة:
...
12-9-2020
1116
Dixon's Factorization Method
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.gif) |
(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.gif) |
(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.gif) |
(6)
|
Since this must be solved only mod 2, the problem can be simplified by replacing the 
s with
![b_(ij)=<span style=]() {0 for a_(ij) even; 1 for a_(ij) odd. " src="https://mathworld.wolfram.com/images/equations/DixonsFactorizationMethod/NumberedEquation7.gif" style="height:46px; width:137px" /> |
(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 
REFERENCES:
Bressoud, D. M. Factorization and Primality 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.
الاكثر قراءة في نظرية الاعداد
اخر الاخبار
اخبار العتبة العباسية المقدسة
