Modular Exponentiation in Rust

And the program to find Power of a number using Modular Arithmetic in Rust Language.

What is Modular Exponentiation

Many times, we have to compute exponents of a given number for various purposes. But it is notable that overflow may occur for large values. Largest number that we can store with numerical data type in rust is 2128, and is 2⁶⁴ in C / C++.

Now, suppose, in some question, we have to find 21000 modulo 1000000007. If we try to first compute 21000 and then find modulo, rust will throw overflow error.

thread 'main' panicked at 'attempt to multiply with overflow', src/iterative.rs:10:9

Problem statement

Given three numbers n, x and p, compute n^x modulo p.

Naive Approach

Simplest solution to this would be to take 1, and multiply it with n, x times, and find modulo p each time. From Modular Multiplication, we already know that

But this will be done in O( x ) or Linear time complexity.

Here's the code for this approach

fn modular_exponent(n:usize , x:usize , p:usize) -> usize{
    // Initialize ans = 1
    let mut ans = 1;

    // Multiply ans with n, x times, ans modulo
    for _ in 0..x {
        ans *= n;
        ans%=p;
    }

    // Return ans
    return ans;
}

With Driver Code

fn modular_exponent(n:usize , x:usize , p:usize) -> usize{
    // Initialize ans = 1
    let mut ans = 1;

    // Multiply ans with n, x times, ans modulo
    for _ in 0..x {
        ans *= n;
        ans%=p;
    }

    // Return ans
    return ans;
}

// Driver Code

use std::io;

fn take_int() -> usize {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

fn main() {
    let n = take_int();
    let x = take_int();
    let p = take_int();

    println!("{}", modular_exponent(n, x, p));
}

Input

2
100000
1000000007

Output

607723520

Time Complexity : O( x )
Space Complexity : O( 1 )

Efficient Divide and Conquer solution

We can find the modular exponentiation in logarithmic time complexity, using Divide and Conqueror approach.

Approach

We know that mathematically,

So, let's suppose we have to find n^x and x = 2.y, so, we can find ( n ² ) ^y .
In y + 1 steps or x/2 + 1 steps

If, on the other hand, x is odd number it is guaranteed that x-1 will be even number, hence, we multiply answer by n, if x is odd, and reduce x by 1.

Algorithm

1. If x <= 0, return 1.
2. If x is 1, return (answer * n) % p
3. If x > 1 and even, change n to n², change x to x/2, and go to step 2
4. If X > 1 and odd, multiply answer by n and store answer modulo p, and reduce x to x-1 and go to step 2.

Program for Modular Exponentiation in Rust

Implementation of above algorithm is written below

fn modular_exponent(mut n:usize ,mut x:usize , p:usize) -> usize{
    // Initialize ans = 1
    let mut ans = 1;

    // x is 0, return 1
    if x<=0 {
        return 1;
    }

    // use loop statement in rust for infinite loop
    loop {
        // Step 2. If x is 1, return (answer * n) % p
        if x==1 {
            return (ans * n) % p;
        }

        // Step 3. If x > 1 and even, change n to n^2, change x to x/2, and go to step 2

        // for checking if x is even, we check the LSB. is 0 or 1
        // Alternatively, we can also check x%2, but this is more efficient
        if x&1==0 {
            n=( n * n ) % p;
            x>>=1; // or x = x/2
            continue;
        }

        // Step 4. If X > 1 and odd, multiply answer by n and store answer modulo p,
        // and reduce x to x-1 and go to step 2.
        else {
            ans = (ans*n) % p;
            x-=1;
        }
    }
}

Input

2
100000
1000000007

Output

607723520

Time Complexity : O( log ₂ x)
Space Complexity : O( 1 )

Conclusion

Modular exponentiation is very frequently used concept in competitive programming for computing the answer. In this article, we made a program for modular exponentiation in rust in logarithmic time complexity instead of linear time complexity using Divide and Conquer approach.

Here is the optimized function for easy access

fn modular_exponent(mut n:usize ,mut x:usize , p:usize) -> usize{
    let mut ans = 1;
    if x<=0 { return 1; }
    loop {
        if x==1 { return (ans * n) % p; }
        if x&1==0 { n=( n * n ) % p; x>>=1;continue; }
        else { ans = (ans*n) % p;x-=1; }
    }
}

Thank You