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

powers mod prime squared

Expand Messages
  • Kermit Rose
    Let p be an odd prime. Let g be a generator mod p**2. Let n = g**m mod p**2. Then n**x mod p**2 = (g**m)**x mod (p**2) = (g**(mx)) mod (p**2) = ( g**(
    Message 1 of 1 , Sep 13, 2009
    • 0 Attachment
      Let p be an odd prime.
      Let g be a generator mod p**2.
      Let n = g**m mod p**2.

      Then

      n**x mod p**2
      = (g**m)**x mod (p**2)
      = (g**(mx)) mod (p**2)
      = ( g**( mod(mx,p*(p-1) ) ) ) mod (p**2)

      Thus, the powers of n mod p**2 is a "cyclic sub-permutation"
      of the powers of g mod p**2.

      The meaning of "cyclic sub-permutation" is clarified by examples.

      Examples for mod 9 and mod 25.

      2 is a generator mod 9

      Powers of 2 mod 9 are 2,4,8,7,5,1.
      powers of 4 mod 9 are 4,7,1,4,7,1.

      The even powers of 2 are the powers of 4.

      I define (4,7,1,4,7,1) to be a cyclic sub-permutation
      of (2,4,8,7,5,1) with index = 2.

      Note that a cyclic sub-permutation is not always strictly
      a permutation.

      That is why I prefix the prefix "sub" to "permutation".

      2 is a generator mod 25.

      powers of 2 mod 25 are
      2,4,8,16,7,14,3,6,12,24,23,21,17,9,18,11,22,19,13,1.

      powers of 3 mod 25 are
      3,9,2,6,18,4,12,11,8,24,22,16,23,19,7,21,13,14,17,1.

      (3,9,2,6,18,4,12,11,8,24,22,16,23,19,7,21,13,14,17,1)
      is an example of a cyclic sub-permutation of
      (2,4,8,16,7,14,3,6,12,24,23,21,17,9,18,11,22,19,13,1)
      with index = 7.

      etc.

      2 ** 1 mod 9 = 2
      2 ** 2 mod 9 = 4
      2 ** 3 mod 9 = 8
      2 ** 4 mod 9 = 7
      2 ** 5 mod 9 = 5
      2 ** 6 mod 9 = 1

      4 ** 1 mod 9 = 4
      4 ** 2 mod 9 = 7
      4 ** 3 mod 9 = 1
      4 ** 4 mod 9 = 4
      4 ** 5 mod 9 = 7
      4 ** 6 mod 9 = 1


      2 ** 1 mod 25 = 2
      2 ** 2 mod 25 = 4
      2 ** 3 mod 25 = 8
      2 ** 4 mod 25 = 16
      2 ** 5 mod 25 = 7
      2 ** 6 mod 25 = 14
      2 ** 7 mod 25 = 3
      2 ** 8 mod 25 = 6
      2 ** 9 mod 25 = 12
      2 ** 10 mod 25 = 24
      2 ** 11 mod 25 = 23
      2 ** 12 mod 25 = 21
      2 ** 13 mod 25 = 17
      2 ** 14 mod 25 = 9
      2 ** 15 mod 25 = 18
      2 ** 16 mod 25 = 11
      2 ** 17 mod 25 = 22
      2 ** 18 mod 25 = 19
      2 ** 19 mod 25 = 13
      2 ** 20 mod 25 = 1

      3 ** 1 mod 25 = 3
      3 ** 2 mod 25 = 9
      3 ** 3 mod 25 = 2
      3 ** 4 mod 25 = 6
      3 ** 5 mod 25 = 18
      3 ** 6 mod 25 = 4
      3 ** 7 mod 25 = 12
      3 ** 8 mod 25 = 11
      3 ** 9 mod 25 = 8
      3 ** 10 mod 25 = 24
      3 ** 11 mod 25 = 22
      3 ** 12 mod 25 = 16
      3 ** 13 mod 25 = 23
      3 ** 14 mod 25 = 19
      3 ** 15 mod 25 = 7
      3 ** 16 mod 25 = 21
      3 ** 17 mod 25 = 13
      3 ** 18 mod 25 = 14
      3 ** 19 mod 25 = 17
      3 ** 20 mod 25 = 1

      4 ** 1 mod 25 = 4
      4 ** 2 mod 25 = 16
      4 ** 3 mod 25 = 14
      4 ** 4 mod 25 = 6
      4 ** 5 mod 25 = 24
      4 ** 6 mod 25 = 21
      4 ** 7 mod 25 = 9
      4 ** 8 mod 25 = 11
      4 ** 9 mod 25 = 19
      4 ** 10 mod 25 = 1
      4 ** 11 mod 25 = 4
      4 ** 12 mod 25 = 16
      4 ** 13 mod 25 = 14
      4 ** 14 mod 25 = 6
      4 ** 15 mod 25 = 24
      4 ** 16 mod 25 = 21
      4 ** 17 mod 25 = 9
      4 ** 18 mod 25 = 11
      4 ** 19 mod 25 = 19
      4 ** 20 mod 25 = 1

      6 ** 1 mod 25 = 6
      6 ** 2 mod 25 = 11
      6 ** 3 mod 25 = 16
      6 ** 4 mod 25 = 21
      6 ** 5 mod 25 = 1
      6 ** 6 mod 25 = 6
      6 ** 7 mod 25 = 11
      6 ** 8 mod 25 = 16
      6 ** 9 mod 25 = 21
      6 ** 10 mod 25 = 1
      6 ** 11 mod 25 = 6
      6 ** 12 mod 25 = 11
      6 ** 13 mod 25 = 16
      6 ** 14 mod 25 = 21
      6 ** 15 mod 25 = 1
      6 ** 16 mod 25 = 6
      6 ** 17 mod 25 = 11
      6 ** 18 mod 25 = 16
      6 ** 19 mod 25 = 21
      6 ** 20 mod 25 = 1

      7 ** 1 mod 25 = 7
      7 ** 2 mod 25 = 24
      7 ** 3 mod 25 = 18
      7 ** 4 mod 25 = 1
      7 ** 5 mod 25 = 7
      7 ** 6 mod 25 = 24
      7 ** 7 mod 25 = 18
      7 ** 8 mod 25 = 1
      7 ** 9 mod 25 = 7
      7 ** 10 mod 25 = 24
      7 ** 11 mod 25 = 18
      7 ** 12 mod 25 = 1
      7 ** 13 mod 25 = 7
      7 ** 14 mod 25 = 24
      7 ** 15 mod 25 = 18
      7 ** 16 mod 25 = 1
      7 ** 17 mod 25 = 7
      7 ** 18 mod 25 = 24
      7 ** 19 mod 25 = 18
      7 ** 20 mod 25 = 1

      8 ** 1 mod 25 = 8
      8 ** 2 mod 25 = 14
      8 ** 3 mod 25 = 12
      8 ** 4 mod 25 = 21
      8 ** 5 mod 25 = 18
      8 ** 6 mod 25 = 19
      8 ** 7 mod 25 = 2
      8 ** 8 mod 25 = 16
      8 ** 9 mod 25 = 3
      8 ** 10 mod 25 = 24
      8 ** 11 mod 25 = 17
      8 ** 12 mod 25 = 11
      8 ** 13 mod 25 = 13
      8 ** 14 mod 25 = 4
      8 ** 15 mod 25 = 7
      8 ** 16 mod 25 = 6
      8 ** 17 mod 25 = 23
      8 ** 18 mod 25 = 9
      8 ** 19 mod 25 = 22
      8 ** 20 mod 25 = 1

      9 ** 1 mod 25 = 9
      9 ** 2 mod 25 = 6
      9 ** 3 mod 25 = 4
      9 ** 4 mod 25 = 11
      9 ** 5 mod 25 = 24
      9 ** 6 mod 25 = 16
      9 ** 7 mod 25 = 19
      9 ** 8 mod 25 = 21
      9 ** 9 mod 25 = 14
      9 ** 10 mod 25 = 1
      9 ** 11 mod 25 = 9
      9 ** 12 mod 25 = 6
      9 ** 13 mod 25 = 4
      9 ** 14 mod 25 = 11
      9 ** 15 mod 25 = 24
      9 ** 16 mod 25 = 16
      9 ** 17 mod 25 = 19
      9 ** 18 mod 25 = 21
      9 ** 19 mod 25 = 14
      9 ** 20 mod 25 = 1

      11 ** 1 mod 25 = 11
      11 ** 2 mod 25 = 21
      11 ** 3 mod 25 = 6
      11 ** 4 mod 25 = 16
      11 ** 5 mod 25 = 1
      11 ** 6 mod 25 = 11
      11 ** 7 mod 25 = 21
      11 ** 8 mod 25 = 6
      11 ** 9 mod 25 = 16
      11 ** 10 mod 25 = 1
      11 ** 11 mod 25 = 11
      11 ** 12 mod 25 = 21
      11 ** 13 mod 25 = 6
      11 ** 14 mod 25 = 16
      11 ** 15 mod 25 = 1
      11 ** 16 mod 25 = 11
      11 ** 17 mod 25 = 21
      11 ** 18 mod 25 = 6
      11 ** 19 mod 25 = 16
      11 ** 20 mod 25 = 1

      12 ** 1 mod 25 = 12
      12 ** 2 mod 25 = 19
      12 ** 3 mod 25 = 3
      12 ** 4 mod 25 = 11
      12 ** 5 mod 25 = 7
      12 ** 6 mod 25 = 9
      12 ** 7 mod 25 = 8
      12 ** 8 mod 25 = 21
      12 ** 9 mod 25 = 2
      12 ** 10 mod 25 = 24
      12 ** 11 mod 25 = 13
      12 ** 12 mod 25 = 6
      12 ** 13 mod 25 = 22
      12 ** 14 mod 25 = 14
      12 ** 15 mod 25 = 18
      12 ** 16 mod 25 = 16
      12 ** 17 mod 25 = 17
      12 ** 18 mod 25 = 4
      12 ** 19 mod 25 = 23
      12 ** 20 mod 25 = 1
    Your message has been successfully submitted and would be delivered to recipients shortly.