The Math Forum

Search All of the Math Forum:

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

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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 ]

Posts: 1,683
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]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.