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

14287Re: Modification of PFGW

Expand Messages
  • grostoon
    Dec 29, 2003
    • 0 Attachment
      Hi all,

      I agree with you that for huge N, computing b^((N-1)/2)%N instead of
      b^(N-1)%N result in a negligible time gain.

      But what if you consider the accuracy of the test itself rather than
      the time it takes : why just doing a basic fermat prp test ?
      Maybe I'm missing something but I believed that a strong probable
      prime test (rabin-miller's prp test) was more accurate than the
      simple fermat's test (and not much difficult to implement). Am I
      wrong ?

      Jean-Louis.


      --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:
      > In a message dated 23/12/03 22:00:27 GMT Standard Time,
      cemmanu@y...
      > writes:
      >
      >
      > > I've been asking of Chris Nash ( I presume that he is very busy)
      to modify
      > > PFGW to check for Carol/Kynea numbers for a while now....Can
      anyone modify
      > > PFGW to do b^((N-1)/2)%N rather than b^(N-1)%N? There is even a
      faster way (I
      > > think) I can let it calculate b^((N-1)/2)%N (with a basic for
      loop)....
      > >
      >
      >
      > You do realize, do you, that for N = 2^1000000-1 (for example), "to
      do
      > b^((N-1)/2)%N rather than b^(N-1)%N" takes 999999 rather than
      1000000 FFTs; in other
      > words, there is a negligible difference in execution time.
      >
      > PFGW is already a highly optimized and efficient program; so if you
      think
      > simple ideas involving "a basic for loop" are going to make it
      faster, you are
      > probably mistaken.
      >
      > The proper forum for this discussion is really the primeform group,
      or, for
      > implementation issues, openpfgw.
      >
      > -Mike Oakes
      >
      >
      > [Non-text portions of this message have been removed]
    • Show all 19 messages in this topic