Comfortably Coding Blog of Mathew Rodley

 

Today someone asked me if I knew of a large number class in C++. Specifically they wanted to be able to hold the value 5⁵⁸ in a variable. I was suspicious of why they would want to do this and asked what their ultimate goal was. It turned out they wanted to calculate n^x mod p for arbitrary values of n,x and p, their ultimate goal being an implementation of Diffie Hellman key exchange.

 

Now, Calculating n^x then taking the modulus p of it is a valid way of solving the problem, but it has a few nagging problems. The first is that you must be able to handle large numbers in whatever environment you are doing these calculations in, and the second is that you must be able to calculate these large numbers and take them modulo some value. To begin with, I remembered back to my early days at University when we covered something called Modular Arithmetic. Consider this example:

 

We have a clock face which has 12 hours on it and we want to find where the clock hand will be pointing to in 7 hours (If we are already at 12 o'clock). Easy, it will be pointing to 7. Now extending this, where will it be pointing in 14 hours? Well the answer is 14 mod 12 or 2.

 

Further extending this, if we want to know where the hand will be in 2 * 14 hours = 28 hours we can do 28mod12 = 4 or (2mod12 * 14)mod12 = 4.

 

Now, what if we want to know 14⁴ mod 12? Well we know 14⁴ is 14 * 14 * 14 * 14 so we can apply what we have just realised above and

14⁴mod12 = ((((14mod12) * 14)mod12 * 14)mod12 * 14)mod12

 

And we can do the same with 5⁵⁸ mod 97 and we can do all this without requiring a large exponent and modular operation.

A quick implementation in Ruby

 

Taking what we have learn, we know that we can now efficiently calculate a modular exponentiation without using large numbers. Implementing this in Ruby works as follows:

 

>> def modpow(base, pow, mod)

>> (1..pow).inject(1) { |mult,x| (mult * base) % mod }

>> end

 

(1..pow) is shorthand for creating a Range object (Range.new(1, pow)) and it represents the set of whole integers between 1 and pow as an enumerable object. Please note, it does not create an array of numbers [1,2,3,...,10].

 

inject is a method which can be called on an enumerable object which is similar to reduce. Here is how it works for summing a collection:

 

[1,2,3,4,5].inject(0) { | a, b| a + b }

 

inject() operates over the collection and we pass the block a + b into it, which take two parameters a and b. a is the value last returned by the last call to the block and b is the current value we are enumerating over. In this example, the first call to block provided to inject will yield a = 0 and b = 1. it will return a + b = 1.

The second call will then yield a = 1 and b = 2 and will return a + b = 3 and so on.

This gives us a mechanism to iterate over everything in a collection and reduce the result to one variable, in this case it will be the sum of all integers in the collection.

 

Looking back at our original code, our block { (mult * base) % mod } will be called pow times by the inject function, and mult will be the result of all previous calls. This is exactly what we want so that line of code effectively does

(((((1*5)%97)*5)%97)*5)%97 ... 55 more times.