问如何计算大数的模数？

EN

好的，你想要计算a^b mod m。首先，我们将采取一种天真的方法，然后看看如何改进它。

首先，减少a mod m。也就是说，找到一个数字，这样0 <= a1 < m和a = a1 mod m就可以。然后在循环中重复乘以a1并再次减少mod m。因此，在伪代码中：

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

通过这样做，我们避免了大于m^2的数字。这是关键。我们避免数字大于m^2的原因是因为在每一步，0 <= p < m和0 <= a1 < m。

作为一个例子，让我们计算5^55 mod 221。首先，5已经降低了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

因此，5^55 = 112 mod 221。

现在，我们可以通过使用exponentiation by squaring来改进这一点；这是一个著名的技巧，在这个技巧中，我们将幂运算减少到只需要log b乘法而不是b。注意，使用我上面描述的算法，通过平方改进的幂运算，您最终得到了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
}

因此，由于55 = 110111，以二进制表示

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

因此，答案是5^55 = 112 mod 221。这样做的原因是因为

55 = 1 + 2 + 4 + 16 + 32

所以

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

在我们计算5^1 mod 221，5^2 mod 221等的步骤中，我们注意到5^(2^k) = 5^(2^(k-1)) * 5^(2^(k-1))，因为2^k = 2^(k-1) + 2^(k-1)，所以我们可以首先计算5^1并减少mod 221，然后平方并减少mod 221以获得5^2 mod 221，等等。

上面的算法形式化了这个想法。

补充一下Jason的答案：

您可以使用指数的二进制展开来加速这个过程(这对于非常大的指数可能很有帮助)。首先计算5，5^2，5^4，5^8mod 221 -你可以通过重复平方来完成：

 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)

现在我们可以写

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)

你可以看到，对于非常大的指数，这将会更快(我相信它是对数，而不是b中的线性，但不是确定的)。