Loading ...
Sorry, an error occurred while loading the content.

PollardP-1(Prime#)

Expand Messages
  • Roahn Wynar
    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!

      thanks in advance,
      Roahn

      [Non-text portions of this message have been removed]
    • Phil Carmody
      ... 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.