[phobos] Issue6244, implementing 'powmod'

Alex Jercaianu alex.jercaianu at gmail.com
Mon Oct 2 16:48:10 UTC 2017


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 
Or does D have any facility similar to 'mulmod'?


[1] - 

More information about the phobos mailing list