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 -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/5XRLJZEAXAQJISCSLTZWJBIO6XOMZHJJ/
Code of Conduct: http://python.org/psf/codeofconduct/
