--- Roahn Wynar <rwynar@...
> Sorry about the lame questions, but I am not clear on a point that should be
> 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.
() 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