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

Re: [PrimeNumbers] PollardP-1(Prime#)

Expand Messages
  • 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 1 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.