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:
“I have a new method of poetry. All you got to do is look over your notebooks ... or lay down on a couch, and think of anything that comes into your head, especially the miseries.... Then arrange in lines of two, three or four words each, don’t bother about sentences, in sections of two, three or four lines each.”
—Allen Ginsberg (b. 1926)