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
_______________________________________________
phobos mailing list
phobos@puremagic.com
http://lists.puremagic.com/mailman/listinfo/phobos