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:
“I was interested to see how a pioneer lived on this side of the country. His life is in some respects more adventurous than that of his brother in the West; for he contends with winter as well as the wilderness, and there is a greater interval of time at least between him and the army which is to follow. Here immigration is a tide which may ebb when it has swept away the pines; there it is not a tide, but an inundation, and roads and other improvements come steadily rushing after.”
—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)