Content deleted Content added
No edit summary |
|||
Line 32:
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>c=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.
==Fermat's and trial division==
| |||