素数証明書

数学とコンピュータ サイエンスにおいて、素数証明書または素数証明は、数が素数であることの簡潔で正式な証明です。素数証明書を使用すると、コストがかかったり信頼性が低い素数テストを実行したりすることなく、数の素数を迅速に確認できます。「簡潔」とは、通常、証明が数自体の桁数よりも多項式的に大きくなければならないことを意味します(たとえば、数がbビットの場合、証明にはおよそb ²ビットが含まれます)。

素数性証明は、素数判定や整数の補因分解などの問題がNPに属することの証明に直接つながります。NPは、解が与えられれば多項式時間で検証可能な問題のクラスです。これらの問題は、すでに自明にco-NPに属しています。これは、これらの問題がNP 完全ではないことを示す最初の強力な証拠でした。なぜなら、もし NP 完全であれば、NP は co-NP のサブセットであることを意味しますが、これは広く誤りであると信じられている結果です。実際、これは、当時 P に属することが知られていなかった NP 交差 co-NP の問題の最初の実証でした。

補数問題に対する証明書の作成、つまり、ある数が合成数であることを証明することは簡単です。非自明な約数を与えるだけで十分です。ベイリー-PSW 素数判定テスト、フェルマー素数判定テスト、ミラー-ラビン素数判定テストなどの標準的な確率的素数判定テストでも、入力が合成数である場合に合成数証明書が作成されますが、素数入力の場合は証明書は作成されません。

素数性証明書の概念は、歴史的には1975年にヴォーン・プラット^{[1]によって考案された}プラット証明書によって導入されました。プラット証明書の構造を説明し、多項式サイズを持ち、多項式時間で検証可能であることを証明しました。これはルーカス素数性テストに基づいており、これは本質的にフェルマーの小定理の逆であり、それを真にするための条件が追加されています。

ルーカスの定理: 次のような整数aがあるとします:

• a ^{n − 1} ≡ 1 (mod n )、
• n − 1のすべての素因数qに対して、 a ^{( n  − 1)/ q} ≡ 1 (mod n )となるわけではありません。

するとnは素数になります。

このようなa (証人と呼ばれる) とn − 1の素因数分解が与えられれば 、上記の条件を素早く簡単に検証できます。すべての整数の素因数はビット数よりも少ないため、線形数のモジュラー指数演算を実行するだけで済み、これらのそれぞれはO(log n ) 回の乗算で平方根による累乗によって実行できます ( big-O 表記法を参照)。小学校で習う整数乗算でも、これは O((log n ) ⁴ ) 時間しかありません。David Harvey と Joris van der Hoeven による最もよく知られた漸近実行時間を持つ乗算アルゴリズムを使用すると、これを O((log n ) ³ (log log n )) 時間まで短縮できます。または、ソフト O 表記法Õ((log n ) ³ ) を使用します。

しかし、合成数を含むn − 1の「素因数分解」を与えることで、検証者を騙して合成数を受け入れさせることは可能です 。たとえば、a  = 4 とn − 1 = 6 × 14 を「素因数分解」として 与え、n = 85 が素数であると主張するとします。この場合 ( q  = 6 とq = 14 を使用 )、次のようになります。

• 4は85と互いに素である。
• 4 ⁸⁵⁻¹ ≡ 1 (mod 85)、
• 4 ^(85−1)/6 ≡ 16 (mod 85)、4 ^(85−1)/14 ≡ 16 (mod 85)。

85 は素数であると誤って結論付けてしまいます。検証者に単純に因数分解を強制したくはありません。そのため、この問題を回避するより良い方法は、元の問題のより小さな例であるn − 1 の素因数ごとに素数証明書も提供することです。この方法で、2 などの素数であることがわかっている数に達するまで再帰的に続けます。最終的には、それぞれが証人a に関連付けられた素数のツリーが作成されます。たとえば、数 229 の完全な Pratt 証明書は次のとおりです。

• 229 ( a  = 6, 229 − 1 = 2 ²  × 3 × 19)、
  • 2（既知の素数）、
  • 3 ( a  = 2, 3 − 1 = 2)、
    • 2（既知の素数）、
  • 19 ( a  = 2, 19 − 1 = 2 × 3 ² )、
    • 2（既知の素数）、
    • 3 ( a  = 2, 3 − 1 = 2)、
      • 2（既知の素数）。

