[Feature request] `powmod`

[konsumlamm]

Description

Provide a powmod(base, exponent, modulus) function that computes (base ^ exponent) % modulus, but more efficiently than the naive computation. In particular, it should avoid building up BigInts that are substantially larger than modulus.

Related work

• D
• Rust

[dlesnoff]

We should first implement a gcd function and a bitops operation to count the number of bits. I tried to implement it for prime modulus and to add some tests. I have to add sign handling too. I am unsure how to handle composite numbers. From a mathematical point of view, I would reduce the exponent modulo the euler totient function of the modulus, and compute the power modulo each factor. We compute the result back with CRT (Chinese Remainder Theorem). But computing the euler totient is as hard as factoring the integer (for very large modulus). So there are probably more practical way. Maybe we should give the euler totient as an optional parameter ? It would avoid check if the modulus is prime and to factor it. I checked Rust library but don't understand their logic. For BigInt, they call a function of another module named power (so I guess they do it the naive way ?). For BigUint, they use a "Montgomerry Ladder" for odd integers implemented in another file I could not find, and for even integers I have not check it yet, but is handmade and optimized.

[konsumlamm]

For now, we could just implement it like pow (using binary exponentiation, but take the modulo every iteration, like the D implementation does) and optimize it later.