我们知道 1000000007 是一个很大的素数。我怎样才能找到两个大数模1000000007的乘法
例如，如果我想找到 78627765*67527574 mod 1000000007，我该怎么做。
至少如果有人告诉我我会尝试的程序
注意：请让我知道原始数据类型的解决方案，如 int、long 或 long long 在此先感谢
问问题
4894 次
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 回答