0

我们知道 1000000007 是一个很大的素数。我怎样才能找到两个大数模1000000007的乘法

例如，如果我想找到 78627765*67527574 mod 1000000007，我该怎么做。

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

注意：请让我知道原始数据类型的解决方案，如 int、long 或 long long 在此先感谢

4

3 回答 3

10

模链与合理的数字一起工作，这些数字正在推动您的数字比较空间的限制：

(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 ）。

于 2012-09-02T10:07:28.553 回答
1

由于这看起来像是一个家庭作业或上下文问题，我只会给出提示。

如果你知道 x%m 和 y%m，你怎么能找到 (x+y)%m？如果你知道 x%m，你怎么能找到 (2x)%m？

既然要找(a*b)%m，有没有办法可以分解b，这样就可以使用上面的两个提示了？

于 2012-09-02T11:05:47.590 回答
1

你为什么不想使用 64 位算法呢？当然，这仅在被相乘的操作数每个不超过 32 位时才有效（但这也可以固定）。考虑：

typedef unsigned long long uint64;
uint64 m = 1000000007UL;
uint64 r = (uint64)a * (uint64)b;
r = r % m; // get the residue

还可以对其进行优化以避免 '%' 这可能很昂贵：

double inv = 1.0 / 1000000007UL; // precompute inverse
uint64 r = (uint64)a * (uint64)b;
uint64 rf = (uint64)floor((double)a * (double)b * inv); // floor(a * b / m) 
r = r - rf * m; //  residue

请注意，第二种方法可能需要一些准确的操作。您也可以改用“long double”

于 2012-09-02T13:58:28.123 回答