[phobos] Issue6244, implementing 'powmod'
Alex Jercaianu
alex.jercaianu at gmail.com
Mon Oct 2 16:36:46 UTC 2017
Hello,
I am trying to implement the 'powmod' functionality as described
here [1].
The issue that I am having is that the algorithm uses
multiplications which can cause overflow.
If the base is 32 bits, then I can use 64 bit variables to handle
the result of multiplications, however the problem arises if the
base is 64 bit.
The pseudocode would look the following:
while (exponent > 0)
{
if (exponent & 1)
{
result = mulmod(result, base, modulus);
}
base = mulmod(base, base, modulus);
exponent >>= 1;
}
return result;
The problem that I am facing is with the 'mulmod' function which
should do multiplication and modulo of the result without
overflow problems.
Do you think that it would be a good idea to limit the base to 32
bits?
Or does D have any facility similar to 'mulmod'?
Thanks,
Alex
[1] -
https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
More information about the phobos
mailing list