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:
“In child rearing it would unquestionably be easier if a child were to do something because we say so. The authoritarian method does expedite things, but it does not produce independent functioning. If a child has not mastered the underlying principles of human interactions and merely conforms out of coercion or conditioning, he has no tools to use, no resources to apply in the next situation that confronts him.”
—Elaine Heffner (20th century)