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.