ポックリントン素数判定

数学において、ポックリントン・レーマー素数判定は、ヘンリー・ケーボーン・ポックリントン^[1]とデリック・ヘンリー・レーマー^[2]によって考案された素数判定である。この判定では、整数が素数であることを証明するため に の部分因数分解を使用する。 ${\displaystyle N-1}$${\displaystyle N}$

これは、 の完全な因数分解を必要とするルーカス素数判定よりも少ない労力で素数証明を生成します。 ${\displaystyle N-1}$

テストの基本バージョンは、次のように定式化されるポックリントン定理（またはポックリントン基準）に基づいています。

を整数とし、自然数aとpが存在し、 ${\displaystyle N>1}$

するとNは素数となる。^[3]ここで、はkで割った余りを求めた後、iとjが等しいことを意味し、はiがjの約数であることを意味し、gcdは最大公約数である。 ${\displaystyle i\equiv j{\pmod {k}}}$${\displaystyle i\vert j}$

注: 式 ( 1 ) は、単にフェルマーの素数判定です。aの値がNで割り切れず、式 ( 1 ) が偽である場合、 N は素数ではないとすぐに結論付けることができます。(この割り切れる条件は、式 ( 3 )によって暗示されるため、明示的には述べられていません。) たとえば、 とします。 の場合、 となります。これは、 Nが素数でないことを証明するのに十分です。 ${\displaystyle N=35}$${\displaystyle a=2}$${\displaystyle a^{N-1}\equiv 9{\pmod {N}}}$

Nが与えられたとき、定理の条件を満たすpとa が見つかる場合は、Nは素数です。さらに、ペア ( p、a ) は素数証明書を構成し、定理の条件を満たすことをすぐに検証できるため、N が素数であることが確認できます。

主な難しさは、( 2 )を満たすpの値を見つけることです。まず、大きな数の大きな素因数を見つけることは通常困難です。次に、多くの素数Nに対して、そのようなpは存在しません。たとえば、、およびであるため、適切なpは存在しません。これは、( 2 )の不等式に違反します。他の例としては 、およびがあります。 ${\displaystyle N=17}$${\displaystyle N-1=2^{4}}$${\displaystyle p=2<{\sqrt {N}}-1}$${\displaystyle N=19,37,41,61,71,73,}$${\displaystyle 97}$

pが与えられれば、 a を見つけることはそれほど難しくありません。^[4] Nが素数の 場合、フェルマーの小定理により、区間内の任意のa は( 1 )を満たします(ただし、 および の場合は自明であり、 ( 3 ) を満たしません)。このa は、 ord( a ) がを割り切らない限り、 ( 3 )を満たします。したがって、区間内でランダムに選択されたa が機能する可能性は高くなります。aがN を法とするジェネレータである場合、その順序は⁠ ⁠であるため、この選択に対してこの方法が機能することが保証されます。 ${\displaystyle 1\leq a\leq N-1}$${\displaystyle a=1}$${\displaystyle a=N-1}$${\displaystyle (N-1)/p}$${\displaystyle 2\leq a\leq N-2}$${\displaystyle N-1}$

ポックリントンの定理の上記のバージョンは、 を割り切る素数が存在しないような素数が存在するため、適用できない場合があります。次のポックリントンの定理の一般化されたバージョンは、より広く適用できます。^{[5] ：系1}${\displaystyle N}$${\displaystyle p}$${\displaystyle N-1}$${\displaystyle p>{\sqrt {N}}-1}$

定理: N  − 1をN  − 1 =  ABとして因数分解します。ここでAとB は互いに素であり、 Aの素因数分解は既知ですが、Bの因数分解は必ずしも既知ではありません。 ${\displaystyle A>{\sqrt {N}}}$

Aの各素因数pに対して、 ${\displaystyle a_{p}}$

N は素数です。

ポックリントン・レーマー素数判定法は、この系から直接導かれる。この系を使うには、まずN  − 1の因数を十分多く見つけて、それらの因数の積が を超えるようにする。この積を A と呼ぶ。次に、N  − 1の残りの因数分解されていない部分をB = ( N  − 1)/ Aとする。 Bが素数かどうかは問題ではない。 Aを割り切る素数はBも割り切れないこと、つまりAとBは互いに素であることを確認する必要があるだけである。次に、 Aのすべての素因数pに対して、系の条件( 6 )と( 7 )を満たす を見つける。そのようなs が見つかる場合、系はNが素数であることを意味する。 ${\displaystyle {\sqrt {N}}}$${\displaystyle a_{p}}$${\displaystyle a_{p}}$

コブリッツによれば、= 2 がしばしば機能する。^[3]${\displaystyle a_{p}}$

かどうかを判断する

${\displaystyle N=27457}$

素数です。

まず、の小さな素因数を探します。すぐに次のことがわかります。 ${\displaystyle N-1}$

${\displaystyle N-1=2^{6}\cdot 3\cdot B=192\cdot B}$。

