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 ]
Herman Rubin

Posts: 399
Registered: 2/4/10
Re: Prime factorization
Posted: Nov 12, 2013 1:40 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On 2013-11-12, Pubkeybreaker <> wrote:
> On Tuesday, November 12, 2013 8:35:56 AM UTC-5, scattered wrote:


>>> 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 Phone: (765)494-6054 FAX: (765)494-0558

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.