31 lines
769 B
D
31 lines
769 B
D
module modular_exponentiation;
|
|
|
|
private import std.bigint;
|
|
|
|
BigInt powMod(BigInt base, BigInt exponent, in BigInt modulus)
|
|
pure nothrow /*@safe*/ in {
|
|
assert(exponent >= 0);
|
|
} body {
|
|
BigInt result = 1;
|
|
|
|
while (exponent) {
|
|
if (exponent & 1)
|
|
result = (result * base) % modulus;
|
|
exponent /= 2;
|
|
base = base ^^ 2 % modulus;
|
|
}
|
|
|
|
return result;
|
|
}
|
|
|
|
version (modular_exponentiation)
|
|
void main() {
|
|
import std.stdio;
|
|
|
|
powMod(BigInt("29883481620585741369158914214988194" ~
|
|
"66320163312926952423791023078876139"),
|
|
BigInt("235139930337346448646612254452369009" ~
|
|
"4744975233415544072992656881240319"),
|
|
BigInt(10) ^^ 40).writeln;
|
|
}
|