この証明木は、プラットの定理2に基づく簡単な帰納的証明によって、最大で2以外の値を含むことが示されます。結果は3の場合にも当てはまります。一般に、 p > 3を取り、その木の子をp ₁、...、p _kとします。帰納的仮説により、 p _{i を}根とする木には最大で値が含まれるため、木全体には最大で ${\displaystyle 4\log _{2}n-4}$${\displaystyle 4\log _{2}p_{i}-4}$

${\displaystyle 1+\sum _{i=1}^{k}(4\log _{2}p_{i}-4)=-4k+4\log _{2}p_{1}\cdots p_{k}\leq 4\log _{2}p-4,}$

k ≥ 2、p ₁ ... p _k = p − 1 であるためです 。各値は最大で log nビットであるため、証明書のサイズは O((log n ) ² ) ビットであることも示しています。

2 以外のO(log n ) 値があり、それぞれを検証するには最大で 1 回の累乗が必要です (累乗が実行時間の大部分を占めます)。そのため、合計時間は O((log n ) ³ (log log n )(log log log n ))、つまり Õ((log n ) ³ ) となり、これは計算数論者が通常扱う範囲の数値に対しては十分に実現可能です。

しかし、理論的には有用で検証も容易である一方、実際にnの Pratt 証明書を生成するには、 n − 1 やその他の潜在的に大きな数を因数分解する必要があります。これはフェルマー素数 などの特殊な数の場合は簡単ですが、現在のところ、一般的な形式の大きな素数の場合は単純な素数判定よりもはるかに困難です。

より大きな数の効率的な証明書生成の問題に対処するため、1986 年にShafi Goldwasserと Joe Kilian は楕円曲線の理論に基づいた新しいタイプの証明書を説明しました。^[2]これはAOL Atkinと François Morainによって Atkin-Goldwasser-Kilian-Morain 証明書の基礎として使用されました。これは楕円曲線素数証明システムによって生成および検証されるタイプの証明書です。^[3] Pratt 証明書が Lucas の定理に基づいているのと同様に、Atkin–Goldwasser–Kilian–Morain 証明書は Goldwasser と Kilian の次の定理に基づいています (「ほとんどすべての素数は迅速に証明できる」の補題 2)。

定理: 以下が与えられたと仮定します:

• 2 または 3 で割り切れない正の整数n 。
• M _x、M _y、A、B ( nを法とする整数) で、 M _y ² = M _x ³ + AM _x + B を満たし、 4A ³ + 27B ^2がnと互いに素であるもの。${\displaystyle \mathbb {Z} _{n}}$
• 素数。${\displaystyle q>n^{1/2}+1+2n^{1/4}}$

このとき、M = (M _x , M _y )は、楕円曲線y ² = x ³ + Ax + B上の非単位元です。k M を、標準的な楕円曲線加算を使用してM に k 回加算したものとします。q Mが単位元 I である場合、nは素数です。

技術的には、楕円曲線は体上でのみ構築でき、nが素数である場合にのみ体となるため、証明しようとしている結果を仮定しているように見えます。問題は、体には存在しない可能性のある逆元を取る楕円曲線加算アルゴリズムで発生します。ただし、曲線が明確に定義されているかのように計算を実行し、逆元のない要素を反転しようとしない場合は、結果は依然として有効であることが示されます (「ほぼすべての素数はすぐに証明できます」の補題 1)。逆元のない要素に遭遇した場合、n は合成元であることが証明されます。 ${\displaystyle \mathbb {Z} _{n}}$${\displaystyle \mathbb {Z} _{n}}$

この定理から証明書を導くには、まず M _x、 M _y、 A、 B、qをエンコードし、次にq < nの素数証明を再帰的にエンコードし、既知の素数に達するまで続けます。この証明書のサイズは O((log n ) ² ) で、 O((log n ) ⁴ ) 時間で検証できます。さらに、これらの証明書を生成するアルゴリズムは、ごく一部の素数を除いてすべてに対して期待される多項式時間であることが示されており、この割合は素数のサイズとともに指数関数的に減少します。したがって、このアルゴリズムは、証明可能な有効なRSAキーの生成などの暗号化アプリケーションで重要なアプリケーションである、証明された大きなランダムな素数を生成するのに適しています。

