NumberTheory`PrimeQ`

このパッケージは素数の証明を実装する．ProvablePrimeQ[n]がTrueを返したら，数が素数であることが数学的に証明できる．また，PrimeQCertificate[n]はが素数または合成数であること検証するために用いることができる証明書を表示する．組込みの素数判定用関数PrimeQは実際には数が素数である証明は返さない．しかし，現時点でPrimeQが失敗する例は知られていない．

素数または合成数の証明

このパッケージに含まれる関数は素数を証明するだけでなく，素数であることの「証明書」も生成する．素数証明書は，素数であることを証明するために簡単に使うことができる比較的短いデータである．「簡単に」と言うのは，このデータを使って素数であることを証明することが，最初にデータを生成することよりもはるかに簡単で速いということである．証明書の簡単な例として，合成数の因数は合成数であることの証明となるということが挙げられる．それらが因数であるということを証明するためにその数を掛け合わせることの方が，因数を求めること自体よりもはるかに簡単なのである．この証明書には，証明書を生成するアルゴリズムの内部的なメカニズムをユーザが信頼しなくてもよいという利点がある．どのようなシステムにおいても，このような証明書が素数であることを証明しているということを検証するプログラムを書くことは非常に容易である．

パッケージをロードする．

In[1]:= <<NumberTheory`PrimeQ`

PrimeQ は1093が素数であるという結果を返す．

In[2]:= PrimeQ[1093]

Out[2]=

ProvablePrimeQ は同じ結果を返すが，こちらには証明書がある．

In[3]:= ProvablePrimeQ[1093]

Out[3]=

証明書を表示する．

In[4]:= PrimeQCertificate[1093]

Out[4]=

証明書を直接表示する．

In[5]:= ProvablePrimeQ[1093, Certificate->True]

Out[5]=

このパッケージで用いられる大きな数nについての素数証明書は，楕円曲線理論に基づいている．基本的な構想はS. GoldwasserおよびJ. Kilianによって「Almost All Primes Can Be Quickly Certified」（Proc. 18th STOC，1986，pp. 316-329）で発見された．彼らのアルゴリズムは理論的な証明のみであったが，A. O. L. Atkinは虚数乗法の考えを用いてこれを実際的なものにする方法を見付けた．虚数情報とは数論の一部で，複素解析，ガロア(Galois)理論，モジュラ形式を組み合わせたものである．F. Morainは「Implementation of the Atkin-Goldwasser-Kilian Primality Testing Algorithm」（INRIA Research Report, # 911，1988年10月）でこの方法の実装に成功した．1989年11月にはMorainは1065桁の数の素数証明を得ることに成功した．この数は特別な目的のアルゴリズムを必要とすることなく判定された最初の大きな素数（桁以上）である．その後，AtkinおよびMorainはこのアルゴリズムを拡張した論文を書いた．それが，A. O. L. Atkin，F. Morain共著「Elliptic Curves and Primality Proving」（Mathematics of Computation，1993，29-68）である．

素数判定と楕円曲線の入門書としてはD. Bressoud著「Factorization and Primality Testing」（Springer-Verlag出版，1989）を参照されたい．

このパッケージは，合成数について合成数証明書を生成するために用いることもできる．このような証明書は，素数について真であることが与えられた数については真でないという簡単な性質を示すことに基づいている．例えばPrimeQCertificate[3837523]は証明書{2, 3837522, 3837523}を返すが，これはが1ではないことを示すことを意図している．

ProvablePrimeQ[n]はnが素数であるかないかに応じてTrueまたはFalseを返す．この素数または合成数の証明書はPrimeQCertificate[n]が生成する．ProvablePrimeQはPrimeQCertificateを呼び出し，結果を保存する．そのため，ProvablePrimeQが解を返した後で証明書を作成するための付加的な時間を必要としない．PrimeQCertificateが発行した証明書はPrimeQCertificateCheckで確認できる．この関数は証明書が素数であることを述べているのか合成数であることを述べているのかを認識し，それを検証するために証明書を用いる．

素数証明書を表示する．

In[6]:= ProvablePrimeQ[1093,
Certificate -> True]

Out[6]=

証明書を使って素数性を証明する．

