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)
“... these great improvements of modern times are blessings or curses on us, just in the same ratio as the mental, moral, and religious rule over the animal; or the animal propensities of our nature predominate over the intellectual and moral. The spider elaborates poison from the same flower, in which the bee finds materials out of which she manufactures honey.”
—Harriot K. Hunt (1805–1875)