PRIMALITY PROVING パッケージ チュートリアル

素数証明パッケージ

このパッケージは素数の証明を実装する.ProvablePrimeQ[n]Trueを返したら,数 が素数であることが数学的に証明できる.また,PrimeQCertificate[n] が素数または合成数であること検証するために用いることができる証明書を表示する.

ProvablePrimeQ[n]n が素数であることが証明できる場合はTrueを,合成数であることが証明できる場合はFalseを返す
ProvablePrimeQ[n, "Certificate"->True]結果の検証に使用できる証明書を表示する
PrimeQCertificate[n]n が素数である証明書,または n が合成数であることの証明書を表示する
PrimeQCertificateCheck[cert,n]証明書 cert が,n が素数または合成数であることを証明しているかどうかを検証する

素数または合成数の証明

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

パッケージをロードする.
In[1]:=
Click for copyable input
PrimeQは1093が素数であるという結果を返す.
In[2]:=
Click for copyable input
Out[2]=
ProvablePrimeQは同じ結果を返すが,こちらには証明書がある.
In[3]:=
Click for copyable input
Out[3]=
証明書を表示する.
In[4]:=
Click for copyable input
Out[4]=
証明書を直接表示する.
In[5]:=
Click for copyable input
Out[5]=

このパッケージで用いられる大きな数 n についての素数証明書は,楕円曲線理論に基づいている.

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

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

素数証明書を表示する.
In[6]:=
Click for copyable input
Out[6]=
証明書を使って素数性を証明する.
In[7]:=
Click for copyable input
Out[7]=
次は合成数の証明書である.合成数の証明書は必ず3つの整数のリストであるので,この証明が合成数の証明であることが分かる.
In[8]:=
Click for copyable input
Out[8]=
合成数であることを検証する.
In[9]:=
Click for copyable input
Out[9]=

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

オプション名
デフォルト値
"SmallPrime"10^50AtkinMorain素数テストの使用のための下限
"Certificate"False証明書を表示するかどうかを指定する
"PollardPTest"Automatic再帰的な証明書において次の素数を探す際に,ポラードの 因数分解アルゴリズムを使う
"PollardRhoTest"Automatic再帰的な証明書において次の素数を探す際に,ポラードの 因数分解アルゴリズムを適用するかどうかを指定する
"TrialDivisionLimit"AutomaticPrimeQCertificateの試行割算部分で使用する素数の数
"PrimeQMessages"Falseアルゴリズムの処理状況を表示するかどうかを指定する

ProvablePrimeQPrimeQCertificateのオプション

がオプションの値より大きいとき,ProvablePrimeQは前述のようにAtkinMorainのテストを行う.

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

のデフォルト値が指定の数より大きいので,プラット(Pratt)の素数性証明書が返される.
In[10]:=
Click for copyable input
Out[10]=
大きな数については証明は非常に長く複雑になることがある.
In[11]:=
Click for copyable input
Out[11]=