ミラー–ラビン素数判定法 - Wikipedia
ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。フェルマーの素数判定法や ソロベイ–シュトラッセン素数判定法と同じく、乱択アルゴリズムの一種である。Gary L. Miller が最初に開発したMillerテストは未だ証明されていない拡張リーマン予想に基づいた決定的アルゴリズムだったが、マイケル・ラビンがこれを無条件の確率的アルゴリズムに修正した。 フェルマーやソロベイ–シュトラッセンの素数判定法と同様、ミラー–ラビン素数判定法も素数に関して成り立つ等式に基づいており、与えられた数についてそれら等式が成り立つかどうかで判定を行う。 まず、有限体 の単位元の平方根についての補題を考える。ここで
エラトステネスのふるい ～さんすう・数学のお勉強～
● 素数の個数 ● ２，３，５，７，１１，１３，１７，１９，２３，２９，・・・・・・・・・・ 素数（そすう）はいったいどれくらいあるのでしょうか。 （素数って何か知らない人は＜お勉強＞の「素数と素因数分解」を見てね。） じつは、無限に多くあることが古くから知られています。 こんなふうに考えるのです。 もし、有限個しかなかったとしたら、一番大きい素数をＰとしましょう。 ２，３，５，・・・ ，Ｐ 以上が、小さいじゅんにならべたすべての素数です。 さて、それら全部をかけて１をたした数をＡとします。 Ａ＝２×３×５×・・・×Ｐ＋１ こうしてできた数は合成数のはずですね。 だって、一番大きい素数のＰより大きいのですから。 合成数ですから、２，３，５，・・・ ，Ｐのどれかの素数でわりきれるはずです。 ところが、 Ａ÷２＝３×５×・・・×Ｐ あまり １ Ａ÷３＝２×５×・・・×Ｐ
素数判定 - Wikipedia
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "素数判定" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2018年1月) 素数判定（そすうはんてい、英: primality test）とは、与えられた自然数が素数か合成数かを判定することである。素数判定を行うアルゴリズムを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する（クラスPに含まれる）素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在
AKS素数判定法 - Wikipedia
AKS素数判定法（AKSそすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 が素数であるかどうかを判定するのにかかる時間が の多項式を上界とすることをいう。 の多項式ではないことに注意する必要がある。 AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（英語版）の3人の名前から付けられた。 この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/0848-08.pdf
