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

Topic: Prime factorization
Replies: 17   Last Post: Nov 16, 2013 9:40 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,416
Registered: 2/12/07
Re: Prime factorization
Posted: Nov 12, 2013 12:28 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Tuesday, November 12, 2013 11:41:58 AM UTC-5, scattered wrote:
> On Tuesday, November 12, 2013 9:38:32 AM UTC-5, Pubkeybreaker wrote: In context, it seems that he meant something akin to "effective" (one of the standard synonyms of the word "efficient") in which case he is 100% correct in his assessment, especially given his qualifier ("of that size").

But it is NOT effective. Why do you think that state-of-the-art factoring
algorithms abandoned it quite a while ago as a subroutine? A combination
of SQUFOF/ECM/MPQS is **far** faster when the ability to split numbers in (say)
the 50 to 100 bit range is time critical. (Such as when used as a subroutine
for NFS).

And yes, trivially the time complexity for numbers of fixed size is O(1).
But the implied constants for Rho are much higher than for other algorithms.




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.