October 02, 2017 [phobos] Issue6244, implementing 'powmod' | ||||
---|---|---|---|---|

| ||||

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 |

Copyright © 1999-2021 by the D Language Foundation