# 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 264 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 nx 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

(a x b) mod m = ((a mod m) x (b mod m)) mod m

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,

na.b = (na ) b

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

n2.y = (n2 ) y
Hence, we multiply n by itself, if x is even.

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 n2, 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 2 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