Today we look at the final component of the mystery project, modular exponentiation. Before today we build a function to check primality, calculate the modular multiplicative inverse and calculate the lowest common multiple of two numbers. The more perceptive of you will no doubt already know what we’re building.

In mathematics, an exponent refers to the number of times a number is multiplied by itself, for example, 3².

A Modulo operation returns the remainder of a division. For example 3 / 2 = 1.5 and 3 mod 2 = 1.

For small numbers, you can calculate these pretty easily. But what happens when you have large numbers? Imagine you have 2046413mod 300. This stops being easy because the exponent results in very large numbers. So our task is to calculate modulo equations with exponentials that do not melt our ram.

Efficient Modular exponentiation

In mathematics, we have an identity that relates to modulo equations.

(a⋅b) mod m = [(a mod m)⋅(b mod m)] mod m

This identity means that we can break down our exponent into several modulo operations. e.g. for 33 mod 5 can bebroken down into.

[3 mod 5 * 3 mod 5 * 3 mod 5] mod 5Code language: CSS (css)

Notice anything? We can iterate the above trivially and that will reduce our memory footprint and speed up our calculation. The final code looks like this;

pub fn mod_exp(x: i64, n: i64, p: i64) -> i64{
    let mut ans: i64 = 1;
    let mut x: i64 = x % p;
    let mut n = n;
    while n > 0 {
        if n & 1 > 0 {
            ans = (ans * x) % p;
        }
        x = x.pow(2) % p;
        n = n >> 1;
    }
    ans
}
Code language: Rust (rust)

Honestly, I think I can clean up this code a little more but this is fine for now. We now have the last part of our project. Next time we will be putting it all together and finishing our mystery project. This is the last chance to guess what I’m building. If you have any guesses as to what involves prime numbers, modular multiplicative inverse, lowest common multiples, and modular exponentiation let me know on Twitter, @phoexer, and as always happy coding.