## PollardP-1(Prime#)

Expand Messages
• Sorry about the lame questions, but I am not clear on a point that should be obvious.... My implementation of the Pollard p-1 algorithm seems to work pretty
Message 1 of 2 , Sep 10, 2006
• 0 Attachment
Sorry about the lame questions, but I am not clear on a point that should be obvious....

My implementation of the Pollard p-1 algorithm seems to work pretty well except when it is given a prime number to chew on. I claim to understand the theory of the algorithm, but I can't quite see how it can recognize a prime number if it attempts to factor one....

Could anyone help me understand how the Pollard p-1 factoring algorithm terminates if the algorithm is given a prime number to start with? My implementation seems to just keep on going!

Roahn

[Non-text portions of this message have been removed]
• ... It searches for factors. For an arbitrary prime it will take an excessively long time, as the only factor is the entire number. It s just doing what it
Message 2 of 2 , Sep 10, 2006
• 0 Attachment
--- Roahn Wynar <rwynar@...> wrote:
> Sorry about the lame questions, but I am not clear on a point that should be
> obvious....
>
> My implementation of the Pollard p-1 algorithm seems to work pretty well
> except when it is given a prime number to chew on. I claim to understand the
> theory of the algorithm, but I can't quite see how it can recognize a prime
> number if it attempts to factor one....
>
> Could anyone help me understand how the Pollard p-1 factoring algorithm
> terminates if the algorithm is given a prime number to start with? My
> implementation seems to just keep on going!

It searches for factors. For an arbitrary prime it will take an excessively
long time, as the only factor is the entire number. It's just doing what it
says on the tin. If you want to detect the case where p is prime, which you do,
perform a PRP test on it first.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
Your message has been successfully submitted and would be delivered to recipients shortly.