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;
}