2

主要なテストのためにフェルマーの小定理を実装しようとしています。ここに私が書いたコードがあります：

lld expo(lld n, lld p) //2^p mod n
{
    if(p==0)
        return 1;
    lld exp=expo(n,p/2);
    if(p%2==0)
        return (exp*exp)%n;
    else
        return (((exp*exp)%n)*2)%n;
}

bool ifPseudoPrime(lld n)
{
    if(expo(n,n)==2)
        return true;
    else
        return false;
}

注:a(<=n-1) asの値を取りました2。

現在、数 n は まで大きくすることができます10^18。これは、 variableexpが に近い値に到達できることを意味します10^18。これは、エクスプレッションがオーバーフローを引き起こす(exp*exp)ほど高くなる可能性があることをさらに意味します。10^36どうすればこれを回避できますか。

これをテストしたところ、 まで問題なく動作しました10^9。私はC++を使用しています

4

2 に答える 2

8

モジュラスが、使用できる最大の整数型の限界に近い場合、状況はいくぶん複雑になります。biginteger 算術を実装するライブラリを使用できない場合は、係数を下位部分と上位部分に分割することで、剰余乗算を自分でロールすることができます。

モジュラスmが2*(m-1)オーバーフローするほど大きい場合、事態は非常に2*(m-1)厄介になりますが、オーバーフローしない場合は耐えられます。

64 ビットの符号なし整数型を使用しているとします。

係数を下位 32 ビットと上位 32 ビットに分割することで剰余積を計算できます。積は次のように分割されます。

a = a1 + (a2 << 32)    // 0 <= a1, a2 < (1 << 32)
b = b1 + (b2 << 32)    // 0 <= b1, b2 < (1 << 32)
a*b = a1*b1 + (a1*b2 << 32) + (a2*b1 << 32) + (a2*b2 << 64)

で計算a*b (mod m)するにはm <= (1 << 63)、 を法として 4 つの積のそれぞれを減らしますm。

p1 = (a1*b1) % m;
p2 = (a1*b2) % m;
p3 = (a2*b1) % m;
p4 = (a2*b2) % m;

シフトを組み込む最も簡単な方法は

for(i = 0; i < 32; ++i) {
    p2 *= 2;
    if (p2 >= m) p2 -= m;
}

p3の と の64 回の反復で同じですp4。それで

s = p1+p2;
if (s >= m) s -= m;
s += p3;
if (s >= m) s -= m;
s += p4;
if (s >= m) s -= m;
return s;

この方法はそれほど高速ではありませんが、ここで必要な数回の乗算では、十分に高速である可能性があります。シフト数を減らすことで、わずかなスピードアップが得られるはずです。最初に計算(p4 << 32) % mし、

for(i = 0; i < 32; ++i) {
    p4 *= 2;
    if (p4 >= m) p4 -= m;
}

次に、 のすべてp2、p3および の現在の値に2 32 moduloをp4掛ける必要があります。m

p4 += p3;
if (p4 >= m) p4 -= m;
p4 += p2;
if (p4 >= m) p4 -= m;
for(i = 0; i < 32; ++i) {
    p4 *= 2;
    if (p4 >= m) p4 -= m;
}
s = p4+p1;
if (s >= m) s -= m;
return s;
于 2013-05-07T19:49:43.497 に答える
0

乗算はいくつかの段階で実行できます。たとえば、X*Y mod n を計算するとします。X と Y を取り、X = 10^9*X_1 + X_0、Y = 10^9*Y_1 + Y_0 と書きます。次に、4 つの積 X_i*Y_j mod n をすべて計算し、最後に X = 10^18*(X_1*Y_1 mod n) + 10^9*( X_0*Y_1 + X_1*Y_0 mod n) + X_0*Y_0 を計算します。この場合、許容される最大サイズの半分の数値で操作していることに注意してください。

2 つの部分に分割するだけでは不十分な場合 (これが当てはまると思います)、同じスキーマを使用して 3 つの部分に分割します。3つに分割するとうまくいくはずです。

より簡単なアプローチは、学校の方法を掛けることです。これは前のアプローチに対応しますが、1 つの数値をその桁数と同じ数の部分で書きます。

幸運を！

于 2013-05-07T19:48:09.980 に答える