In this tutorial, we'll have a peek into the inner workings of the Ruby interpreter and we'll build a fully functional C extension to Ruby to perform modular exponentiation on big integers.
Modular exponentiation is a kind of exponentiation performed over a modulus. Easy, right?. Ok, lets better see an example:
Regular exponentiation is something like this:
5^3 = 5*5*5 = 125
Modular exponentiation is the same, but after performing the exponentiation you take the result modulo some other number:
5^3 mod 17 = 125 mod 17 = 6
Modular exponentiation is interesting because some of its properties make it perfect to use in cryptography.
Regular exponentiation is a two way function: if I say to you that I chose a number, raised this number to three and got 125, it's easy for you to find out this number is 5. This is what we call a logarithm:
x^3 = 125 => x = log3 125 = 5
After all, regular exponentiation a is monotonically increasing function, that's it: the bigger I make x the bigger will be the result. If I know x^3 = 125, I can try with some values for x and eventually I'll find the right value:
10^3 = 1000 => so x must be less than 10 2^3 = 8 => so x must be greater that 2 6^3 = 216 => so x must be less than 5
For modular exponentiation that question is not so easy because modular exponentiation is not a monotonically increasing function.
7^3 mod 17 = 3 8^3 mod 17 = 2 9^3 mod 17 = 15 10^3 mod 17 = 14
Let's say I want to know which number raised to three modulo 17 yield to six. Even if I know 7^3 mod 17 is 3, I don't know if 8^3 mod 17 will be more or less than 3 until I calculate it. In fact, the correct answer if 5:
ruby-1.9.2-p0 > 0.upto(17).collect { |i| i**3 %17 }
=> [0, 1, 8, 10, 13, 6, 12, 3, 2, 15, 14, 5, 11, 4, 7, 9, 16, 0]
A modulus of 17 is a small enough so we can calculate all the possible outcomes of x^3 mod 17, from 0 to 17 and find which one yields to 6. But if the modulus is large enough (let's say, something of the order of 2^124), we won't be able to do that. There are too many possibilities, even for the best computers in the world.
Modular exponentiation is a good function for cryptography because it is very difficult to reverse. This is a far advanced topic, but if you are interested you can read, for example, about the ElGamal cryptosystem.
So, how can we implement modular exponentiation in Ruby?
First, we need to understand that Ruby uses two kind of integers: Fixnum and Bignum. Fixnum can represent integers in binary form using the same machine internal representation, except one bit that it is used to mark it internally as an integer instead of a regular object.
My machine, for instance, has a 64 bit processor, so Fixnum uses one bit to mark the object as a Fixnum: one to store the sign and the other 62 to store the integer absolute value.
The Ruby interpreter shows clearly that the class of an integer is different wether the number is bigger or not than 2^62:
ruby-1.9.2-p0 > 2**62 -1 => 4611686018427387903 ruby-1.9.2-p0 > (2**62 -1 ).class => Fixnum ruby-1.9.2-p0 > (2**62).class => Bignum
So in my machine, 4611686018427387903, is the biggest Fixnum that Ruby can store. When a Fixnum grows beyond this number, it becomes a Bignum.
Bignums, on the other hand it is an arbitrary precision integer that theoretically could be as large as we want.
With this background in mind, let's try to do some modular exponentiation with big numbers in ruby:
ruby-1.9.2-p0 > 8392498274982739487923749879872 ** 43 % 1928739128739 => 170770405706 ruby-1.9.2-p0 > 8392498274982739487923749879872 ** 431 % 1928739128739 => 1077860096306 ruby-1.9.2-p0 > 8392498274982739487923749879872 ** 43156 % 1928739128739 => 1529021204077 ruby-1.9.2-p0 > 8392498274982739487923749879872 ** 43156567 % 1928739128739 (irb):12: warning: in a**b, b may be too big => NaN ruby-1.9.2-p0 > 8392498274982739487923749879872 ** 43156567 (irb):14: warning: in a**b, b may be too big => Infinity
It seems that Ruby simply give up when we try to exponentiate big enough numbers. But, what's happening? Didn't we say that a Bignum can store arbitrary long integers? And if Ruby can't exponentiate big enough numbers, what's the limit in which we no longer can exponentiate numbers? There is not much information in the official documentation so we need to peek the most authoritative source about Ruby: the Ruby source code itself.
So, after downloading and decompressing the ruby 1.9 source code all we see is a bunch of c source files. Where do we start? bignum.c seems a good candidate. Grepping for pow we soon find the function we were looking for:
/*
* call-seq:
* big ** exponent -> numeric
*
* Raises _big_ to the _exponent_ power (which may be an integer, float,
* or anything that will coerce to a number). The result may be
* a Fixnum, Bignum, or Float
*
* 123456789 ** 2 #=> 15241578750190521
* 123456789 ** 1.2 #=> 5126464716.09932
* 123456789 ** -2 #=> 6.5610001194102e-17
*/
VALUE
rb_big_pow(VALUE x, VALUE y)
{
double d;
SIGNED_VALUE yy;
if (y == INT2FIX(0)) return INT2FIX(1);
switch (TYPE(y)) {
case T_FLOAT:
d = RFLOAT_VALUE(y);
if ((!RBIGNUM_SIGN(x) && !BIGZEROP(x)) && d != round(d))
return rb_funcall(rb_complex_raw1(x), rb_intern("**"), 1, y);
break;
case T_BIGNUM:
rb_warn("in a**b, b may be too big");
d = rb_big2dbl(y);
break;
case T_FIXNUM:
yy = FIX2LONG(y);
if (yy < 0)
return rb_funcall(rb_rational_raw1(x), rb_intern("**"), 1, y);
else {
VALUE z = 0;
SIGNED_VALUE mask;
const long BIGLEN_LIMIT = 1024*1024 / SIZEOF_BDIGITS;
if ((RBIGNUM_LEN(x) > BIGLEN_LIMIT) ||
(RBIGNUM_LEN(x) > BIGLEN_LIMIT / yy)) {
rb_warn("in a**b, b may be too big");
d = (double)yy;
break;
}
for (mask = FIXNUM_MAX + 1; mask; mask >>= 1) {
if (z) z = bigsqr(z);
if (yy & mask) {
z = z ? bigtrunc(bigmul0(z, x)) : x;
}
}
return bignorm(z);
}
/* NOTREACHED */
break;
default:
return rb_num_coerce_bin(x, y, rb_intern("**"));
}
return DBL2NUM(pow(rb_big2dbl(x), d));
}
The first argument to this function -VALUE x- is the base, the Bignum we want to exponentiate. The second -VALUE y- is the exponent. The Ruby interpreter starts checking the exponent type with the macro TYPE(v). This macro returns the exponent type, that could be a Fixnum, a Bignum or a Float.
If the exponent is a Bignum, or it is a Fixnum but the base is large enough, it prints our already familiar warning:
in a**b, b may be too big
Concretely, this warning appears when:
-
The size of the base in bytes is bigger than BIGLEN_LIMIT (1024*1024 / the size of an int)
-
The size of the base in bytes is bigger than BIGLEN_LIMIT / exponent.
In those cases in which the operands are too big, Ruby just transforms both numbers to a floating point double and perform the operation calling the standard C pow() function; then it converts the result back to an integer.
This seems a last resort option, and it won't normally succeed, as the biggest double a typicial 64 bit machine can store is of order 10^308. Any number bigger than that will be converted to a Float::INFINITY, which is precisely what we are getting:
ruby-1.9.2-p0 > (8392498274982739487923749879872 ** 431565672837) == Float::INFINITY (irb):56: warning: in a**b, b may be too big => true
Luckily for us, there is a better way to perform modular exponentiation.
A Ruby implementation of the algorithm could be like this:
class Integer
def mod_pow(exp, mod)
result = 1
base = self
while exp > 0
if (exp & 1) == 1
result = (result * base) % mod
end
exp = exp >> 1
base = (base * base) % mod
end
result
end
end
With this algorithm we can calculate modular exponentiation for really big numbers:
ruby-1.9.2-p0 > require 'mod_pow' => true ruby-1.9.2-p0 > 8392498274982739487923749879872.mod_pow(43156567,1928739128739) => 960137722727
I also implemented this same algorithm as a C extension to see the performance improvement I could obtain. To my surprise, the C version of the algorithm was only a mere 12% faster than the Ruby version. You can check the code for the C extension in Github.