algorithm - 使用素数的非常大数的余数

Question

我遇到了一个问题，我需要使用质数找到一个非常大的数字的余数。实际的问题是数量很大，大约10^100. 所以我们不能将它存储在任何变量中，唯一的选择是将它存储在一个数组中。

现在我们需要使用素数 say 找到这个数字的余数(10^9)+7。

我想不出任何想法，有什么建议吗？

PS：编程语言是C++。

Answer 1

一般来说，我会利用以下事实

a^n mod b == (a mod b)^n mod b

所以在这个例子中，你可以计算

= 10^100 mod 10^9 + 7 = (10^10 mod 10^9 + 7)^10  mod 10^9 + 7

= (999999937) ^ 10 mod 10^9 + 7
= ((999999937) ^ 2 mod 10^9 + 7) ^ 5 mod 10^9 + 7
= 4900 ^ 5 mod 10^9 +7
= 226732710

等等

Answer 2

什么编程语言？C/C++、Java、PHP、Perl、JavaScript... 都有某种形式的 Big Integer，它允许您拥有不超过以空字符结尾的字符串的最大长度的整数。实际语法取决于语言，但可能类似于：

$num = new BigInt("1234567891234567912346579865432165498765462132165498765431");
$prime = new BigInt("54657613216846346874321638743");
$mod = $num.mod($prime);

Answer 3

十进制数（例如 1234）可以通过以下方式从其数字构建：

x=1;
x=x*10+2;
x=x*10+3;
x=x*10+4;//x=1234

（你从最重要的数字开始，每次都取下一个）。

由于加法和乘法允许将模运算移入其中，因此您可以简单地在每个步骤上应用模数（例如 7）：

x=1;
x=(x*10+2)%7;
x=(x*10+3)%7;
x=(x*10+4)%7;//x=1234%7

如果您的素数约为 10^9，则 32 位整数将不够用，但 64 位将绰绰有余。