大数のモジュールの計算方法は？

質問

5^55モジュラス221のモジュラスを電卓をあまり使わずに計算する方法を教えてください。

暗号技術における数論には、このようなことを計算する簡単な原理があるのでしょう。

どのように解決するのですか？

さて、では計算したいのは a^b mod m . まず、素朴なアプローチをとり、次にそれをどのように洗練させるかを見てみましょう。

まず、縮小して a mod m . つまり、数字を見つける a1 ということで 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 .

さて、これを改善するために 二乗による指数計算 これは有名なトリックで、指数を減らして log b の代わりに b . 上で説明したアルゴリズム、二乗改善による指数化では、最終的に 右から左への2進法 .

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
}

したがって、2進数で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 など。

上記のアルゴリズムはこの考えを形式化したものです。