大量的模运算

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;
}