フェルマー素数判定

フェルマー素数判定は、ある数が素数であるかどうかを判定する確率的テストです。

フェルマーの小定理は、pが素数であり、aがpで割り切れない場合、

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

pが素数かどうかをテストしたい場合は、pで割り切れないランダムな整数aを選び、合同性が成り立つかどうかを確認します。 aの値に対して合同性が成り立たない場合、pは合成数です。 pが合成数である場合、この合同性はランダムなaに対して成立する可能性は低いです。^{[1]したがって、} aの1つ以上の値に対して等式が成立する場合、pはおそらく素数であると言えます。

ただし、合同関係はべき乗と互換性があるため、上記の合同は に対して自明に成り立つことに注意してください。同じ理由で、 pが奇数の場合もに対して自明に成り立ちます。これが、通常、区間 内のランダムなa を選択する理由です。 ${\displaystyle a\equiv 1{\pmod {p}}}$${\displaystyle a\equiv -1{\pmod {p}}}$${\displaystyle 1<a<p-1}$

そのよう な

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

nが合成数の場合、フェルマーの嘘つき数と呼ばれます。この場合、n はa を底とするフェルマー擬素数と呼ばれます。

もし、aを選んだとすると、

${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

この場合、a はnの合成性を証明するフェルマーの証拠として知られています。

n  = 221 が素数かどうかを判定したいとします。ランダムに 1 < a < 220 を選び、a  = 38 とします。上記の合同性をチェックすると、次の式が成り立つことがわかります。

${\displaystyle a^{n-1}=38^{220}\equiv 1{\pmod {221}}.}$

221 は素数であるか、38 はフェルマーの嘘つきであるため、別のa、たとえば 24 を取ります。

${\displaystyle a^{n-1}=24^{220}\equiv 81\not \equiv 1{\pmod {221}}.}$

したがって、221 は合成数であり、38 は確かにフェルマーの嘘つきでした。さらに、24 は 221 の合成数を証明するフェルマーの証人です。

アルゴリズムは次のように記述できます。

入力: n : 素数かどうかをテストする値、n >3; k : 素数かどうかをテストする回数を決定するパラメータ

出力: nが合成数の場合は合成数、そうでない場合はおそらく素数

k回繰り返します:

[2, n − 2]の範囲でランダムに選ぶ

の場合、複合値を返す${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

合成数が返されない場合は、おそらく素数を返す

等式はそれぞれすべてのnとすべての奇数のnに当てはまるため、 a値1 とn -1 は使用されず、したがって、それらをテストしても価値は追加されません。

モジュラー指数演算と倍精度乗算の高速アルゴリズムを使用すると、このアルゴリズムの実行時間はO ( k log ² n log log n ) = Õ ( k  log ² n )になります。ここで、k はランダムなaをテストする回数、n は素数かどうかをテストする値です。詳細については、 Miller–Rabin 素数性テストを参照してください。

任意の基底a > 1に対して、フェルマー擬素数は無限に存在します。^{[1] ：定理 1}さらに悪いことに、カーマイケル数 も無限に存在します。 ^[2]これらは、 のすべての値がフェルマーの嘘つきとなる数です。これらの数に対して、フェルマー素数判定を繰り返し適用すると、因数に対する単純なランダム検索と同じ結果になります。カーマイケル数は素数よりもかなり少ないですが (カーマイケル数の個数に対するエルデシュの上限値^[3]は素数関数 n/log(n)よりも低い)、その数は十分にあるため、上記の形式ではフェルマーの素数判定はあまり使用されません。代わりに、ベイリー–PSW、ミラー–ラビン、ソロベイ–シュトラッセンなど、フェルマー判定のより強力な拡張がより一般的に使用されています。 ${\displaystyle n}$${\displaystyle a}$${\displaystyle \operatorname {gcd} (a,n)=1}$

一般に、がカーマイケル数でない合成数である場合、少なくとも全体の半分は ${\displaystyle n}$

${\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$（つまり）${\displaystyle \operatorname {gcd} (a,n)=1}$

はフェルマーの証人です。このことを証明するために、 をフェルマーの証人とし、、 、 ...をフェルマーの嘘つきとします。すると、 ${\displaystyle a}$${\displaystyle a_{1}}$${\displaystyle a_{2}}$${\displaystyle a_{s}}$

${\displaystyle (a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}}$

そして、すべてがフェルマーの証人です。 ${\displaystyle a\cdot a_{i}}$${\displaystyle i=1,2,...,s}$

前述のように、ほとんどのアプリケーションは素数判定にミラー・ラビンまたはベイリー・PSWテストを使用します。パフォーマンスを向上させるために、フェルマー テスト (および小さな素数による試し割り) が最初に実行されることも あります。バージョン 3.0 以降のGMP では、試し割りの後、ミラー・ラビン テストを実行する前に、基数 210 のフェルマー テストを使用します。Libgcrypt はフェルマー テストに基数 2 の同様のプロセスを使用しますが、OpenSSL は使用しません。

実際には、GMPなどの大部分の大きな数値ライブラリでは、フェルマーテストはミラー・ラビンテストよりも著しく高速ではなく、多くの入力に対して遅くなる可能性があります。^[4]

例外として、OpenPFGW は、素数検定にフェルマー検定のみを使用します。このプログラムは通常、数千桁の入力で使用され、非常に大きな入力での最大速度を目標としています。フェルマー検定のみを使用するもう 1 つの有名なプログラムはPGPで、自己生成の大きなランダム値の検定にのみ使用されます (オープンソースの同等プログラムであるGNU Privacy Guard は、フェルマーの事前検定に続いてミラー・ラビン検定を使用します)。

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein (2001)。「セクション 31.8: 素数判定」。アルゴリズム入門(第 2 版)。MIT Press、McGraw-Hill。p. 889–890。ISBN 0-262-03293-7。{{cite book}}: CS1 maint: multiple names: authors list (link)