如何找到模数为100000007的大数的多重化

Question

我们知道1000000007是一个大素数.如何找到模数为1000000007的两个大数的乘法

例如,如果我想找到78627765*67527574 mod 1000000007,我该怎么办呢.

至少如果有人告诉我我将尝试的程序

注意:请告诉我原始数据类型的解决方案,如int,long或long long,提前感谢

Answer 1

Modulo链接使用合理的数字来推动数值comp空间的限制:

(A * B) % C == ((A % C) * (B % C)) % C.

这方面的证据非常简单,世界各地的密码学网站上都有成千上万的例子.一个简单的样本:

(7*8)%5 = 56%5 = 1

和

((7 % 5) * (8 % 5)) % 5 = (2 * 3) % 5 = 6 % 5 = 1

我希望这有帮助.显然当A和B已经被推到你的高端平台限制并且仍然小于C时,它变得毫无意义,但是当不是这种情况时它会非常方便(即当A> C和/或B> C时).