ポックリントンの定理の変形（ポックリントン素数性テストを参照）^[4]に基づく証明可能素数生成は、素数を生成するための効率的な手法（コストは一般に確率的生成よりも低い）であり、素数証明が組み込まれているという利点もあります。これらは特別な素数のように見えるかもしれませんが、ポックリントンに基づく証明可能生成アルゴリズムを使用してすべての素数を生成できることに注目してください。

0より大きい整数と証拠を持つ異なる素数があると します。${\displaystyle P=Rh+1}$${\displaystyle R=\prod q_{j}^{e_{j}}}$${\displaystyle q_{j}}$${\displaystyle e_{j}}$${\displaystyle g}$

次のいずれかが成り立つ場合、P は素数です。

ポックリントン素数証明は、素数 P、を割り切る素数の集合（それぞれが独自のポックリントン素数証明を持つか、素数として知られているほど小さい）、および証人から構成されます。 ${\displaystyle q_{j}}$${\displaystyle (P-1)}$${\displaystyle g}$

この証明書に必要なビット数（および計算コストの順序）は、バージョン（b）ではおよそ からバージョン（a） ではおよそ の範囲になります。${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{3^{k}}}\right)=1.5\log _{2}{P}}$${\displaystyle \log _{2}{P}\left(1+\sum _{k=1}^{\infty }{\frac {1}{2^{k}}}\right)=2\log _{2}{P}}$

と します。および であることに注意してください。${\displaystyle P=1056893}$${\displaystyle (P-1)=1621\cdot 163\cdot 2^{2}}$${\displaystyle P^{1/2}=1028.053\ldots }$${\displaystyle P^{1/3}=101.86156\ldots }$

• 「証人」2 を使用すると、式1が満たされ、および2を使用して式 3 が満たされます。${\displaystyle q=163}$${\displaystyle q=1621}$
• バージョンaの場合、証明書には のみが必要です。${\displaystyle P=1056893,\ q=1621,\ g=2}$
• バージョンbの場合、証明書には のみが必要ですが、もう少し作業が必要です。 ${\displaystyle P=1056893,\ q=163,\ g=2}$
  • ${\displaystyle h=(1056893-1)/163=6484}$
  • ${\displaystyle a\equiv h\equiv 127{\bmod {163}}}$そして${\displaystyle b=\left(6484-127\right)/163=39}$
  • 使用が失敗する:${\displaystyle r=3}$${\displaystyle \left(127^{2}-4\cdot 39\right)^{(3-1)/2}\equiv (1^{2}-0)^{1}\equiv 1{\bmod {3}}}$
  • を使用すると成功します: 、および は素数です。${\displaystyle r=5}$${\displaystyle \left(127^{2}-4\cdot 39\right)^{(5-1)/2}\equiv (2^{2}-1)^{2}\equiv 2{\bmod {5}}}$${\displaystyle P}$

「素数はPに含まれる」^[7]は理論計算機科学における画期的な発見でした。 2002年8月にManindra Agrawal、Nitin Saxena、Neeraj Kayalによって発表されたこの論文は、数の素数性をチェックするという有名な問題が多項式時間で決定論的に解決できることを証明しています。著者らはこの研究により 2006年のゲーデル賞と2006年のフルカーソン賞を受賞しました。

AKS 素数性テストを使用して多項式時間で決定論的に素数性テストを実行できるようになったため、素数自体が素数であることの証明書と見なすことができます。このテストは Õ((log n ) ⁶ ) 時間で実行されます。実際には、この検証方法は Pratt 証明書の検証よりもコストがかかりますが、証明書自体を決定するための計算は必要ありません。

• Mathworld: 素数証明
• Mathworld: プラット証明書
• Mathworld: アトキン・ゴールドワッサー・キリアン・モレイン証明書
• 素数用語集: 素数証明書
• Vašek Chvátal . Pratt の素数証明に関する講義ノート。ラトガース大学コンピュータサイエンス学部。コンコルディア大学の PDF 版。