
Re: Prime factorization
Posted:
Nov 12, 2013 1:40 PM


On 20131112, Pubkeybreaker <pubkeybreaker@aol.com> wrote: > On Tuesday, November 12, 2013 8:35:56 AM UTC5, scattered wrote:
><snip>
>>> You seem to need some valium or something. To say that a method is efficient isn't to say that it is the most efficient method in existence. I wrote an inefficient Python implementation of Pollard's rho when I first read about it a few years ago (idle curiosity on my part, this isn't my area of expertise). I just tried it on 130642890110987 and the factorization appeared on my screen even before my pinky left the enter key (even though Python is a "slow" interpreted language). That is "almost instantly" in any reasonable interpretation of that phrase.
> You have a strange notion of the word "efficient". The topic of discussion > is computer implementation of factoring methods. In that domain human > perception of "almost instantly" is meaningless. What does have meaning is > how well the method performs when called as a subroutine. By any reasonable > interpretation of the word "efficient", an exponential time algorithm is > NOT efficient. Indeed, even from a theoretical computer science point of view > exponential time algorithms are NOT efficient.
I know this argument, but one can often raise the question of how large a problem has to be for an asymptotically more efficient algorithm becomes better. If an exponential time procedure beats a polynomial time algorithm for factoring numbers of length less than 10^100, which is more efficient?
>>There is no reason to adopt a scolding tone againt somebody who make the true albeit unnuanced claim that Pollard's rho can efficiently factor numbers of that size.
> This NG has become overwhelmed with cranks, spammers, and nonsense. When I > see someone who is ignorant of a subject make an ignorant and erroneous claim, > I respond.
> To claim that Pollard Rho is efficient is wrong. It is not.
 This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)4946054 FAX: (765)4940558

