** Fast Modular Exponentiation algorithm ** in
Perl. This will silently fail if any of the argument are larger than
the square root of the largest allowable integer in your
implementation. A common implementation bound for integers is 2^31-1
or so. Thus, you should not have the modulus * m * bigger than
about \sqrt(2^31), which is about 46,340.

First we give a "verbose" perl version, then a somewhat less verbose one.

We define a function f(x,e,m) whose return value is x^e % m sub f { my($x,$e,$m) = @_; ## @_ is the array of arguments to the function my $y=1; while ($e>0) { if ($e % 2 == 0) { $x = $x * $x % $m; $e = $e/2; } else { $y = $y * $x % $m; $e = $e - 1; } } return $y; }

The just slightly less verbose version:

sub f { my($x,$e,$m) = @_; my $y=1; while ($e>0) { if ($e % 2 == 0) { $x *= $x; $x %= $m; $e /= 2; } else { $y *= $x; $y %= $m; $e -= 1; } } return $y; }