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 large semiprimes, which are the "worst-case". The primary improvement that quadratic sieve makes over Fermat's factorization method is that instead of simply finding a square in the sequence of, 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.
Read more about this topic: Fermat's Factorization Method
Famous quotes containing the word improvements:
“The improvements of ages have had but little influence on the essential laws of man’s existence: as our skeletons, probably, are not to be distinguished from those of our ancestors.”
—Henry David Thoreau (1817–1862)
“A country whose buildings are of wood, can never increase in its improvements to any considerable degree.... Whereas when buildings are of durable materials, every new edifice is an actual and permanent acquisition to the state, adding to its value as well as to its ornament.”
—Thomas Jefferson (1743–1826)