ブラウザよりも高速アクセス！
23 関係: AKS素数判定法、対偶 (論理学)、乱択アルゴリズム、平方剰余の相互法則、マイケル・ラビン、ランダウの記号、リーマン予想、ロナルド・リベスト、ディリクレ指標、フェルマーの小定理、アルゴリズム、カール・ポメランス、ソロベイ–シュトラッセン素数判定法、冪剰余、素数、素数判定、補題、高速フーリエ変換、Ruby、暗号、決定的アルゴリズム、有限体、整数の合同。
AKS素数判定法
AKS素数判定法（-そすうはんていほう）は、与えられた自然数が素数であるかどうかを決定的多項式時間で判定できる、世界初のアルゴリズムである。ここで、素数判定法が多項式時間であるとは、与えられた自然数 n が素数であるかどうかを判定するのにかかる時間が\log(n) の多項式を上界とすることをいう。n の多項式ではないことに注意する必要がある。 AKS素数判定法は2002年8月6日に "PRIMES is in P" と題された論文で発表された。Agrawal-Kayal-Saxena 素数判定法としても知られ、論文の著者であるインド工科大学のマニンドラ・アグラワル教授と、2人の学生ニラジュ・カヤル、ナイティン・サクセナ（Nitin Saxena）の3人の名前から付けられた。 この素数判定法が発見される以前にも、素数の判定方法は多数知られていたが、リーマン予想などの仮説を用いずに、決定的多項式時間で判定できるアルゴリズムは存在しなかった。 素数判定という重要な問題が実際にクラスPに属することを示した点で理論的には大躍進であった。しかし実用的には、多項式の次数が高すぎるので、今まで判定できなかった素数を高速に判定できるようになったわけではない（まだ「一般数体ふるい法」で因数分解した方がよい）。.
新しい！!: ミラー–ラビン素数判定法とAKS素数判定法 · 続きを見る »
対偶 (論理学)
対偶（たいぐう、Contraposition）とは、ある命題が成立する場合に、その命題の仮定と結論の両方を否定した命題も成立するという命題同士の関係性の事を言う。 命題「AならばB」の対偶は「BでないならAでない」である。 論理記号を用いて説明すると、命題「A ⇒ B」の対偶は「¬B⇒ ¬A」（¬A は命題 A の否定）である。 通常の数学では、命題「AならばB」の真偽とその対偶「BでないならAでない」の真偽とは必ず一致する(すなわち真理値が等しい）。 数学では、元の命題「AならばB」の証明が難しくても、その対偶「BでないならAでない」の証明は比較的易しい場合がある。「AならばB」と「BでないならAでない」との真偽は一致するので、このようなときには対偶「BでないならAでない」のほうを証明すれば「AならばB」を証明できる（対偶論法）。.
新しい！!: ミラー–ラビン素数判定法と対偶 (論理学) · 続きを見る »
乱択アルゴリズム
乱択アルゴリズム（らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、Probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.
新しい！!: ミラー–ラビン素数判定法と乱択アルゴリズム · 続きを見る »
平方剰余の相互法則
整数論』（1801年）で平方剰余の相互法則の最初の証明を公開した。 （へいほうじょうよ、quadratic residue）とは、ある自然数を法としたときの平方数のことであり、平方剰余の相互法則（へいほうじょうよのそうごほうそく、quadratic reciprocity）は、ある整数 が別の整数 の平方剰余であるか否かを判定する法則である。.
新しい！!: ミラー–ラビン素数判定法と平方剰余の相互法則 · 続きを見る »
マイケル・ラビン
マイケル・ラビン（Michael Oser Rabin、1931年9月1日 - ）は、著名な計算機科学者であり、その分野で最も権威のあるチューリング賞を受賞した。.
新しい！!: ミラー–ラビン素数判定法とマイケル・ラビン · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: ミラー–ラビン素数判定法とランダウの記号 · 続きを見る »
リーマン予想
1.
新しい！!: ミラー–ラビン素数判定法とリーマン予想 · 続きを見る »
ロナルド・リベスト
ナルド・リン・リベスト（Ronald Linn Rivest、1947年5月6日 - ）は、暗号の研究者。現在はMITの計算機科学の教授で、MITコンピュータ科学・人工知能研究所の所員である。通称はロン・リベスト (Ron Rivest)。アメリカ合衆国選挙支援委員会の技術ガイドライン開発委員会の委員を務めており、Voluntary Voting System Guidelines の起草を助けた, from the National Institute of Standards and Technology。.
新しい！!: ミラー–ラビン素数判定法とロナルド・リベスト · 続きを見る »
ディリクレ指標
ディリクレ指標(でぃりくれしひょう)とは、ディリクレがL関数を定義する際に導入した整数から複素数への関数である。.
新しい！!: ミラー–ラビン素数判定法とディリクレ指標 · 続きを見る »
フェルマーの小定理
数論において、フェルマーの小定理（フェルマーのしょうていり、Fermat's little theorem）は素数の性質についての定理であり、実用としてもRSA暗号に応用されている定理である。.
新しい！!: ミラー–ラビン素数判定法とフェルマーの小定理 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ミラー–ラビン素数判定法とアルゴリズム · 続きを見る »
カール・ポメランス
ール・ポメランス（Carl Pomerance, 1944年 - ）は、アメリカの数学者。専門は数論および暗号理論。ミズーリ州ジョプリン生まれ。 奇完全数は少なくとも7個の相異なる素因数を持つことを証明した論文で、1972年にハーヴァード大学で博士号を取得した。その後、ジョージア大学に勤め、1982年に教授になった。2003年よりダートマス大学教授。 1984年には、RSA などの公開鍵暗号の安全性の根拠となっている素因数分解問題を、準指数時間で解くアルゴリズム（2次ふるい法）を発表している。Adleman-Pomerance-Rumely 素数判定法の発案者でもある。.
新しい！!: ミラー–ラビン素数判定法とカール・ポメランス · 続きを見る »
ソロベイ–シュトラッセン素数判定法
ベイ–シュトラッセン素数判定法は、とフォルカー・シュトラッセンによって開発された、与えられた数が合成数か擬素数か判定する確率的テストである。現在ではやミラー-ラビン素数判定法にとって代わられているが、RSA暗号の実用性を示したアルゴリズムとして歴史的には重要である。.
新しい！!: ミラー–ラビン素数判定法とソロベイ–シュトラッセン素数判定法 · 続きを見る »
冪剰余
冪剰余（べきじょうよ、英: Modular exponentiation）とは、冪乗の剰余のことである。数論的に重要な概念であるとともに、計算機科学、特に暗号理論の分野での応用が重要である。冪乗剰余とも呼ばれる。 正の整数 （底）の整数 乗（冪指数）を正の整数 （法）で割った余りを、「 を法とした の -冪剰余」と呼ぶ。つまり、冪剰余を求めるとは、次の を計算することに他ならない。 例えば、 の場合、 は を で割った余りなので、冪剰余は となる。 冪指数 に対する -冪剰余は、通常それぞれ平方剰余、立方剰余と呼ばれる。 冪剰余は、指数 が負の場合も定義できる。その場合、 を法として の逆数（モジュラ逆数）となる d によって、 と定義する。 冪剰余 を求める計算は、たとえ巨大な数であっても難しくはない。一方、 が与えられたとき、指数 を求めることは難しい。このような一方向性関数的性質から、冪剰余の暗号での利用についての研究が進んでいる。.
新しい！!: ミラー–ラビン素数判定法と冪剰余 · 続きを見る »
素数
素数（そすう、prime number）とは、 より大きい自然数で、正の約数が と自分自身のみであるもののことである。正の約数の個数が である自然数と言い換えることもできる。 より大きい自然数で素数でないものは合成数と呼ばれる。 一般には、素数は代数体の整数環の素元として定義される（そこでは反数などの同伴なものも素数に含まれる）。このため、有理整数環 \mathbb Z での素数は有理素数（ゆうりそすう、rational prime）と呼ばれることもある。 最小の素数は である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。 素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。 自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。 分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 であり、十進法で表記したときの桁数は2324万9425桁に及ぶ。.
新しい！!: ミラー–ラビン素数判定法と素数 · 続きを見る »
素数判定
素数判定（そすうはんてい）とは、ある自然数 n が素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。 RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。 仮定なしで決定的かつ多項式時間で終了する素数判定法が存在するか否かは長らく未解決の問題だったが、2002年にそのような素数判定法が存在することを示す論文がAgrawal, Kayal, Saxenaにより発表された（AKS素数判定法）。しかし多項式の次数が高く、実用上はなどのほうが高速であることが多い。 なお、メルセンヌ数など特殊な形をした数に対しては次数の低い多項式時間で動作するアルゴリズムがあることが知られている。.
新しい！!: ミラー–ラビン素数判定法と素数判定 · 続きを見る »
補題
数学において、「補助定理」(helping theorem) あるいは補題 (lemma))-->とは、それ自身興味あるステートメントとしてよりはむしろ、より大きな結果のための一歩として使われる、証明された命題である。.
新しい！!: ミラー–ラビン素数判定法と補題 · 続きを見る »
高速フーリエ変換
速フーリエ変換（こうそくフーリエへんかん、fast Fourier transform, FFT）は、離散フーリエ変換（discrete Fourier transform, DFT）を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換（inverse fast Fourier transform, IFFT）と呼ぶ。.
新しい！!: ミラー–ラビン素数判定法と高速フーリエ変換 · 続きを見る »
Ruby
Ruby（ルビー）は、まつもとゆきひろ（通称 Matz）により開発されたオブジェクト指向スクリプト言語であり、スクリプト言語が用いられてきた領域でのオブジェクト指向プログラミングを実現する。 また日本で開発されたプログラミング言語としては初めて国際電気標準会議で国際規格に認証された事例となった。.
新しい！!: ミラー–ラビン素数判定法とRuby · 続きを見る »
暗号
暗号とは、セキュア通信の手法の種類で、第三者が通信文を見ても特別な知識なしでは読めないように変換する、というような手法をおおまかには指す。いわゆる「通信」（telecommunications）に限らず、記録媒体への保存などにも適用できる。.
新しい！!: ミラー–ラビン素数判定法と暗号 · 続きを見る »
決定的アルゴリズム
決定的アルゴリズム（けっていてきアルゴリズム、deterministic algorithm）は、計算機科学におけるアルゴリズムの種類であり、その動作が予測可能なものをいう。入力を与えられたとき、決定的アルゴリズムは常に同じ経路で計算を行い、常に同じ結果を返す。決定的アルゴリズムは最も研究の進んでいるアルゴリズムであり、その多くは実際のコンピュータで効率的に実行できる実用性を備えている。決定性アルゴリズムと言うことも多い。 決定的アルゴリズムは、同じ入力に対しては常に（ひとつの）同じ結果を返すという点で、関数の一種とみなせる。アルゴリズムはその結果の計算の具体的な手順を与えるものである。.
新しい！!: ミラー–ラビン素数判定法と決定的アルゴリズム · 続きを見る »
有限体
有限体（ゆうげんたい、英語：finite field）とは、代数学において、有限個の元からなる体、すなわち四則演算が定義され閉じている有限集合のことである。主に計算機関連の分野においては、発見者であるエヴァリスト・ガロアにちなんでガロア体あるいはガロア域（ガロアいき、Galois field）などとも呼ぶ。 有限体においては、体の定義における乗法の可換性についての条件の有無は問題にはならない。実際、ウェダーバーンの小定理と呼ばれる以下の定理 が成り立つことが知られている。別な言い方をすれば、有限体において乗法の可換性は、体の有限性から導かれるということである。.
新しい！!: ミラー–ラビン素数判定法と有限体 · 続きを見る »
整数の合同
ウスの『Disquisitiones Arithmeticae（整数論）』のタイトルページ。 整数の合同（ごうどう、congruence）は、数学において二つの整数の間に定められる関係である。初めてこれを構造として研究したのはドイツの数学者ガウスで、1801年に発表された著書『Disquisitiones Arithmeticae』でも扱われている。今日では整数の合同は、数論や一般代数学あるいは暗号理論などに広く用いられる。 整数の合同に基づく数学の分野は合同算術 (modular arithmetic) と呼ばれる。これは整数そのものを直接的に扱うのではなく、何らかの整数（法と呼ばれる、以下本項では で表す）で割った剰余を代表元として扱う算術である。合同算術の歴史や道具立てあるいはその応用については合同算術の項を参照。また、より包括的で堅苦しくない説明は剰余類環 の項へ譲る。.
新しい！!: ミラー–ラビン素数判定法と整数の合同 · 続きを見る »
ここにリダイレクトされます：
ラビン-ミラー素数判定法、ミラー-ラビン素数判定法、強擬素数。
