javascript - 对非常大的数进行模运算

Question

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

例如，进行素数模运算:

6864797660130609714981900799081393217269435300143305409394463459185543183
3976560521225596406614545549772963113914808580371219879997166438125740282
91115057151 % 4

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

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

Answer 1

我没有足够的声誉来评论，但是这两个人说你只能看最后的数字是错误的，以 %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;
}