x ^ y Mod z

[bdbackify]

Hi, I was wondering if there's any general algorithm where you can calculate x^y Mod z assuming they're all positive integers without having to calculate x^y (since extremely large results don't keep all their digits in Visual Basic 2008)?

[jemidiah]

Yup, the usual algorithm is exponentiation by squaring with modular reduction after each step, and I imagine better ones exist. It's a native command in Python if I remember correctly, so it's a common operation. Here's a Wikipedia section discussing it. You can write a recursive version of this algorithm extremely quickly, eg. using the pseudocode in the section following the one I linked and reducing the result each time before returning.

[bdbackify]

Thank you very much this was helpful the algorithm seems to be quick too. I was wondering if there's an even more generic algorithm for if y is a negative integer (in my case if it's negative it will always be -1).

[jemidiah]

If y=-1, you use the extended Euclidean algorithm to compute the result. You can then reduce the y negative case to the y positive case by inverting, computing as above, and inverting again.

Here's another Wikipedia section discussing it. Note that x^(-1) mod z does not always exist, as in the case of 2^(-1) mod 4 (since 0*2 = 0, 1*2 = 2, 2*2=4=0, 3*2 = 6=2). It in fact exists precisely when x and z are relatively prime, which the Euclidean algorithm is designed to detect.