Notes - Modular Exponentiation

The following are notes from Introduction to Cryptography with Coding Theory.

• We will often be looking at numbers in the form of
•  x^a(mod n)
• suppose we want to compute 2¹²³⁴(mod 789)
• start with 2² ≡ 4(mod 789) repeatedly square the sides
• 2⁴ ≡ 4² ≡ 16
• 2⁸ ≡ 16² ≡ 256
• 2¹⁶ ≡ 256² ≡ 49
• 2³² ≡  34
• 2⁶⁴ ≡  367
• 2¹²⁸ ≡  559
• 2²⁵⁶ ≡  37
• 2⁵¹² ≡  580
• 2¹⁰²⁴ ≡  286
• since 1234 = 1024 + 128 + 64 + 16 + 2
• 2¹²³⁴ ≡ 286 * 559 * 367 * 49 * 4 ≡ 481 (mod 789)
• never had to deal with number larger than 788^2

Back to ToC