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:
“... 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)
“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)