Historical gloss: Lehman surprisingly transformed Fermat's O(n) method
into an O(cube_root(n)) method. I believe that was the first deterministic
factoring method known beating trial division's O(sqrt(n)) time. Alas for
Lehman, Pollard very soon after published his rho method, which runs in
probabilistic O(sqrt(p)) time where p is n's smallest prime factor, so in
worst-case probabilistic O(fourth_root(n)) time.
https://mobileappdevelopmentcompanyindia.co
_______________________________________________
Python-ideas mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/[email protected]/message/5XRLJZEAXAQJISCSLTZWJBIO6XOMZHJJ/
Code of Conduct: http://python.org/psf/codeofconduct/
