Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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)
|
|
|
|
