Chapter 14 – Modular Arithmetic and the Multiplicative Cipher 211- 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
The GCD algorithm is described earlier in this chapter. The findModInverse() function
implements an algorithm called Euclid’s Extended Algorithm. How these functions work is
beyond the scope of this book, but you don’t have to know how the code works in order to make
use of it.
From the interactive shell, you can try out these functions after importing the module. Try typing
the following into the interactive shell:
import cryptomath
cryptomath.gcd(24, 32)
8
cryptomath.gcd(37, 41)
1
cryptomath.findModInverse(7, 26)
15
cryptomath.findModInverse(8953851, 26)
17
Practice Exercises, Chapter 14, Set E
Practice exercises can be found at http://invpy.com/hackingpractice14E.
Summary
Since the multiplicative cipher is the same thing as the affine cipher except using Key B of 0 , we
won’t have a separate program for the multiplicative cipher. And since it is just a less secure
version of the affine cipher, you shouldn’t use it anyway. The source code to our affine cipher
program will be presented in the next chapter.
The math presented in this chapter isn’t so hard to understand. Modding with the % operator finds
the “remainder” between two numbers. The Greatest Common Divisor function returns the
largest number that can divide two numbers. If the GCD of two numbers is 1, we say that those
numbers are “relatively prime” to each other. The most useful algorithm to find the GCD of two
numbers is Euclid’s Algorithm.