| 出典: 素数 『通信用語の基礎知識』 更新年月日 2016/03/18,URL: https://www.wdic.org/ 2、3、5、7、11…のように、1とその数自身以外に約数を持たない、1より大きい自然数のこと。 [概要] 素数に1は含まれない。また2以外は全て奇数であり、2桁以上の素数の下一桁は1、3、7、9のいずれかとなる。 素数は自然数や整数を考える上で重要な要素と考えられている。数学としてだけでなく、暗号理論などにおいても用いられている。 現在知られる最も大きな素数は、GIMPSプロジェクトで2008(平成20)年に発見された45個目のメルセンヌ素数で、243,112,609−1であり、その桁数は1297万8189桁である。同プロジェクトは46個目、47個目まで発見しているが、この二つは45個目より桁が小さかった(詳細後述)。 [特徴] [種類] 特殊な素数 素数単独での特殊な素数。以下の式では、素数でないnも存在する。 ● メルセンヌ素数: 2n−1 ● フェルマー素数: 22n+1 ● オイラー素数: n2+n+1 ● レピュニット素数: (1)n 特に名前のないもの。 ● n!+1 ● n!−1 ● nまでの素数の積±1 素数そのものは無限に存在するが、こういった特殊な素数が無限に存在するかは未解明である。 [特殊な素数の組] 素数のうち一定の条件に一致する組み合わせを素数の組といい、特に研究されているものには次のようなものがある。 ● 差を見るもの ・ 差が2 [(p, p+2)] … 双子素数 ・ 差が2と6または4と6 [(p, p+2, p+6)または(p, p+4, p+6)] … 三つ子素数 ・ 差が2と6と8 [(p, p+2, p+6, p+8)] … 四つ子素数 ・ 差が4 [(p, p+4)] … いとこ素数 ・ 差が6 [(p, p+6)] … セクシー素数 ● ソフィー・ジェルマン素数と安全素数 [(p, 2p+1)] pと2p+1が共に素数であるとき、pをソフィー・ジェルマン素数、2p+1を安全素数という。 [性質] 素数の数 素数が無限に存在することはユークリッドの定理により証明されている。 ・・・ |
| 出典: 素数判定 『フリー百科事典 ウィキペディア日本語版(Wikipedia)』 最終更新 2017年7月30日 (日) 03:20 UTC、URL: https://ja.wikipedia.org/ 素数判定（そすうはんてい）とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。しかし多項式の次数が高く、実用上はAPR(Adleman-Pomerance-Rumely)判定法などのほうが高速であることが多い。なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。 [確率的素数判定法] 素数判定法の中には確率的アルゴリズムに基づいた、与えられた自然数 n を「合成数である」または「良く分からない」と判別する判定法がある。この判定法を確率的素数判定法 (probabilistic primality test) ということがある。これに対して「素数である」あるいは否と判定する決定的アルゴリズムは決定的素数判定法 (deterministic primality test) ということがある。 ・・・ |
| 同義語・類義語 | 関連語・その他 |
|---|---|
| 素数判定 | |
| そすう はんてい | |
| 素数判定法 | |
| 素数判定アルゴリズム | |
| 素数判定プログラム | |
| AKS素数判定法 | |
| APR判定法 | |
| ・ | |
| probabilistic primality test | |
| prɔ̀bəbəlístik praimǽliti tést | |
| プロバゥボリゥィステック プリィマェリゥィティー テストゥ | |
| プロバゥボリゥィステック・プリィマェリゥィティー・テストゥ | |
| プロ̀バゥボリゥィ́ステック・プリィマェ́リゥィティー・テ́ストゥ | |
| プロバビリスティク プリマリティー テスト | |
| プロバビリスティク・プリマリティー・テスト | |
| プロ̀バビリスティク・プリマ́リティー・テ́スト | |
| 確率的素数判定法 | |
| かくりつてき そすう はんていほう | |
| ・ | |
| deterministic primality test | |
| ditə́rminìstik praimǽliti tést | |
| デタゥーミネスティック プリィマェリゥィティー テストゥ | |
| デタゥーミネスティック・プリィマェリゥィティー・テストゥ | |
| ディタゥ́ーミネ̀スティック・プリィマェ́リゥィティー・テ́ストゥ | |
| デターミニスティック プリマリティー テスト | |
| デターミニスティック・プリマリティー・テスト | |
| デタ́ーミニ̀スティック・プリマ́リティー・テ́スト | |
| 決定的素数判定法 | |
| けっていてき そすう はんていほう | |
| ・ | |
| 更新日:2024年11月 5日 |