
Oct. 4, 2019
9:37 a.m.
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