Chapter 14 – Modular Arithmetic and the Multiplicative Cipher 209 3 is not the modular inverse of 7 mod 26, because (7 * 3) % 26 = 21.
4 is not the modular inverse of 7 mod 26, because (7 * 4) % 26 = 2.
5 is not the modular inverse of 7 mod 26, because (7 * 5) % 26 = 9.
6 is not the modular inverse of 7 mod 26, because (7 * 6) % 26 = 16.
7 is not the modular inverse of 7 mod 26, because (7 * 7) % 26 = 23.
8 is not the modular inverse of 7 mod 26, because (7 * 8) % 26 = 4.
9 is not the modular inverse of 7 mod 26, because (7 * 9) % 26 = 11.
10 is not the modular inverse of 7 mod 26, because (7 * 10) % 26 = 18.
11 is not the modular inverse of 7 mod 26, because (7 * 11) % 26 = 25.
12 is not the modular inverse of 7 mod 26, because (7 * 12) % 26 = 6.
13 is not the modular inverse of 7 mod 26, because (7 * 13) % 26 = 13.
14 is not the modular inverse of 7 mod 26, because (7 * 14) % 26 = 20.
15 is the modular inverse of 7 mod 26, because (7 * 15) % 26 = 1.So the affine cipher decryption key is 15. To decrypt a ciphertext letter, we take that letter’s
number and multiply it by 15, and then mod 26. This will be the number of the original
plaintext’s letter.
Finding Modular Inverses
In order to calculate the modular inverse to get the decryption key, we could take a brute-force
approach and start testing the integer 1, and then 2, and then 3, and so on like we did above. But
this will be very time-consuming for large keys like 8,953,851.
There is an algorithm for finding the modular inverse just like there was for finding the Greatest
Common Divisor. Euclid’s Extended Algorithm can be used to find the modular inverse of a
number:
def findModInverse(a, m):
if gcd(a, m) != 1:
return None # no mod inverse exists if a & m aren't relatively prime
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3 # // is the integer division operator
v1, v2, v3, u1, u2, u3 = (u1 - q v1), (u2 - q v2), (u3 - q * v3),
v1, v2, v3
return u1 % m
You don’t have to understand how Euclid’s Extended Algorithm works in order to make use of it.
We’re just going to have our programs call this function. If you’d like to learn more about how it
works, you can read http://invpy.com/euclid.