Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math.independent

Topic: Looking for O (n^(1/3)) factoring algorithm
Replies: 3   Last Post: Jan 19, 2013 9:18 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Pubkeybreaker

Posts: 1,351
Registered: 2/12/07
Re: Looking for O (n^(1/3)) factoring algorithm
Posted: Jan 18, 2013 6:49 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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)




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.