Fermat's factorization method: Difference between revisions

Revision as of 17:31, 20 November 2007

Revision as of 19:04, 13 December 2007

Line 110:

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''²−''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, "[http://www.ams.org/mcom/1999-68-228/S0025-5718-99-01133-3/home.html Speeding Fermat's factoring method]", ''Mathematics of Computation'', 68:1729-1737, (1999).

[[Category:Integer factorization algorithms]]