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

Re: [PrimeNumbers] Re: PFGW and PRPing

Expand Messages
  • Cletus Emmanuel
    Jim, I understand that it calculates b^(N-1)%N, does PFGW first set (N-1)= (2^k)*D, where D is odd, to take advantage of calculating b^(N-1)%N or does it go
    Message 1 of 3 , Dec 23, 2003
    • 0 Attachment
      Jim,
      I understand that it calculates b^(N-1)%N, does PFGW first set (N-1)= (2^k)*D, where D is odd, to take advantage of calculating b^(N-1)%N or does it go through one exponent at a time until it reaches (N-1)?

      jim_fougeron <jfoug@...> wrote:
      For checking a prp, pfgw simply computes:

      b^(N-1)%N and checks to see if the result of that is equal to 1.

      If you "try" to perform a prp-11 check on 11 (and tell PFGW to
      NOT perform any trivial factoring at all), then PFGW will claim
      that 11 is composite. This is because 11^10%11 == 0 and the
      ONLY value PFGW is looking for is b^(N-1)%N == 1.

      --- In primenumbers@yahoogroups.com, Cletus Emmanuel <cemmanu@y...>
      wrote:
      > Hi all,
      > When checking for PRP, how does PFGW handle this task? For
      example, if the base and the number to be checked is N=11, does PFGW
      check 2^1 mod 11, 2^2mod 11, 2^3 mod 11, etc. Or does it check 2^2
      mod 11 and 2^5 mod 11. In other words, does it check every single
      exponent from 1 to N-1 or does it check only the prime divisors of N-
      1?
      >
      > ---Cletus
      >
      >
      > ---------------------------------
      > Do you Yahoo!?
      > Free Pop-Up Blocker - Get it now
      >
      > [Non-text portions of this message have been removed]



      Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      The Prime Pages : http://www.primepages.org/





      ---------------------------------
      Yahoo! Groups Links

      To visit your group on the web, go to:
      http://groups.yahoo.com/group/primenumbers/

      To unsubscribe from this group, send an email to:
      primenumbers-unsubscribe@yahoogroups.com

      Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.



      ---------------------------------
      Do you Yahoo!?
      Free Pop-Up Blocker - Get it now

      [Non-text portions of this message have been removed]
    Your message has been successfully submitted and would be delivered to recipients shortly.