对非常大的数进行模运算

Question

在无法采用模幂方法的情况下，您将如何对相当大的数执行模运算？

例如，取这个素数模运算：

6864797660130609714981900799081393217269435300143305409394463459185543183
3976560521225596406614545549772963113914808580371219879997166438125740282
91115057151 % 4

WolframAlpha 告诉我它是 3。这很好，但我想编写一个算法以便我自己的计算器应用程序可以处理它。

我假设对于如此大的数字，我会将数字存储在一个数组中，每个数字一个元素。

Answer 1

如果你有这样的数字：xyz % n，你只需要做yz % n。您需要 n%10 + 1 个最后数字才能使您的操作具有最佳性能。

Answer 2

我没有足够的声誉来发表评论，但是这两个说你只能看最后数字的人是错误的，以 %7 为例 - 你总是必须看所有数字。

你可能知道 (a+b)%n = (a%n + b%n) % n 和 (a*b)%n = (a%n * b%n) % n 使用那个我们可以先计算 1%n、10%n、100%n 等等，然后将这些值乘以您的数字中的数字，最后将它们相加。

我用c++写的：

//assume we have number of length len in reversed order
//example: 123%9 -> n = 9, num[0] = 3, num[1] = 2; num[2] = 1, len = 3
int mod(int n, int num[], int len)
{
    int powersOf10modn = 1;
    int anwser = 0;
    for(int i = 0; i < len; i++)
    {
        anwser = (anwser + powersOf10modn * num[i]) % n;
        powersOf10modn = (powersOf10modn*10) % n;
    }
    return anwser;
}

对非常大的数进行模运算

Modulo operation on a very large number

javascript

algorithm

math

modulo