Modular exponentiation

For any inquisitive minds, the fast Modular exponentiation used in the last post (Scala example) might at first glance seem odd, perhaps.

What we want to achieve is x = b^n mod m

where b^n is performed first, the result in then operated on by mod m. Mathematically this is what we are doing, this is what we want to achieve.

However, the expmod function computes the value recursively, applying mod at each step of recursion (on each recursion result).

This is in fact a better way to approach the problem, as the intermediate values are kept small (between 0 and m-1) rather than growing exponentially (with potential overflow/performance problems), only to be operated on by modulus to shrink the value back down again!

Here is a simple Scala snippet that compares expMod with fastExp mod m, with some debugging added to show the intermediate values at each stage of recursion.

package test

import java.util.Random;

object ExpTest {

 def main(args : Array[String]) {

   println("fastExpt(4, 7) % 9) = " + fastExpt(4, 7) % 9)
   println("expMod(4, 7, 9) = " + expMod(4, 7, 9))

   println("fastExpt(5, 12) % 6) = " + fastExpt(5, 12) % 6)
   println("expMod(5, 12, 6) = " + expMod(5, 12, 6))
}

 def expMod(base : Int, exp : Int, m : Int) : Int = {

   val res = if (exp == 0)
     1
   else if (even(exp))
     remainder(square(expMod(base, (exp / 2), m)), m)
   else
     remainder(base * expMod(base, exp - 1, m), m)

   println("expMod: b = " + base + ", exp = " + exp + ", m = " + m + ", res = " + res)
   res
 }

 def fastExpt(b : Int,  exp : Int) : Int = {

   val res = if (exp == 0)
     1
   else if (even(exp))
     square(fastExpt(b, exp / 2))
   else
     b * fastExpt(b, exp - 1)

   println("fastExpt: b = " + b + ", exp = " + exp + ", res = " + res)
   res
 }

 def square(n : Int) : Int = {

   n * n
 }

 def even(n : Int) : Boolean = {

   remainder(n, 2) == 0
 }

 def remainder(n : Int, d : Int) : Int = {

     n % d
 }
}

Results are as follows:

fastExpt: b = 4, exp = 0, res = 1
fastExpt: b = 4, exp = 1, res = 4
fastExpt: b = 4, exp = 2, res = 16
fastExpt: b = 4, exp = 3, res = 64
fastExpt: b = 4, exp = 6, res = 4096
fastExpt: b = 4, exp = 7, res = 16384
fastExpt(4, 7) % 9) = 4
expMod: b = 4, exp = 0, m = 9, res = 1
expMod: b = 4, exp = 1, m = 9, res = 4
expMod: b = 4, exp = 2, m = 9, res = 7
expMod: b = 4, exp = 3, m = 9, res = 1
expMod: b = 4, exp = 6, m = 9, res = 1
expMod: b = 4, exp = 7, m = 9, res = 4
expMod(4, 7, 9) = 4
fastExpt: b = 5, exp = 0, res = 1
fastExpt: b = 5, exp = 1, res = 5
fastExpt: b = 5, exp = 2, res = 25
fastExpt: b = 5, exp = 3, res = 125
fastExpt: b = 5, exp = 6, res = 15625
fastExpt: b = 5, exp = 12, res = 244140625
fastExpt(5, 12) % 6) = 1
expMod: b = 5, exp = 0, m = 6, res = 1
expMod: b = 5, exp = 1, m = 6, res = 5
expMod: b = 5, exp = 2, m = 6, res = 1
expMod: b = 5, exp = 3, m = 6, res = 5
expMod: b = 5, exp = 6, m = 6, res = 1
expMod: b = 5, exp = 12, m = 6, res = 1
expMod(5, 12, 6) = 1

Most importantly, the functions yield the same results, but expMod achieves it in a more efficient and scalable way.

Just a small posting, as whilst appearing simple, modular exponentiation underpins much of modern cryptographic methods, and efficient algorithms are important.


.