0

私たちが知っているように、1000000007は大きな素数です。1000000007を法とする2つの大きな数の乗算を見つけるにはどうすればよいですか

たとえば、78627765 * 67527574 mod 1000000007を見つけたい場合、どうすればよいですか。

少なくとも誰かが私に手順を教えてくれたら、私は試してみます

注：plsは、int、long、longlongなどのプリミティブデータ型を使用したソリューションを教えてくれます。よろしくお願いします。

4

3 に答える 3

10

モジュロ連鎖は、数値計算空間の限界を押し上げる合理的な数値で機能します。

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

これの証明は非常に簡単で、世界中の暗号化 Web サイトに文字通り何千もの例があります。簡単なサンプル:

(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

Since this looks like a homework or context problem, I will only give hints.

If you know x%m and y%m, how can you find (x+y)%m? If you know x%m, how can you find (2x)%m?

Since you want to find (a*b)%m, is there a way you can decompose b so that you can use the above two hints?

于 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

2 番目の方法では、正確な操作が必要になる場合があることに注意してください。代わりに「long double」を使用することもできます

于 2012-09-02T13:58:28.123 に答える