如何计算大数的模数? [英] 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 <米
.
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 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
155 * 5 = 112 mod 221
112 * 5 = 118 mod 221
118 * 5 = 148 mod 221
148 * 5 = 77 mod 221
77 * 5 = 164 mod 221
164 * 5 = 157 mod 221
157 * 5 = 122 mod 221
122 * 5 = 168 mod 221
168 * 5 = 177 mod 221
177 * 5 = 1 mod 221
1 * 5 = 5 mod 221
5 * 5 = 25 mod 221
25 * 5 = 125 mod 221
125 * 5 = 183 mod 221
183 * 5 = 31 mod 221
31 * 5 = 155 mod 221
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 * (5^1 mod 221) = 5 mod 221
5 * (5^2 mod 221) = 125 mod 221
125 * (5^4 mod 221) = 112 mod 221
112 * (5^16 mod 221) = 112 mod 221
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屋!