In[7]:= PrimeQCertificateCheck[Last[%], 1093]

Out[7]=

次は合成数の証明書である．合成数の証明書は必ず3つの整数のリストであるので，この証明が合成数の証明であることが分かる．

In[8]:= PrimeQCertificate[1093 * 3511]

Out[8]=

合成数であることを検証する．

In[9]:= PrimeQCertificateCheck[%, 3837523]

Out[9]=

組込み関数PrimeQは，まず小さな素数で割り切れるかどうかを判定する．その後ミラー・ラビン(Miller-Rabin)の強擬似素数テストを2または3を底として行い，さらにルーカス(Lucas)のテストを行う．1998年に，この手順はについてのみ正しいということが分かった．従って，大きい数にこの手順を用いた場合，素数であるにもかかわらず合成数であるという結果が返される可能性があることが分かる．しかし，PrimeQ[n]がFalseを返した場合は，数は間違いなく合成数である．従ってPrimeQ[n]が失敗する可能性があるのは，が合成数であるにもかかわらずPrimeQ[n]がは素数であるという結果を返したときである．PrimeQは決定論的であるということに注意していただきたい．つまり，計算に乱数は使用されないということである．

このパッケージは，組込み関数PrimeQに取って代わるようには意図されていない．むしろ数が素数であることを確実にすることを可能にするためのものである．このパッケージは数論的な作業がすべて終了した後で，結果を保証するために用いるべきである．例えば，整数の因数分解アルゴリズムの主要な判定にProvablePrimeQを用いるのは間違いである．それよりも，PrimeQを主要判定に使い，因数分解が行われた後でアルゴリズムが返した素因数の素数性を証明するためにProvablePrimeQを用いるという使い方がよいだろう．これは一般にPrimeQの方がProvablePrimeQよりも数段速く計算を行うからである．

前述のように，PrimeQの結果は正しくない可能性がある．換言すると，本当は合成数である数を素数であると判定してしまうことがあるということである．ProvablePrimeQがこれを常に検知できるかどうかは分からない．検知できた場合はPrimeQに対する反証を示す警告メッセージとFalseが返される．これは既知の合成数についてPrimeQ[n]をTrueに設定することでシミュレートできる．

PrimeQが正しくない答を返すように設定する．ProvablePrimeQはPrimeQの誤りを検出し，警告メッセージと正しい答を返す．

In[10]:= (Unprotect[PrimeQ];
PrimeQ[38200901201] = True;
ProvablePrimeQ[38200901201])

SqrtMod::fail: Warning: $IterationLimit exceeded; PrimeQ[38200901201] may be incorrect.



PrimeQCertificate::qrsqrtmod:

Failure of elliptic curves certificate for p = 38200901201. Unable to find quadratic representation 4*p = u^2 + 7*v^2 due to failure of SqrtMod[-7 , p].



PrimeQCertificate::false:

Warning: PrimeQCertificate has detected a counterexample to PrimeQ:

PowerMod[3, 38200901200, 38200901201] != 1.

Out[10]=False

ProvablePrimeQとPrimeQCertificateのオプション

がオプションSmallPrimeの値より大きいとき，ProvablePrimeQは前述のようにAtkin-Morainのテストを行う．与えられた数が効率的な因数分解アルゴリズムの範囲内であるとき，この素数判定アルゴリズムは最適とはならない．この場合，「Every Prime Has a Succinct Certificate」（SIAM Journal of Computation 4 ，1975，pp. 214-220）のV. Prattの手法の方が適している．Mathematica でのこのアルゴリズムの実装についてはS. Wagon著「Mathematica in Action」（W. H. Freeman出版，1991）のセクション8.7に述べられている．

PrimeQCertificateを使って証明書を確認する場合，ProvablePrimeQまたはPrimeQCertificateを使って証明書を生成したときと同じSmallPrimeの値を用いなければならない．

SmallPrimeのデフォルト値が指定の数より大きいので，プラット(Pratt)の素数性証明書が返される．

In[11]:= PrimeQCertificate[3511]

Out[11]=

大きな数については証明は非常に長く複雑になることがある．

In[12]:= PrimeQCertificate[10^20 + 39]

Out[12]=