Content deleted Content added
rvv by SUMpTHY |
Talk about how quadratic sieve generalizes Fermat's |
||
Line 107:
==Other improvements==
The fundamental ideas of Fermat's factorization method are the basis of the [[quadratic sieve]] and [[general number field sieve]], the best-known algorithms for factoring "worst-case" large semiprimes. The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of ''a''<sup>2</sup>−''n'', it finds a subset of elements of this sequence whose ''product'' is a square, and it does this in a highly efficient manner. The end result is the same: a difference of square mod ''n'' that, if nontrivial, can be used to factor ''n''.
See also J. McKee, "Speeding Fermat's factoring method", ''Mathematics of Computation'', 68:1729-1737, 1999.
| |||