Friday, September 20, 2013

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
    •  xa(mod n)
  • suppose we want to compute 21234(mod 789)
    • start with 22 ≡ 4(mod 789) repeatedly square the sides
    • 2≡ 42 ≡ 16
    • 2≡ 162 ≡ 256
    • 216 ≡ 2562 ≡ 49
    • 232 ≡  34
    • 264 ≡  367
    • 2128 ≡  559
    • 2256 ≡  37
    • 2512 ≡  580
    • 21024 ≡  286
  • since 1234 = 1024 + 128 + 64 + 16 + 2
    • 21234 ≡ 286 * 559 * 367 * 49 * 4 ≡ 481 (mod 789)
    • never had to deal with number larger than 788^2

No comments:

Post a Comment