Wikipedia defines a modular multiplicative inverse as an integer x such that the product ax is congruent to 1 with respect to the modulus m.

That’s a lot of long words, we naught but humble pirates. So let’s try to break it down to a more straightforward definition.

Inverse

To understand it better I find it useful to define what a normal inverse is. In mathematics, an inverse of a number x is the number which if we multiply it to x we get 1.

So here 1/x is the inverse of x.

Modular multiplicative inverse is a similar idea. It is the value of x with which if we divide the product ax by the modulus m we get 1. There are a number of good resources that go into more detail if you’re interested in the topic so I won’t go further here.

Our task today is to calculate the modular multiplicative inverse of a given number a on modulus n.

Solution

To calculate it we will be using the extended euclidean algorithm. If this sounds familiar that’s because it is. We used its cousin, the euclidean algorithm before to calculate the greatest common divisor. The code for the function looks like this:

pub fn inverse(a: i64, n: i64) -> i64 {
    let (mut t, mut new_t, mut r, mut new_r) = (0, 1, n, a);

    loop {
        if new_r == 0 {
            if r > 1 {
                panic!("a is not invertible");
            }
            if t < 0 {
                t = t + n;
            }
            return t;
        }
        let quotient = r / new_r;
        (t, new_t) = (new_t, t - quotient * new_t);
        (r, new_r) = (new_r, r - quotient * new_r);
    }
}

Code language: Rust (rust)

This is easily the more complicated function we will need to write for the mystery project so if it’s not clicking feel free to take your time and read up on it. Or you can message me on Twitter @phoexer and we can talk about it. Happy Coding.