Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Looking for O (n^(1/3)) factoring algorithm
Posted:
Jan 18, 2013 6:49 PM


On Jan 18, 4:34 pm, "christian.bau" <christian....@cbau.wanadoo.co.uk> wrote: > Some years ago I found a factoring algorithm on the internet that > worked in O (n^(1/3)) worst case and was reasonably easy to understand > for mere mortals. Invented sometime around 1975. The principle was > using Fermat's algorithm which finds factors of almost equal size > quickly, then extending it to find factors with a ratio p/q for small > p and q, and cleverly arranging things so that every factor is > guaranteed to be found in O (N^(1/3)) (and not finding any factors > proves primality). Lost the paper, and can't remember the name of the > author or any other detail.
Lehman's Algorithm. (Sherman Lehman)



