如何在不使用计算器的情况下计算 5^55 模数 221 的模数？
我想密码学中的数论中有一些简单的原则来计算这些东西。
151559 次
10 回答
102
好的，所以你要计算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 * 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 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 * (5^1 mod 221) = 5 mod 2215 * (5^2 mod 221) = 125 mod 221125 * (5^4 mod 221) = 112 mod 221112 * (5^16 mod 221) = 112 mod 221112 * (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和 reduce mod 221，然后将其平方和 reducemod 221以获得5^2 mod 221等。
上面的算法形式化了这个想法。
于 2010-02-01T15:36:12.493 回答
29
添加到杰森的答案：
您可以使用指数的二进制展开来加快处理速度（这可能对非常大的指数有帮助）。首先计算 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)
您可以看到对于非常大的指数，这将如何更快（我相信它是对数而不是 b 中的线性，但不确定。）
于 2010-02-01T15:53:26.383 回答
12
/* 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;
}
于 2012-01-23T14:03:18.953 回答
3
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
于 2011-08-18T19:15:53.367 回答
2
中国剩余定理的初始点是 221 = 13 * 17。因此，将其分解为最后合并的两部分，一个用于 mod 13，一个用于 mod 17。其次，我相信有一些证据对于所有非零 a，a^(p-1) = 1 mod p 这也有助于减少您的问题，因为对于 mod 13 的情况，5^55 变为 5^3，即 13*4=52。如果您查看“有限域”主题，您可能会发现一些关于如何解决此问题的好结果。
编辑：我提到这些因素的原因是，这创造了一种将零分解为非零元素的方法，就好像你尝试了 13^2 * 17^4 mod 221 之类的东西，答案是 0，因为 13*17=221。许多大数不会是素数，尽管有一些方法可以找到大素数，因为它们在密码学和数学的其他领域中被大量使用。
于 2010-02-01T15:45:32.077 回答
2
您正在寻找的是模幂，特别是模二进制幂。这个维基百科链接有伪代码。
于 2010-02-01T15:48:07.297 回答
2
这是我为 IBAN 验证所做的代码的一部分。随意使用。
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);
}
于 2010-02-11T17:53:25.387 回答
2
Jason 在 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);
}
}
于 2016-01-09T23:45:34.030 回答
1
只需提供 C 的 Jason 答案的另一种实现。
和同学讨论后，根据Jason的解释，如果你不是很在意性能的话，我更喜欢递归版本：
例如：
#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;
}
于 2013-10-15T05:58:20.060 回答
1
这称为模幂运算（https://en.wikipedia.org/wiki/Modular_exponentiation）。
假设您有以下表达式：
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
模幂算法做出以下假设：
x ^ y == (x ^ |y/2|) ^ 2 if y is even
x ^ y == x * ((x ^ |y/2|) ^ 2) if y is odd
所以递归模幂算法在java中看起来像这样：
/**
* Modular exponentiation algorithm
* @param x Assumption: x >= 0
* @param y Assumption: y >= 0
* @param N Assumption: N > 0
* @return x ^ y mod N
*/
public static long modExp(long x, long y, long N) {
if(y == 0)
return 1 % N;
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);
}
特别感谢@chux在 y 和 0 比较的情况下发现错误返回值不正确。
于 2017-10-15T20:00:14.490 回答