8

a*amodを計算する必要nがaありますが、かなり大きいため、2 乗するとオーバーフローが発生します。(n-1) 2がオーバーフローする可能性が((a % n)*(a % n)) % nあるため、実行は機能しません。これはC++であり、私は使用していますint64_t

編集：

値の例: a = 821037907258 および n = 800000000000、2 乗するとオーバーフローします。

私はDevCPPを使用していますが、すでに大きな整数ライブラリを無駄に動作させようとしました。

編集2：

いいえ、これらの数字にパターンはありません。

4

5 に答える 5

15

大きな整数のライブラリを使用できず、ネイティブuint128_t（または同様のもの）がない場合は、手動でこれを行う必要があります。

1つのオプションはa、2つの32ビット量の合計として表すことです。つまり、a = 2 32 b + cです。ここで、bには32 msbsが含まれ、 cには32lsbsが含まれます。その場合、二乗は4つの相互乗算のセットです。各結果は64ビットタイプに適合することが保証されています。次に、個々の項を再結合するときにモジュロ演算を実行します（すべてを再調整するために必要なシフトを慎重に考慮します）。

于 2012-04-09T16:09:21.800 に答える
3

これはもう必要ないことはわかっています。別の解決策がありますが、それを実装するための別の方法を追加したいと思います。double and add アルゴリズムmod(a + b, n)と、オーバーフロー検出で処理するメソッドの 2 つの異なる手法が提供されます。

double and add アルゴリズムは通常、乗算が不可能であるか、コストがかかりすぎて直接計算できない分野 (楕円曲線など) で使用されますが、代わりにオーバーフローを処理する状況でそれを処理するために採用することができます。

次のコードは、(最適化しても) 一般に受け入れられているソリューションよりもおそらく遅いですが、速度が重要でない場合は、わかりやすくするためにこちらを使用することをお勧めします。

unsigned addmod(unsigned x, unsigned y, unsigned n)
{
    // Precondition: x<n, y<n
    // If it will overflow, use alternative calculation
    if (x + y <= x) x = x - (n - y);
    else x = (x + y) % n;
    return x;
}

unsigned sqrmod(unsigned a, unsigned n)
{
    unsigned b;
    unsigned sum = 0;

    // Make sure original number is less than n
    a = a % n;

    // Use double and add algorithm to calculate a*a mod n
    for (b = a; b != 0; b >>= 1) {
        if (b & 1) {
            sum = addmod(sum, a, n);
        }
        a = addmod(a, a, n);
    }
    return sum;
}
于 2012-04-09T17:30:18.333 に答える
-3

乗算を自分で実装し、実行ごとにnを加算して、結果をすぐに変更できます。

于 2012-04-09T16:06:55.187 に答える
-5

((a % n)*(a % n)) % n正の整数で機能するはずだと本当に思います。なぜうまくいかないと思いますか？反例はありますか？n が負の可能性がある場合、%演算子は未定義です。

于 2012-04-09T16:25:13.657 に答える