PrimalityProving`
PrimalityProving`

ProvablePrimeQ

ProvablePrimeQ[n]

n が素数であることを証明できればTrueを，それ以外の場合はFalseを返す．

詳細とオプション

  • ProvablePrimeQを使うためには，まず素数証明パッケージをロードしなくてはならない．それにはNeeds["PrimalityProving`"]を実行する必要がある．
  • ProvablePrimeQ[n]がTrueを返すならば，n はプラットの素数証明書，あるいはAtkin–Morainの素数証明に基づいた素数である．
  • PrimeQは桁違いに速いので， ProvablePrimeQをPrimeQの代用として使うべきではない．代りに必要な場合は，PrimeQの結果の証明にProvablePrimeQを使うとよい．
  • 次のオプションを使うことができる：
  • "SmallPrime"1050Atkin–Morainテストを使用する下限
    "Certificate"False証明書を出力するかどうか
    "PollardPTest"Automaticポラード(Pollard)の メソッドを使うかどうか
    "PollardRhoTest"Automaticポラードの メソッドを使うかどうか
    "TrialDivisionLimit"Automatic試行割算で使う素数の数
    "PrimeQMessages"False処理状況を監視するかどうか

例題

すべて開くすべて閉じる

例  (1)

PrimeQにより1093が素数であることが分かる：

ProvablePrimeQでも同じ結果であるが，証明書が生成される：

スコープ  (2)

ProvablePrimeQは任意の大きい数にも使える：

ProvablePrimeQは自動的にリストに縫い込まれる：

オプション  (2)

Certificate  (1)

オプション"Certificate"->Trueを使うと，直接証明書を見ることができる：

PrimeQMessages  (1)

ランダムな素数：

PrimeQCertificateで，進行状況のメッセージが出力される：

特性と関係  (1)

ランダムな素数である：

ProvablePrimeQが結果を返したら，PrimeQCertificateを使って証明書を出力することができる：

"Certificate"->Trueとすると，ProvablePrimeQはAtkin–Morain素数検定を繰り返す：

考えられる問題  (1)

，，に対しては，証明書は生成されない：