素数証明パッケージ

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

素数または合成数の証明

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

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

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

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

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

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

ProvablePrimeQとPrimeQCertificateのオプション

n がオプション"SmallPrime"の値より大きいとき，ProvablePrimeQは前述のようにAtkin–Morainのテストを行う．

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