## Probable prime test revisited

Expand Messages
• If p is prime, there exist an element g such that g**(p-1) = 1 mod p, and for 0
Message 1 of 1 , Feb 4, 2010
If p is prime, there exist an element g such that
g**(p-1) = 1 mod p,
and
for 0 < k < (p-1),
g**k is not = 1 mod p.

g is called a generator mod p.

I don't know the proof of this, but I know it is
a fundamental theorem in number theory.

Theorem 1:

If p is prime, and p = 1 mod 2**s,
then
there are exactly 2**s distinct
values of b**( (p-1)/2**s),
for 0 < b < p.

Proof:

Let g be a generator mod p.
Define d = (p-1)/2**s

Since g is a generator mod p,
g**d, g**(2d), g**(3d), ..... g**((2**s)d)
are all distinct values mod p.

I use this to construct probable prime tests as follows:

If z = 1 mod 2,
and there exist more than two distinct values of
b**((z-1)/2) for b = 1,2,3,.....(z-1),
then z is composite.

If z = 1 mod 4,
and there exist more than four distinct values of
b**((z-1)/4) for b = 1,2,3,....(z-1),
then z is composite.

If z = 1 mod 8,
and there exist more than eight distinct values of
b**((z-1)/8) for b = 1,2,3,....(z-1),
then z is composite.

etc
Your message has been successfully submitted and would be delivered to recipients shortly.