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.

.

## 1 comment:

data entry india applications let you recognize forms filled in by hand in order to automate data entry tasks. Handprint recognition has come a long way in the past few years. Cost and complexity have gone down while accuracy gets increasingly higher. This has finally made this technology available to small and mid-sized businesses.

Post a Comment