および が系の条件を満たす かどうかを判定する必要があります。なので、 となります。したがって、を適用するにはを十分に因数分解しました。 であることも検証する必要があります。 ${\displaystyle A=192}$${\displaystyle B=(N-1)/A=143}$${\displaystyle A^{2}=36864>N}$${\displaystyle A>{\sqrt {N}}}$${\displaystyle N-1}$${\displaystyle \gcd {(A,B)}=1}$

Bが素数であるかどうかは問題ではありません(実際は素数ではありません)。

最後に、 Aの各素因数pに対して試行錯誤を繰り返し、( 6 )と( 7 )を満たすap_を見つけます。

については、 を試してください。この高いべき乗は、2 進累乗法を使用して効率的に実行できます。 ${\displaystyle p=2}$${\displaystyle a_{2}=2}$${\displaystyle a_{2}}$

${\displaystyle a_{2}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$

${\displaystyle \gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(2^{13728}-1,27457)}=27457}$。

したがって、は( 6 )を満たしますが、( 7 )は満たしません。各pに対して異なるapが許可されているので、_代わりに次を試してください。 ${\displaystyle a_{2}=2}$${\displaystyle a_{2}=5}$

${\displaystyle a_{2}^{N-1}\equiv 5^{27456}\equiv 1{\pmod {27457}}}$

${\displaystyle \gcd {(a_{2}^{(N-1)/2}-1,N)}=\gcd {(5^{13728}-1,27457)}=1}$。

したがって、( 6 )と( 7 )の両方を満たします。 ${\displaystyle a_{2}=5}$

Aの 2 番目の素因数である については、次を試してください。 ${\displaystyle p=3}$${\displaystyle a_{3}=2}$

${\displaystyle a_{3}^{N-1}\equiv 2^{27456}\equiv 1{\pmod {27457}}}$。

${\displaystyle \gcd {(a_{3}^{(N-1)/3}-1,N)}=\gcd {(2^{9152}-1,27457)}=1}$。

${\displaystyle a_{3}=2}$（６）と（７）の両方を満たす。

これで が素数である証明が完了します。 が素数であることの証明は、(2, 5) と (3, 2) の 2 つのペアで構成されます。${\displaystyle N=27457}$${\displaystyle N=27457}$${\displaystyle (p,a_{p})}$

この例では小さな数を選択しましたが、実際にはA を因数分解し始めると、因数自体が非常に大きく、素数であることが明白でない場合があります。 A の因数が素数であることを証明しなければ、 N が素数であることを証明することはできません。このような場合、すべての素数が妥当なしきい値を下回るまで、 Aの大きな因数に対して同じテストを再帰的に使用します。

この例では、2 と 3 が素数であると確実に言えるため、結果が証明されました。素数証明は、系で簡単に確認できるペアのリストです。 ${\displaystyle (p,a_{p})}$

この例に大きな素因数が含まれていた場合、証明書はより複雑になります。証明書は、まずAの「素」因数に対応するa _pの初期ラウンドで構成されます。次に、素数かどうか不明なAの各因数について、さらにa _{p を}作成し、これらの因数の因数についてこれを繰り返して、素数かどうかが確実な因数に到達します。最初の素数が大きい場合は、これを多くの層にわたって続けることができますが、重要な点は、各レベルでテストする素数と、簡単に検証できる 対応するa _{pを含む証明書を作成できることです。}

1975 年の Brillhart、Lehmer、Selfridge による論文^[5]では、623 ページの定理 4 として、上で「一般化された Pocklington 定理」として示したものの証明が示されています。因数分解を少なくする追加の定理も示されています。これには、定理 3 (1878 年の Proth の定理を強化したもの) が含まれます。

となる奇数の素数pがあるとします。 となるaが存在する場合、 であるが、となる場合、Nは素数です。${\displaystyle N-1=mp}$${\displaystyle 2p+1>{\sqrt {N}}}$${\displaystyle a^{(N-1)/2}\equiv -1{\pmod {N}}}$${\displaystyle a^{m/2}\not \equiv -1{\pmod {N}}}$

Nが大きい場合、上記の系を適用できるほど十分に を因数分解することが難しい場合が多い。ブリルハート、レーマー、セルフリッジの論文の定理 5 は、因数分解された部分が にしか達していない場合でも素数性の証明を可能にする。 、、、およびの部分因数分解に基づいてNの素数性を証明できるような多くの追加の定理が提示されている。^{[5] [6] [7]}${\displaystyle N-1}$${\displaystyle (N/2)^{1/3}}$${\displaystyle N-1}$${\displaystyle N+1}$${\displaystyle N^{2}+1}$${\displaystyle N^{2}\pm N+1}$

• レナード・ユージン・ディクソン、「数論の歴史」第 1 巻、370 ページ、チェルシー出版、1952 年
• ヘンリー・ポックリントン、「Math. Quest. Educat. Times」、(2)、25、1914年、p 43-46（「エデュケーショナル・タイムズ」の数学コラムの続きである数学の問題と解答。）

• Chris Caldwell、「素数証明 3.1: n-1 テストと Fermats の Pepin テスト」、Prime Pagesにて。
• Chris Caldwell、「素数証明 3.2: n+1 テストとメルセンヌの Lucas-Lehmer テスト」、Prime Pagesにて。