| 释义 |
Dixon's Factorization MethodIn order to find Integers  and  such that
 | (1) |
 is aFactor of  , choose a Random Integer  , compute
 | (2) |
 . 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, ..., whichallows 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) |
 | (4) |
 are even for any  , then is a Square Number and we have found a solution to (1).If not, look for a linear combination  such that the elements are all even, i.e.,
 | (5) |
 | (6) |
 s with
 | (7) |
 | (8) |
 , where  is a Vector equal to  (mod 2). Once is known, then we have
 | (9) |
 . 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 repeatthe procedure. There is no guarantee that this method will yield a factor, but in practice it produces factors faster thanany method using trial divisors. It is especially amenable to parallel processing, since each processor can work on adifferent value of .
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.
|