MoeinHm - 1 year ago 134
C Question

# Calculating pow(a,b) mod n

I want to calculate ab mod n for use in RSA decryption. My code (below) returns incorrect answers. What is wrong with it?

``````unsigned long int decrypt2(int a,int b,int n)
{
unsigned long int res = 1;

for (int i = 0; i < (b / 2); i++)
{
res *= ((a * a) % n);
res %= n;
}

if (b % n == 1)
res *=a;

res %=n;
return res;
}
``````

You can try this C++ code. I've used it with 32 and 64-bit integers. I'm sure I got this from SO.

``````template <typename T>
T modpow(T base, T exp, T modulus) {
base %= modulus;
T result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % modulus;
base = (base * base) % modulus;
exp >>= 1;
}
return result;
}
``````

You can find this algorithm and related discussion in the literature on p. 244 of

``````Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download