アルゴリズム の 素数判定に関する解説。

株式会社 日立ソリューションズ

HITACHI Inspire the Next

  • ホーム
  • ソリューション・商品
  • 事例紹介
  • セミナー・展示会
  • ビジネスコラム
  • 企業情報
  • お問い合わせ

素数判定

読み方、または別称:そすうはんてい

素数判定(そすうはんてい)とは、ある自然数nが素数であるか合成数であるかを判定する問題のことで、素数判定を行うアルゴリズムを素数判定法という。素数性判定はPSA暗号の鍵生成同様、応用上重要であるため、素数性を高速に判定するアルゴリズムは、計算理論おいて強い関心の対象になる。
仮定なしで決定的、また多項式時間で終了する素数判定法の存在は長らく未解決であったが、2002年に素数判定が存在することを示す論文が発表された。しかし、多項式の次数が高いため、実用上APR(Adleman-Pomerance-Rumely)判定法などのほうが素数判定よりも高速であることが多いと言われている。
ちなみに、メルセンヌ数など特殊な形の数には、次数の低い多項式時間で動作するアルゴリズムであることが知られている。素数判定法の中には、確率的アルゴリズムに基づいた、与えられた自然数nを“合成数である”“良く分からない”と判定し、この判定法を確率的素数判定法と呼ぶ。
これに対し“素数である”や否の判定である決定的アルゴリズムは、決定的素数判定法と呼ぶ。

ページトップへ戻る

話題の用語

ITと社会用語辞典

ワークロード

ワークロードとは、システムのパフォーマンスを適正な状態に保つための指標のこと。

インターネット用語辞典

ライフログ

ライフログとは、人間の活動の記録(行動履歴)をデジタルデータとして記録すること、およびその記録のことである。

ページトップへ戻る

情報漏洩防止ソリューション 「秘文」

ITのお悩みをソリュっと解決! 特命課ソリュートくんがいく!

『オムニチャネル』から商品を探すページです。日立ソリューションズは、コンサルティングからシステム構築、サポートとトータルソリューションをご提供するシステムインテグレーション企業です。

ページトップへ戻る