How to calculate modulus of large numbers?

Okay, so you want to calculate a^b mod m. First we'll take a naive approach and then see how we can refine it.

First, reduce a mod m. That means, find a number a1 so that 0 <= a1 < m and a = a1 mod m. Then repeatedly in a loop multiply by a1 and reduce again mod m. Thus, in pseudocode:

a1 = a reduced mod m
p = 1
for(int i = 1; i <= b; i++) {
    p *= a1
    p = p reduced mod m
}

By doing this, we avoid numbers larger than m^2. This is the key. The reason we avoid numbers larger than m^2 is because at every step 0 <= p < m and 0 <= a1 < m.

As an example, let's compute 5^55 mod 221. First, 5 is already reduced mod 221.

  1. 1 * 5 = 5 mod 221
  2. 5 * 5 = 25 mod 221
  3. 25 * 5 = 125 mod 221
  4. 125 * 5 = 183 mod 221
  5. 183 * 5 = 31 mod 221
  6. 31 * 5 = 155 mod 221
  7. 155 * 5 = 112 mod 221
  8. 112 * 5 = 118 mod 221
  9. 118 * 5 = 148 mod 221
  10. 148 * 5 = 77 mod 221
  11. 77 * 5 = 164 mod 221
  12. 164 * 5 = 157 mod 221
  13. 157 * 5 = 122 mod 221
  14. 122 * 5 = 168 mod 221
  15. 168 * 5 = 177 mod 221
  16. 177 * 5 = 1 mod 221
  17. 1 * 5 = 5 mod 221
  18. 5 * 5 = 25 mod 221
  19. 25 * 5 = 125 mod 221
  20. 125 * 5 = 183 mod 221
  21. 183 * 5 = 31 mod 221
  22. 31 * 5 = 155 mod 221
  23. 155 * 5 = 112 mod 221
  24. 112 * 5 = 118 mod 221
  25. 118 * 5 = 148 mod 221
  26. 148 * 5 = 77 mod 221
  27. 77 * 5 = 164 mod 221
  28. 164 * 5 = 157 mod 221
  29. 157 * 5 = 122 mod 221
  30. 122 * 5 = 168 mod 221
  31. 168 * 5 = 177 mod 221
  32. 177 * 5 = 1 mod 221
  33. 1 * 5 = 5 mod 221
  34. 5 * 5 = 25 mod 221
  35. 25 * 5 = 125 mod 221
  36. 125 * 5 = 183 mod 221
  37. 183 * 5 = 31 mod 221
  38. 31 * 5 = 155 mod 221
  39. 155 * 5 = 112 mod 221
  40. 112 * 5 = 118 mod 221
  41. 118 * 5 = 148 mod 221
  42. 148 * 5 = 77 mod 221
  43. 77 * 5 = 164 mod 221
  44. 164 * 5 = 157 mod 221
  45. 157 * 5 = 122 mod 221
  46. 122 * 5 = 168 mod 221
  47. 168 * 5 = 177 mod 221
  48. 177 * 5 = 1 mod 221
  49. 1 * 5 = 5 mod 221
  50. 5 * 5 = 25 mod 221
  51. 25 * 5 = 125 mod 221
  52. 125 * 5 = 183 mod 221
  53. 183 * 5 = 31 mod 221
  54. 31 * 5 = 155 mod 221
  55. 155 * 5 = 112 mod 221

Therefore, 5^55 = 112 mod 221.

Now, we can improve this by using exponentiation by squaring; this is the famous trick wherein we reduce exponentiation to requiring only log b multiplications instead of b. Note that with the algorithm that I described above, the exponentiation by squaring improvement, you end up with the right-to-left binary method.

a1 = a reduced mod m
p = 1
while (b > 0) {
     if (b is odd) {
         p *= a1
         p = p reduced mod m
     }
     b /= 2
     a1 = (a1 * a1) reduced mod m
}

Thus, since 55 = 110111 in binary

  1. 1 * (5^1 mod 221) = 5 mod 221
  2. 5 * (5^2 mod 221) = 125 mod 221
  3. 125 * (5^4 mod 221) = 112 mod 221
  4. 112 * (5^16 mod 221) = 112 mod 221
  5. 112 * (5^32 mod 221) = 112 mod 221

Therefore the answer is 5^55 = 112 mod 221. The reason this works is because

55 = 1 + 2 + 4 + 16 + 32

so that

5^55 = 5^(1 + 2 + 4 + 16 + 32) mod 221
     = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221
     = 5 * 25 * 183 * 1 * 1 mod 221
     = 22875 mod 221
     = 112 mod 221

In the step where we calculate 5^1 mod 221, 5^2 mod 221, etc. we note that 5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1)) because 2^k = 2^(k-1) + 2^(k-1) so that we can first compute 5^1 and reduce mod 221, then square this and reduce mod 221 to obtain 5^2 mod 221, etc.

The above algorithm formalizes this idea.


To add to Jason's answer:

You can speed the process up (which might be helpful for very large exponents) using the binary expansion of the exponent. First calculate 5, 5^2, 5^4, 5^8 mod 221 - you do this by repeated squaring:

 5^1 = 5(mod 221)
 5^2 = 5^2 (mod 221) = 25(mod 221)
 5^4 = (5^2)^2 = 25^2(mod 221) = 625 (mod 221) = 183(mod221)
 5^8 = (5^4)^2 = 183^2(mod 221) = 33489 (mod 221) = 118(mod 221)
5^16 = (5^8)^2 = 118^2(mod 221) = 13924 (mod 221) = 1(mod 221)
5^32 = (5^16)^2 = 1^2(mod 221) = 1(mod 221)

Now we can write

55 = 1 + 2 + 4 + 16 + 32

so 5^55 = 5^1 * 5^2 * 5^4 * 5^16 * 5^32 
        = 5   * 25  * 625 * 1    * 1 (mod 221)
        = 125 * 625 (mod 221)
        = 125 * 183 (mod 183) - because 625 = 183 (mod 221)
        = 22875 ( mod 221)
        = 112 (mod 221)

You can see how for very large exponents this will be much faster (I believe it's log as opposed to linear in b, but not certain.)


/* The algorithm is from the book "Discrete Mathematics and Its
   Applications 5th Edition" by Kenneth H. Rosen.
   (base^exp)%mod
*/

int modular(int base, unsigned int exp, unsigned int mod)
{
    int x = 1;
    int power = base % mod;

    for (int i = 0; i < sizeof(int) * 8; i++) {
        int least_sig_bit = 0x00000001 & (exp >> i);
        if (least_sig_bit)
            x = (x * power) % mod;
        power = (power * power) % mod;
    }

    return x;
}