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.

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`

.

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.

King Pinn: I Salute You. I’m driving halfway across the country and this song is on repeat. Rest in Peace Tonderai Makoni. You were awesome.

After a few weeks off I’m back to business. This is just an update post detailing plans for the rest of the year.

At last we finally have the great reveal, our mystery project was implementing RSA encryption in rust.

We build the final piece of our mystery project, a function that computes modular exponentiation. Come on in, we have large numbers.

We build another part of the mystery project by creating a function that calculates the modular multiplicative inverse of a number.