As hinted by Abigail-II, exponentiating mod a number is better accomplished by keeping the numbers reduced at every step. The straightforward algorithm would be
`# modexp ( base, exp, n ) = base**exp mod n
sub modexp {
my ($base, $exp, $n) = @_;
die "Negative exponent" if $exp<0;
my $res = 1;
while ($exp>0) {
$res = ( $res * $base ) % $n;
$exp--;
}
return $res;
}
`
This has the disadvantage of being of linear complexity in the exponent. An algorithm linear in log($exp) is as follows:
`sub binmodexp {
my ($base, $exp, $n) = @_;
die "Negative exponent" if $exp<0;
my $res = 1;
my $mul = $base % $n;
while ($exp) {
if ($exp & 1) {
$res = ( $res * $mul ) % $n;
}
$exp>>=1;
$mul = ($mul*$mul) % $n;
}
return $res;
}
`
It is based on the simple (but powerful) observation that
if you have to take, say, the 37-th power of a number *a*, as 37 = 2^5 + 2^2 + 1, it is enough to multiply the factors
*a*,
*a*^(2^2) = (*a*^2) ^ 2
and
*a*^(2^5) = ((((*a*^2) ^ 2) ^ 2) ^ 2) ^ 2
Best regards
Antonio Bellezza
*The stupider the astronaut, the easier it is to win the trip to Vega - A. Tucket* |
Comment onThe Exponentiation of (not-so) Large Primes