In my last post, I detailed how you can use the extended Euclidean algorithm to not only determine the greatest common divisor of two numbers but also to determine Bézout’s coefficients. This is crucial in determining the modular multiplicative inverse of a number and has practical applications in cryptosystems such as RSA. Let’s dig in.
I’m not going to describe either the Euclidean algorithm or the extended Euclidean algorithm again, so please refer to my last post for a refresher.
The Modular Multiplicative Inverse
First, let’s define the multiplicative inverse:
-
A multiplicative inverse or reciprocal is a number
x-1
such that when multiplied withx
yields the multiplicative identity, the number 1. -
More formally, in group theory, one axiom of a group is invertibility that says there is an element that can undo the effect of combination with another given element. The result is the identity element.
The identity element for multiplication is 1. xx-1 = 1 x-1x = 1 x = 5 1 = 5 * 1/5 = 5 * .2 = 1 --- x = .125 1 = .125 * 1/.125 = .125 * 8 = 1
The identity element is a member of a set that helps to satisfy another condition of a group!
Easy peasy.
Now, let’s look the modular multiplicative inverse. Again, this is an operation that will also result in 1, the difference being that it is congruent to, not equal to, 1. This is important and implies that there is more than one result that can be a modular multiplicative inverse.
a ≡ x-1 mod m ⇔ ax ≡ 1 mod m
So, in the above notation, the number x
is a multiplicative inverse of the number a
if the product ax
is congruent to 1, modulus m
.
There can only be a modular multiplicative inverse if both
a
andm
are coprime.Recall that another way to say that two numbers are coprime or relatively prime is that their greatest common divisor is 1.
gcd(a, m)
= 1
Example
Let’s look at an example of “brute forcing” by trying a range of numbers sequentially from 1 < m
(we don’t try m
since m % m == 0
, i.e., it is the same as 0):
a = 5 m = 17 5 ≡ d-1 mod 17 5d ≡ 1 mod 17 # Again, we're only trying numbers # less than the modulus! # # 5d ≡ 1 mod 17 # # We'll use our workhorse `bc`. $ for d in {1..16} > do > bc <<< 5*$d%17 > done 5 10 15 3 8 13 1 <--- Bingo! 6 11 16 4 9 14 2 7 12 In this case, d = 7. Let's verify that. 5(7) ≡ 1 mod 17 35 ≡ 1 mod 17 35 mod 17 ≡ 1 1 ≡ 1 So, 7 is the modular multiplicative inverse of 5!
Did you notice anything interesting about the results of that loop? All of the numbers are represented in the range 1 <
m
! Neat!
One thing that’s very important to note is that modulus operations will have an infinite number of multiplicative inverses. This is because of the nature of modular arithmetic: when reaching a certain value, i.e., the modulus, the numbers will “wrap around”.
For example, think of the 12-hour clock as having the modulus 12. So 1, 13, 25, 37, etc. are all values congruent to 1.
Let’s see what happens when we raise the upper bound of our range to be greater than the modulus.
We’ll use the helper program [priv_key.c], and we’ll use it like this:
Usage: priv_key <e> <mod> <bound> e = The integer for which we're looking for the multiplicative inverse. mod = The modulus. bound = The number of times to loop. Defaults to the modulus.
Remember, we’re solving
d
fored ≡ 1 mod m
First, let’s calculate the previous result using our new tool so we can compare the result.
Here, we’re looking for a number that when multiplied by 5 is congruent with 1 modulus 17. We’ll try numbers 1 - 16, inclusive.
$ priv_key 5 17 16
7
Let’s increase the bound to 100 (trying numbers 1 - 100):
$ priv_key 5 17 100
7 24 41 58 75 92
And 500 (trying numbers 1 - 500):
$ priv_key 5 17 500
7 24 41 58 75 92 109 126 143 160 177 194 211 228 245 262 279 296 313 330 347 364 381 398 415 432 449 466 483 500
This demonstrates a couple of things:
-
As previously mentioned, when a modular multiplicative inverse can be found, there are an infinite number of them.
-
All of the inverses are 17 greater than the previous one, which is the value of the modulus! The numbers wrap around just like the 12-hour clock! All of the numbers
mod 17
above are in the same congruence class.
Keep in mind that for numbers that are tens or hundreds of digits long that it is impractical to use a brute-force approach to finding the inverse like the
priv_key
does. In these case, the extended Euclidean algorithm is the way to go.
Computation
We’ll now look at two ways to compute the modular multiplicative inverse:
- the extended Euclidean algorithm
- Euler’s theorem
We’ll work with the same values for both algorithms:
a = 17, m = 37
The Extended Euclidean Algorithm
The following should look familiar from what we’ve already covered. I’ve also written about it previously.
ax + my = gcd(a, m) = 1 ⇔ ax - 1 = (-y)m ⇔ ax ≡ 1 mod m
You’ll also see this as part of the RSA algorithm to determine the private key
d
in the key generation step:d ≡ e-1 mod n ⇔ de ≡ 1 mod n
Example
gcd(17, 37) a = 37, b = 17 Step 1: n = 37 d = 17 q = 2 r = n % d = 3 3 = 37 - 17(2) 3 = a - 2b Step 2: Is r > 1? Yes. Step 1: n = 17 d = 3 q = 5 r = n % d = 2 2 = 17 - 3(5) 2 = b - 5(a - 2b) 2 = b - 5a + 10b 2 = -5a + 11b Step 2: Is r > 1? Yes. Step 1: n = 3 d = 2 q = 1 r = n % d = 1 1 = 3 - 2(1) 1 = a - 2b - 1(-5a + 11b) 1 = a - 2b + 5a - 11b 1 = 6a - 13b Step 2: Is r > 1? No! Step 3: 1 = 6a - 13b 1 = 6(37) - 13(17) 1 = 222 - 221 1 = 1 So, we've learned the gcd is 1 (but we knew that already since both numbers were prime and that is the prerequisite for computing the modular multiplicative inverse!). The coefficients are 6 and -13, respectively (recall that one of the numbers will always be negative). gcd(17, 37) = 6a + -13m Finally, let's determine the inverse. This is the easy part; simply subtract the Bézout's coefficient that we computed from the modulus: 37 - 13 = 24 Let's verify: 17(24) ≡ 1 mod 37 408 ≡ 1 mod 37 1 ≡ 1 mod 37
Why can we subtract one of the Bézout’s coefficients from the modulus to get the inverse? Recall that any two numbers whose difference equals the modulus are congruent to each other:
58 ≡ 1 mod 57 -27 ≡ 30 mod 57 And again, from the example above: -13 ≡ 24 mod 37 We subtract from the modulus, since we want the inverse to be an element of the group, that is, within the range 1 < m.
Euler’s Theorem
Euler’s theorem, as I’ve covered previously, states that when a
and n
are coprime that:
aϕ(m) ≡ 1 mod m
Now, let’s rewrite it so we’re solving for the inverse of a
, a-1:
aϕ(m) ≡ 1 mod m ⇔ aϕ(m)-1 ≡ a-1 mod m
Example
So, plugging in our values, we’re now solving for:
17ϕ(37)-1 ≡ a-1 mod 37
We’ll solve this by reducing the terms every chance we get. Let’s go!
1735 mod 37 ≡ 17 * 1734 ≡ 17 * 28917 ≡ 17 * 3017 ≡ 17 * 30 * 3016 ≡ 17 * 30 * -716 ≡ 17 * 30 * 716 ≡ 17 * 30 * 498 ≡ 17 * 30 * 128 ≡ 17 * 30 * 1444 ≡ 17 * 30 * -44 ≡ 17 * 30 * 44 ≡ 17 * 30 * 162 ≡ 17 * 30 * 256 ≡ 17 * 30 * 34 ≡ 24 Cool, it's the same value we got from using the extended Euclidean algorithm! Let's verify: 24ϕ(37) ≡ 1 mod 37 2436 ≡ 1 mod 37 1 ≡ 1 mod 37 If this feels unfamiliar or awkward, consult the links in the `References` section and brush up on your modular arithmetic.
Drawbacks to Euler’s Theorem
-
It may be impractical, however, to find the inverse using Euler’s theorem if the modular isn’t prime and is very large. To illustrate, can you compute the following?:
ϕ(25777777)
That number, by the way, is well over a million digits long! Have fun!
-
It is usually easier to compute the inverse using the extended Euclidean algorithm.
Recall Euler’s totient function, also known as the
phi
function, counts the number of integers up to some numbern
that are coprime ton
. It is symbolized by eitherφ
or ϕ.Also, recall that neither number has to be prime, although it is easier to calculate if the modulus is prime, i.e.:
ϕ(p) = p - 1 p = 17 ϕ(17) = 16
Just For Fun a = 9 m = 17 ϕ(a) = 6 ϕ(m) = 16 ϕ(am) = ϕ(a)ϕ(m)
Conclusion
I’ve found the modular multiplicative inverse to be a difficult topic to write about. It is necessary to at least understand the fundamentals of many different aspects of mathematics; namely, number theory, group theory, modular arithmetic and modular exponentiation.
As an autodidact, it took me a tremendous amount of time to wade through the copious amounts of information on each subject, and then loads more time in trying to arrange the narrative into something cohesive. Hopefully, the reader will bear this in mind if they are unnecessarily confused and/or find mistakes, and I welcome any and all corrections and suggestions.
References
- https://www.di-mgt.com.au/multiplicative-group-mod-p.html
- https://www.quora.com/How-do-I-calculate-8-%E2%80%931-mod-77-using-Eulers-Theorem/
- https://math.stackexchange.com/questions/747342/extended-euclidean-algorithm-for-modular-inverse/
- https://math.stackexchange.com/questions/1307082/use-eulers-theorem-to-find-the-inverse-of-17-modulo-31-in-the-range-1-30/
- https://www.di-mgt.com.au/rsa_alg.html