9 min read

On the Modular Multiplicative Inverse

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 with x 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 and m 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 for ed ≡ 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:

  1. As previously mentioned, when a modular multiplicative inverse can be found, there are an infinite number of them.

  2. 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 number n that are coprime to n. 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