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

Probable prime test revisited

Expand Messages
  • Kermit Rose
    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
    View Source
    • 0 Attachment
      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.