COMPUTING POWERS IN MODULAR ARITHMETIC -- SHORTCUTS


(Note: This was before we learned about a third,
very important shortcut after the second midterm:
Euler's number phi(n) for composite modulus n.)



1) FERMAT'S LITTLE THEOREM  (for prime modulus only)
----------------------------------------------------
a^(p-1) == 1 (mod p)  for any nonzero `a' when `p' is prime.

Thus, if p=29, we can find 3^928374 by taking
 3^928374 ==  3^(28 x 33156  +  6)  (mod 29)
          == (3^28)^33156 x 3^6     (mod 29)
          ==  1^33156 x 3^6         (mod 29)
          ==  3^6                   (mod 29)
          ==  27  x  27             (mod 29)
          == (-2) x (-2)            (mod 29)
          == 4                      (mod 29)




2) "SUCCESSIVE SQUARING"  (for prime OR composite modulus)
----------------------------------------------------------
First, figure out the power-of-2 exponents,
like 3^1, 3^2, 3^4, 3^8, 3^16, 3^32  (mod 48)
This can be done by successive squaring:
  3^1  ==  3                       ==  3  (mod 48)
  3^2  == (3^1)^2  ==  3^2 ==    9 ==  9  (mod 48)
  3^4  == (3^2)^2  ==  9^2 ==   81 == 33  (mod 48)
  3^8  == (3^4)^2  == 33^2 == 1089 == 33  (mod 48)
  3^16 == (3^8)^2  == 33^2 == 1089 == 33  (mod 48)
  3^32 == (3^16)^2 == 33^2 == 1089 == 33  (mod 48).

Next, represent any other exponent as a sum of these
powers of 2.  (You could do this by putting the number
in binary form, if you wanted).
  3^23 == 3^(16 +  4  +  2  +  1)  (mod 48)
       == 3^16 x 3^4 x 3^2 x 3^1   (mod 48)
       ==  33  x  33 x  9  x 3     (mod 48)
       ==     33     x  27         (mod 48)
       == 891                      (mod 48)
  3^23 == 27                       (mod 48)