如何计算大数的模数？

如何计算5 ^ 55模数221的模数？

我想在密码学的数论中有一些简单的原理来计算这样的事情。

Answer 1

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

首先，减lessa mod m 。 这意味着，find一个数字a1使0 <= a1 < m和a = a1 mod m 。 然后在a1中循环乘以a1再减lessmod 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已经减less了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的着名的技巧。 请注意，使用上面介绍的algorithm，通过平方的改进来求幂，最终使用从右到左的二进制方法 。

 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))因为我们可以首先计算5^1并减lessmod 221 ，然后对其进行平方并减lessmod 221得到5^2 mod 221 2^k = 2^(k-1) + 2^(k-1) 5^2 mod 221等

以上algorithm正式化了这个想法。

Answer 2

添加到Jason的答案：

您可以使用指数的二进制展开来加速进程（这可能对非常大的指数有帮助）。 首先计算5，5 ^ 2，5 ^ 4，5 ^ 8 mod 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) 

你可以看到，对于非常大的指数来说，这将会快得多（我相信它是log而不是b中的线性，但是不确定）。

Answer 3

 /* 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; } 

Answer 4

 5^55 mod221 = ( 5^10 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( 77 * 5^10 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 77 * 5^10) mod221 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( 183 * 5^10 * 5^10 * 5^10 * 5^5) mod221 = ( ( 183 * 5^10) mod221 * 5^10 * 5^10 * 5^5) mod221 = ( 168 * 5^10 * 5^10 * 5^5) mod221 = ( ( 168 * 5^10) mod 221 * 5^10 * 5^5) mod221 = ( 118 * 5^10 * 5^5) mod221 = ( ( 118 * 5^10) mod 221 * 5^5) mod221 = ( 25 * 5^5) mod221 = 112 

Answer 5

你正在寻找的是模幂运算，特别是模二进制指数运算。 这个维基百科链接有伪代码。

Answer 6

中国剩余定理的初始点是221 = 13 * 17。所以，把它分解成2部分，最后得到组合，一部分用于13号模式，另一部分用于17号模式。其次，我相信有一些证据对于所有非零的a，a（p-1）= 1 mod p，这也有助于减less你的问题，因为对于13情况，5 ^ 55变成5 ^ 3，13 * 4 = 52。 如果你看“有限域”的主题，你可能会find一些关于如何解决这个问题的好结果。

编辑：我提到这些因素的原因是，这创build了一个方法来将零分成非零元素，就好像你尝试了类似13 ^ 2 * 17 ^ 4 mod 221的东西，从13 * 17 = 221开始答案是零。 许多大数不会成为素数，尽pipe有很多方法可以find大质数，因为它们在密码学和math领域的其他领域被广泛使用。

Answer 7

这是我为IBANvalidation所做的代码的一部分。 随意使用。

  static void Main(string[] args) { int modulo = 97; string input = Reverse("100020778788920323232343433"); int result = 0; int lastRowValue = 1; for (int i = 0; i < input.Length; i++) { // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number if (i > 0) { lastRowValue = ModuloByDigits(lastRowValue, modulo); } result += lastRowValue * int.Parse(input[i].ToString()); } result = result % modulo; Console.WriteLine(string.Format("Result: {0}", result)); } public static int ModuloByDigits(int previousValue, int modulo) { // Calculating the modulus of a large number Wikipedia http://en.wikipedia.org/wiki/International_Bank_Account_Number return ((previousValue * 10) % modulo); } public static string Reverse(string input) { char[] arr = input.ToCharArray(); Array.Reverse(arr); return new string(arr); } 

Answer 8

杰森在Java中的答案（注意i < exp ）。

 private static void testModulus() { int bse = 5, exp = 55, mod = 221; int a1 = bse % mod; int p = 1; System.out.println("1. " + (p % mod) + " * " + bse + " = " + (p % mod) * bse + " mod " + mod); for (int i = 1; i < exp; i++) { p *= a1; System.out.println((i + 1) + ". " + (p % mod) + " * " + bse + " = " + ((p % mod) * bse) % mod + " mod " + mod); p = (p % mod); } } 

Answer 9

这被称为模幂（ https://en.wikipedia.org/wiki/Modular_exponentiation ）。

假设您有以下expression式：

 19^3 mod 7 

直接给19供电，你可以做以下事情：

 (((19 mod 7) * 19) mod 7) * 19) mod 7 

但是这可能需要很长时间，因为大量的顺序乘法，所以你可以乘以平方值：

 x mod N -> x ^ 2 mod N -> x ^ 4 mod -> ... x ^ 2 |log y| mod N 

模幂运算algorithm假定：

 x ^ y == (x ^ |y/2|) ^ 2 if y is even x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd 

所以recursion模幂algorithm在java中看起来像这样：

 public static long modExp(long x, long y, long N) { if(y == 0) return 1; long z = modExp(x, Math.abs(y/2), N); if(y % 2 == 0) return (long) ((Math.pow(z, 2)) % N); return (long) ((x * Math.pow(z, 2)) % N); } 

Answer 10

只要提供另一个由杰森的回答实施C.

在和我的同学讨论之后，根据Jason的解释，如果你不关心性能，我更喜欢recursion版本：

例如：

 #include<stdio.h> int mypow( int base, int pow, int mod ){ if( pow == 0 ) return 1; if( pow % 2 == 0 ){ int tmp = mypow( base, pow >> 1, mod ); return tmp * tmp % mod; } else{ return base * mypow( base, pow - 1, mod ) % mod; } } int main(){ printf("%d", mypow(5,55,221)); return 0; }