ペパンのテスト

数学において、ペパンの判定法は素数判定法の一つであり、フェルマー数が素数であるかどうかを判定するために用いられる。これはプロスの判定法の変形である。この判定法は、フランスの数学者テオフィル・ペパンにちなんで名付けられた。

させて${\displaystyle F_{n}=2^{2^{n}}+1}$n番目のフェルマー数をとする。ペパンの判定法によれば、n > 0 の場合、

${\displaystyle F_{n}}$素数であるのは、${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}$

その表現${\displaystyle 3^{(F_{n}-1)/2}}$を法として評価できます${\displaystyle F_{n}}$繰り返し二乗することで、このテストは高速な多項式時間アルゴリズムとなる。しかし、フェルマー数は非常に急速に増加するため、妥当な時間と空間でテストできるフェルマー数はごくわずかである。

3の代わりに他の基数を使用することもできます。これらの基数は次のとおりです。

3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160, ... ( OEISの配列A129802 )。

上記の数列に含まれる素数はエリート素数と呼ばれ、以下の通りです。

3、5、7、41、15361、23041、26881、61441、87041、163841、544001、604801、6684673、14172161、159318017、446960641、1151139841、3208642561、38126223361、108905103361、171727482881、318093312001、443069456129、912680550401、...（OEISの配列A102742）

整数b > 1 の場合、基数b は、有限個のフェルマー数F _{n が}以下の条件を満たす場合に限り使用できます。${\displaystyle \left({\frac {b}{F_{n}}}\right)=1}$、 どこ${\displaystyle \left({\frac {b}{F_{n}}}\right)}$はヤコビ記号です。

実際、ペパンのテストはフェルマー数のオイラー・ヤコビのテストと同じである。ヤコビ記号${\displaystyle \left({\frac {b}{F_{n}}}\right)}$−1 であるということは、上記の基底に対してオイラー・ヤコビ擬素数となるフェルマー数は存在しないということである。

十分性:合同条件が満たされていると仮定します。

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$

保持する。それから${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$したがって、3を法とする乗法の位数は${\displaystyle F_{n}}$分ける${\displaystyle F_{n}-1=2^{2^{n}}}$これは2のべき乗です。一方、この順序は割り切れません。${\displaystyle (F_{n}-1)/2}$したがって、それは等しくなければならない${\displaystyle F_{n}-1}$特に、少なくとも${\displaystyle F_{n}-1}$以下の数字${\displaystyle F_{n}}$互いに素な${\displaystyle F_{n}}$、そしてこれは、${\displaystyle F_{n}}$素数です。

必要性:${\displaystyle F_{n}}$は素数である。オイラーの基準によれば、

${\displaystyle 3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$、

どこ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$はルジャンドル記号です。繰り返し二乗すると、次のようになります。${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$、 したがって${\displaystyle F_{n}\equiv 2{\pmod {3}}}$、 そして${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$。 として${\displaystyle F_{n}\equiv 1{\pmod {4}}}$結論として${\displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$二次相互法則から。

フェルマー数の希少性のため、ペパンテストはこれまでに8回しか実行されていません（素数性がすでに判明していないフェルマー数に対して）。^{[ 1 ] [ 2 ] [ 3 ]} メイヤー、パパドプロス、クランドールは、実際には、まだ未確定のフェルマー数の大きさのため、ペパンテストを妥当な時間内に実行できるようになるには、かなりの技術進歩が必要になるだろうと推測しています。^{[ 4 ]}

• P. ペパン、『公式について』${\displaystyle 2^{2^{n}}+1}$、Comptes rendus de l'Académie des Sciences de Paris 85 (1877)、329–333 ページ 。

• プライム用語集：ピピンのテスト