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