如何计算大数模数? [英] How to calculate modulus of large numbers?

问题描述

如何在不使用计算器的情况下计算5 ^ 55模数221的模数?

How to calculate modulus of 5^55 modulus 221 without much use of calculator?

我猜想密码学中的数论中有一些简单的原理可以计算出这些东西.

I guess there are some simple principles in number theory in cryptography to calculate such things.

推荐答案

好的，因此您要计算a^b mod m.首先，我们将采用一种幼稚的方法，然后看看如何对其进行改进.

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.

首先，减少a mod m.这意味着找到一个数字a1，以便0 <= a1 < m和a = a1 mod m.然后在循环中反复乘以a1并再次减小mod m.因此，用伪代码:

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
}

这样做，我们避免使用大于m^2的数字.这是关键.我们避免使用大于m^2的数字的原因是因为在每个步骤0 <= p < m和0 <= a1 < 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.

作为一个例子，让我们计算5^55 mod 221.首先，5已被简化为mod 221.

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

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.请注意，使用我上面描述的算法(通过平方改进求幂)，最终得到

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
}

因此，因为55 = 110111(二进制)

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

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.之所以有效，是因为

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

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，等等.

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.

这篇关于如何计算大数模数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！