## Re: [PrimeNumbers] Re: PFGW and PRPing

Expand Messages
• 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/

---------------------------------

To visit your group on the web, go to:

To unsubscribe from this group, send an email to: