Calculating pow(a,b) mod n

Question

I want to calculate a^bmod 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; } 

Answer 1

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.

---

Note that the multiplications result * base and base * base are subject to overflow in this simplified version. If the modulus is more than half the width of T (i.e. more than the square root of the maximum T value), then one should use a suitable modular multiplication algorithm instead - see the answers to Ways to do modulo multiplication with primitive types.