如何计算大数模数？

Question

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

我想密码学中的数论有一些简单的原理来计算这些东西。

Answer 1

好的，所以你要计算a^b mod m。首先，我们将采取一种天真的方法，然后看看我们如何改进它。首先，减少a mod m。这意味着，找到一个数字，a1以便0 <= a1 < m和a = a1 mod m。然后在一个循环中重复乘以a1并再次减少mod m。因此，在伪代码中：a1 = a reduced mod mp = 1for(int i = 1; i <= b; i++) {&nbsp; &nbsp; p *= a1&nbsp; &nbsp; p = p reduced mod m}通过这样做，我们避免大于的数字m^2。这是关键。我们避免数字大于的原因m^2是因为在每一步0 <= p < m和0 <= a1 < m。举个例子，让我们来计算吧5^55 mod 221。首先，5已经减少了mod 221。1 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221112 * 5 = 118 mod 221118 * 5 = 148 mod 221148 * 5 = 77 mod 22177 * 5 = 164 mod 221164 * 5 = 157 mod 221157 * 5 = 122 mod 221122 * 5 = 168 mod 221168 * 5 = 177 mod 221177 * 5 = 1 mod 2211 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221112 * 5 = 118 mod 221118 * 5 = 148 mod 221148 * 5 = 77 mod 22177 * 5 = 164 mod 221164 * 5 = 157 mod 221157 * 5 = 122 mod 221122 * 5 = 168 mod 221168 * 5 = 177 mod 221177 * 5 = 1 mod 2211 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221112 * 5 = 118 mod 221118 * 5 = 148 mod 221148 * 5 = 77 mod 22177 * 5 = 164 mod 221164 * 5 = 157 mod 221157 * 5 = 122 mod 221122 * 5 = 168 mod 221168 * 5 = 177 mod 221177 * 5 = 1 mod 2211 * 5 = 5 mod 2215 * 5 = 25 mod 22125 * 5 = 125 mod 221125 * 5 = 183 mod 221183 * 5 = 31 mod 22131 * 5 = 155 mod 221155 * 5 = 112 mod 221因此，5^55 = 112 mod 221。现在，我们可以通过使用取幂进行平方来改善这一点; 这是着名的技巧，其中我们将求幂减少到只需要log b乘法而不是b。请注意，使用上面描述的算法，通过平方改进进行求幂，最终得到了从右到左的二进制方法。a1 = a reduced mod mp = 1while (b > 0) {&nbsp; &nbsp; &nbsp;if (b is odd) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p *= a1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;p = p reduced mod m&nbsp; &nbsp; &nbsp;}&nbsp; &nbsp; &nbsp;b /= 2&nbsp; &nbsp; &nbsp;a1 = (a1 * a1) reduced mod m}因此，因为55 = 110111二进制1 * (5^1&nbsp; mod 221) = 5 mod 2215 * (5^2&nbsp; mod 221) = 125 mod 221125 * (5^4&nbsp; mod 221) = 112 mod 221112 * (5^16&nbsp; mod 221) = 112 mod 221112 * (5^32&nbsp; 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&nbsp; &nbsp; &nbsp;= 5^1 * 5^2 * 5^4 * 5^16 * 5^32 mod 221&nbsp; &nbsp; &nbsp;= 5 * 25 * 183 * 1 * 1 mod 221&nbsp; &nbsp; &nbsp;= 22875 mod 221&nbsp; &nbsp; &nbsp;= 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等上述算法形式化了这个想法。

Answer 2

您可以使用指数的二进制扩展来加快进程（这可能对非常大的指数有用）。首先计算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 + 32so 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&nbsp; &nbsp;Applications 5th Edition" by Kenneth H. Rosen.&nbsp; &nbsp;(base^exp)%mod*/int modular(int base, unsigned int exp, unsigned int mod){&nbsp; &nbsp; int x = 1;&nbsp; &nbsp; int power = base % mod;&nbsp; &nbsp; for (int i = 0; i < sizeof(int) * 8; i++) {&nbsp; &nbsp; &nbsp; &nbsp; int least_sig_bit = 0x00000001 & (exp >> i);&nbsp; &nbsp; &nbsp; &nbsp; if (least_sig_bit)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x = (x * power) % mod;&nbsp; &nbsp; &nbsp; &nbsp; power = (power * power) % mod;&nbsp; &nbsp; }&nbsp; &nbsp; return x;}