Fermat's factorization method: Difference between revisions

Revision as of 09:55, 24 October 2021

Revision as of 13:37, 18 February 2022

Line 46:

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>.

If ''N'' is prime (so that <math>dc = 1</math>), one needs <math>O(N)</math> steps. This is a bad way to prove primality. But if ''N'' has a factor close to its square root, the method works quickly. More precisely, if ''c'' differs less than <math>{\left(4N\right)}^{1/4}</math> from <math>\sqrt N</math>, the method requires only one step; this is independent of the size of ''N''.{{Citation needed|date=January 2015}}

==Fermat's and trial division==