如何在不使用太多计算器的情况下计算5 ^ 55 mod 221的模数？
我想在密码学的数论中有一些简单的原则可以用来计算这样的问题。
如何计算大数的模数？
81
- Priyank Bolia
8
1这是一个解释：http://www.devx.com/tips/Tip/39012 - tur1ng
devx的链接并不是很有用，对于这种事情，还有其他简单的数论方法，据我所知。 - Priyank Bolia
1@Priyank Bolia：不用担心，这个问题不太可能被关闭。这是一个好问题。如果它被关闭了，会有很多人投票重新开放。 - jason
4没错，我们中的很多人都知道计算机科学有时涉及数学。 - Cascabel
14MathOverflow是面向研究生及以上水平的数学问答平台；这个问题在那里可能会被不赞同。 - jason
显示剩余3条评论
10个回答
105
好的，你想计算 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且0<=a1。
例如，让我们计算5^55 mod 221。首先，5已经被减小到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并减少mod 221，然后将其平方并减少mod 221以获得5^2 mod 221等。
上述算法正式化了这个想法。- jason
10
1大多数编程语言都有内置的这种运算符。例如，在基于 C 的语言中，
% 运算符是模运算符。因此，int p = 625 % 221 将把 183 赋值给 p。您可以通过将 625 除以 221 并获得答案 2 来实现相同的功能作为整数除法。然后你取 625 - 2 * 221 来得到余数。在这种情况下，625 - 2 * 221 = 183 是答案。 - jason2是的，正如我在结尾段落中描述的那样，您可以通过平方进行指数运算。 - jason
6在指数较大的情况下，您实际上可以比使用平方法更好地计算幂。请注意，您发现
5^16 == 1 (mod 221)。因此，5^k == 5^(k%16) (mod 221)。 - Cascabel2@Jason：你写道：“首先，将a对m取模。这意味着要找到一个数字a1，使得0 <= a1 < m且a = a1 mod m。”看起来最后一个等式中有个错别字，应该是“a1 = a mod m”吧？ - Timofey
2@Jason，大部分情况下，如果你只是在你的伪代码中添加“;”（和其他一些字符），它就会变成C语言。 - haneefmubarak
显示剩余5条评论
30
补充Jason的答案：
如果要处理非常大的指数，你可以利用指数的二进制展开来加快计算速度。首先通过重复平方计算5、5^2、5^4和5^8模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，但不确定）。
- Tom Smith
3
7这是更好的解释。 - Priyank Bolia
1我怀疑避免使用平方取幂法实际上会更快（通常情况下），而是直接搜索最小指数$k$，使得$5^k == 5 (mod 221)$。当然，这当然取决于指数与模数的大小，但一旦你有了那个指数，你只需要进行一次计算（指数模$k$）和查找。请注意，如果您需要重复类似的计算，则肯定更好。（通常情况下，您无法寻找$a^k == 1 (mod 221)$，因为只有当$a$和221互质时才会发生这种情况） - Cascabel
1一般来说，找到具有该属性的最小指数比平方乘法要慢得多。但是，如果您知道模数的因数分解，则可以轻松计算 Carmichael Lambda 函数，它是您的 k 的倍数。 - President James K. Polk
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;
}
- Timothy Kwok
3
1当
mod*mod > UINT_MAX + 1 时，x * power 和 power * power 可能会发生溢出。 - chux - Reinstate Monica没错，@chux是对的，在x * power和power * power期间我们应该进行取模。 - jack_1729
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
- Udhayakumar.c
1
这种方法比指数方式慢吗？ - Pacerier
2
在Java中，Jason的答案为（注意 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);
}
}
- Martin Pfeffer
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);
}
- Jaroslav Kubacek
2
中国剩余定理可以作为一个初始点，因为221 = 13 * 17。因此，将其拆分成两部分，在最后合并，一部分是mod 13的，另一部分是mod 17的。其次，我相信有一个证明对于所有非零a，a^(p-1) = 1 mod p，这也有助于将您的问题简化为5^55变为mod 13情况下的5^3，因为13*4=52。如果您在“有限域”主题下查找，可能会发现一些有关如何解决此问题的好结果。
编辑：我提到因子的原因是这样可以将零因子分解为非零元素，例如，如果您尝试计算13^2 * 17^4 mod 221，答案为零，因为13*17=221。很多大数字不会是质数，但是有方法可以找到大质数，因为它们在密码学和其他数学领域中经常使用。
编辑：我提到因子的原因是这样可以将零因子分解为非零元素，例如，如果您尝试计算13^2 * 17^4 mod 221，答案为零，因为13*17=221。很多大数字不会是质数，但是有方法可以找到大质数，因为它们在密码学和其他数学领域中经常使用。
- JB King
2
我一开始就不知道阶乘，现在正试图使用Miller Rabin算法证明这个数字是质数。所以，我处于相反的位置。 - Priyank Bolia
这里没有阶乘，但有一种不同的因数分解。整数n的阶乘被定义为小于n的所有正整数的乘积，例如2！= 2，3！= 6等，并经常使用！符号表示。因数分解是不同的，没有一个通用的符号用于表示正在分解的整数。 - JB King
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;
}
- Boris
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比较时返回值不正确的错误。
- Stepan Pogosyan
2
非常感谢您的反馈。请问您能否提供导致输出不正确的输入数据？ - Stepan Pogosyan
1非常感谢您发现错误。我已经更正为1％N。 - Stepan Pogosyan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接