Fermat's factorization method: Difference between revisions

Revision as of 13:46, 28 January 2008

Revision as of 02:44, 10 March 2008

Line 28:

The third try produces a square. <math>A=80</math>, <math>B=21</math>, and the factors are <math>A-B = 59</math>, and <math>A+B = 101</math>.

Suppose N has more than onetwo factorizationprime factors. That procedure first finds the factorization with the least values of ''a'' and ''b''. That is, <math>a+b</math> is the smallest factor &ge; the square-root of ''N''. And so <math>a-b = N/(a+b)</math> is the largest factor &le; root-''N''. If the procedure finds <math>N=1*N</math>, that shows that ''N'' is prime.

For <math>N=cd</math>, let ''c'' be the largest subroot factor. <math>a = (c+d)/2</math>, so the number of steps is approximately <math>(c+d)/2 - \sqrt N = (\sqrt d - \sqrt c)^2 / 2 = (\sqrt N - c)^2 / 2c</math>.