Search All of the Math Forum:

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

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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Herman Rubin Posts: 399 Registered: 2/4/10
Re: Prime factorization
Posted: Nov 12, 2013 1:40 PM
 Plain Text Reply

On 2013-11-12, Pubkeybreaker <pubkeybreaker@aol.com> wrote:
> On Tuesday, November 12, 2013 8:35:56 AM UTC-5, 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)494-6054 FAX: (765)494-0558

Date Subject Author
11/4/13 me
11/4/13 Ben Bacarisse
11/4/13 Michael F. Stemper
11/11/13 Kermit Rose
11/12/13 Pubkeybreaker
11/12/13 scattered
11/12/13 Pubkeybreaker
11/12/13 scattered
11/12/13 Pubkeybreaker
11/12/13 Herman Rubin
11/12/13 Pubkeybreaker
11/12/13 David Bernier
11/12/13 Pubkeybreaker
11/16/13 Michael F. Stemper
11/4/13 scattered
11/4/13 me
11/4/13 me
11/5/13 scattered

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