Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:
That difference is algebraically factorable as ; if neither factor equals one, it is a proper factorization of N.
Each odd number has such a representation. Indeed, if is a factorization of N, then
Since N is odd, then c and d are also odd, so those halves are integers. (A multiple of four is also a difference of squares: let c and d be even.)
In its simplest form, Fermat's method might be even slower than trial division (worst case). Nonetheless, the combination of trial division and Fermat's is more effective than either.
Read more about Fermat's Factorization Method: The Basic Method, Fermat's and Trial Division, Sieve Improvement, Multiplier Improvement, Other Improvements
Famous quotes containing the word method:
“No method nor discipline can supersede the necessity of being forever on the alert. What is a course of history or philosophy, or poetry, no matter how well selected, or the best society, or the most admirable routine of life, compared with the discipline of looking always at what is to be seen? Will you be a reader, a student merely, or a seer? Read your fate, see what is before you, and walk on into futurity.”
—Henry David Thoreau (1817–1862)