1

Cプログラム内から次のモジュロ除算演算を実行しています。

（5 ^ 6）mod 23 = 8

（5 ^ 15）mod 23 = 19

便宜上、次の関数を使用しています。

int mod_func(int p, int g, int x) {
    return ((int)pow((double)g, (double)x)) % p;
}

ただし、関数を呼び出したときの操作の結果は正しくありません。

mod_func(23, 5, 6) //returns 8
mod_func(23, 5, 15) //returns -6

モジュロ演算子には、オペランドのサイズに制限がありますか？

4

4 に答える 4

3

の整数部分はpow(5, 15)で表現できませんint（の幅intが32ビットであると仮定）。変換（キャスト式でのからdoubleへの変換int）は、CおよびC++では未定義の動作です。

未定義の動作を回避するにはfmod、関数を使用して浮動小数点の剰余演算を実行する必要があります。

于 2012-12-19T21:59:00.570 に答える
3

5の15乗は30,517,578,125です

に保存できる最大値intは2,147,483,647です。

64ビット整数を使用することもできますが、double最終的に変換するときに精度の問題が発生することに注意してください。

メモリから、実行している計算に関する数論の規則があります。つまり、モジュロ結果を決定するために全電力展開を計算する必要はありません。しかし、私は間違っている可能性があります。私がそのことを学んでから何年も経ちました。

ああ、ここにあります：べき乗剰余

それを読んで、doubleand pow=）の使用をやめてください

int mod_func(int p, int g, int x)
{
    int r = g;
    for( int i = 1; i < x; i++ ) {
        r = (r * g) % p;
    }
    return r;
}
于 2012-12-19T22:02:26.527 に答える
1

INT_MAX私の推測では、問題は5 ^ 15 = 30517578125であり、これは（2147483647）よりも大きくなります。あなたは現在それをにキャストしていますint、それは失敗しているものです。

于 2012-12-19T22:01:04.720 に答える
0

言われているように、あなたの最初の問題は

int mod_func(int p, int g, int x) {
    return ((int)pow((double)g, (double)x)) % p;
}

それはpow(g,x)しばしばint範囲を超え、その結果をに変換する未定義の動作がありint、結果が何であれ、intそれが目的の係数と関係があると信じる理由はありません。

次の問題は、pow(g,x)asの結果doubleが正確でない可能性があることです。が2の累乗でない限り、数学的な結果は、範囲内であっても十分に大きい指数gとして正確に表すことはできませんが、数学的な結果が正確に表現できる場合にも発生する可能性があります（の実装によって異なります）。doublepow

数論的計算を行い、整数を法とする留数を計算する場合は、整数型のみを使用する必要があります。

手元のケースでは、すべての中間結果の残差を計算して、2乗を繰り返すことでべき乗を使用できます。モジュラスpが十分に小さく(p-1)*(p-1)、オーバーフローしない場合は、

int mod_func(int p, int g, int x) {
    int aux = 1;
    g %= p;
    while(x > 0) {
        if (x % 2 == 1) {
            aux = (aux * g) % p;
        }
        g = (g * g) % p;
        x /= 2;
    }
    return aux;
}

それをします。p大きくできる場合は、計算に幅の広いタイプを使用する必要があります。

于 2012-12-19T22:19:03.210 に答える