26 関係: 多項式時間、宇宙線、一方向性関数、乱数列、ハードウェア乱数生成器、メルセンヌ・ツイスタ、ロジスティック写像、テント写像、アルゴリズム、カオス理論、キャリー付き乗算、ジョン・フォン・ノイマン、サイコロ、Blum-Blum-Shub、線形合同法、線形帰還シフトレジスタ、熱雑音、識別不能、Lagged Fibonacci 法、M系列、Xorshift、暗号、暗号学的ハッシュ関数、暗号理論、暗号論的擬似乱数生成器、楕円曲線暗号。
多項式時間
多項式時間(たこうしきじかん)とは計算理論において多項式で表される計算時間。 多項式時間のアルゴリズムとは、解くべき問題の入力サイズnに対して、処理時間の上界としてnの多項式で表現できるものが存在するアルゴリズムを指す。問題入力サイズの増大に対する、処理時間の増大を表すものであることに注意されたい。 たとえばバブルソートの処理時間は要素数nに対して要素の比較・交換を行う回数は高々 \frac n(n-1) である。したがって、この場合の最悪計算量のオーダーは''O''記法を用いてO()と表される。 またクイックソートの期待計算量のオーダーはO(n \log n)、最悪計算量のオーダーはO()である。.
新しい!!: 擬似乱数と多項式時間 · 続きを見る »
宇宙線
宇宙線(うちゅうせん、Cosmic ray)は、宇宙空間を飛び交う高エネルギーの放射線のことである名越 2011 p.3。主な成分は陽子であり、アルファ粒子、リチウム、ベリリウム、ホウ素、鉄などの原子核が含まれている。地球にも常時飛来している。.
一方向性関数
一方向性関数(いちほうこうせいかんすう、one-way function)とは、簡単に計算できるが逆関数の計算は非常に困難である関数を指す。暗号理論などで用いられる概念である。素因数分解問題の困難性を用いたものが代表的。 下では、単に「多項式時間アルゴリズム」と書いたら「平均多項式時間確率アルゴリズム」を指す。.
新しい!!: 擬似乱数と一方向性関数 · 続きを見る »
乱数列
乱数列(らんすうれつ)とはランダムな数列のこと。 数学的に述べれば、今得られている数列 x1, x2,..., xn から次の数列の値 xn+1 が予測できない数列。乱数列の各要素を乱数という。.
ハードウェア乱数生成器
ハードウェア乱数生成器(-らんすうせいせいき)は、ハードウェアに由来する不確定性を利用した、擬似乱数列でない「真の乱数列」を発生させるシステム。コンピュータの内部などのものでは、システム中にソフトウェアが併用されることも多い。 サイコロなども原始的なハードウェア乱数生成器である。 ダイオードの生成するノイズや熱雑音、放射性物質の崩壊による放射線をセンサで検出する等、ランダムな物理現象を用い、その信号を元に乱数を生成する。物理現象は必ずしも一様乱数とはならないため、センサからの出力を必要な種類の乱数に変換する必要がある場合もある。使用環境によっては発生する乱数に傾向が見られないようにノイズ発生器を設計する事が重要になる。.
新しい!!: 擬似乱数とハードウェア乱数生成器 · 続きを見る »
メルセンヌ・ツイスタ
メルセンヌ・ツイスタ (Mersenne twister、通称MT) は擬似乱数列生成器 (PRNG) の1つである。1996年に国際会議で発表されたもので(1998年1月に論文掲載)松本眞と西村拓士による。既存の疑似乱数列生成手法にある多くの欠点が無く、高品質の疑似乱数列を高速に生成できる。考案者らによる実装が修正BSDライセンスで公開されている。.
新しい!!: 擬似乱数とメルセンヌ・ツイスタ · 続きを見る »
ロジスティック写像
ティック写像(ロジスティックしゃぞう、)とは、1次元の離散力学系の一種。ロジスティック方程式の離散化からも得られるため離散型ロジスティック方程式とも呼ばれる。変数を x としたとき、次の1変数2次差分方程式(漸化式)で示される。 ロジスティック写像は、パラメータ a にどのような値を与えるかによって、n を増やすに連れたxnの値の変化(振る舞いや軌道と呼ぶ)が、一定値への収束、複数の値を繰り返し取り続ける周期的な振動、カオスと呼ばれる非周期的な極めて複雑な振る舞い、へと変化する。 この複雑な振る舞いについて多くの研究がされてきたが、特にロバート・メイ(他にジム・ヨーク、ジョージ・オスター)の研究によって広く知られるようになった。 カオスを生み出す系は非線形性を持つ必要があるが、このような非線形関数の中でも、ロジスティック写像は最も単純なものの1つである二次関数の差分方程式からカオスを生成する。この単純さと、他のカオスとも共通する現象がいくつも現れることから、カオス理論の入り口としてよく採り上げられる。.
新しい!!: 擬似乱数とロジスティック写像 · 続きを見る »
テント写像
分岐図 テント写像(テントしゃぞう、tent map)は、力学系あるいはカオス理論における基礎的な写像の一つである。パラメータ(定数)を一つ持つ、以下のような区分線形関数 で与えられる。 f(x).
新しい!!: 擬似乱数とテント写像 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム(algorithm )とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい!!: 擬似乱数とアルゴリズム · 続きを見る »
カオス理論
論(カオスりろん、、、)は、力学系の一部に見られる、数的誤差により予測できないとされている複雑な様子を示す現象を扱う理論である。カオス力学ともいう。 ここで言う予測できないとは、決してランダムということではない。その振る舞いは決定論的法則に従うものの、積分法による解が得られないため、その未来(および過去)の振る舞いを知るには数値解析を用いざるを得ない。しかし、初期値鋭敏性ゆえに、ある時点における無限の精度の情報が必要であるうえ、(コンピューターでは無限桁を扱えないため必然的に発生する)数値解析の過程での誤差によっても、得られる値と真の値とのずれが増幅される。そのため予測が事実上不可能という意味である。.
新しい!!: 擬似乱数とカオス理論 · 続きを見る »
キャリー付き乗算
ャリー付き乗算 (multiply-with-carry, MWC) は、George Marsagliaにより開発された整数疑似乱数生成用の手法である。乱数種には2〜数千の値を必要とする。MWC の主な長所は、単純な整数演算からなっており非常に高速に動作するという点と、260〜2000000 という非常に長周期であるという点である。.
新しい!!: 擬似乱数とキャリー付き乗算 · 続きを見る »
ジョン・フォン・ノイマン
ョン・フォン・ノイマン(ハンガリー名:Neumann János(ナイマン・ヤーノシュ、)、ドイツ名:ヨハネス・ルートヴィヒ・フォン・ノイマン、John von Neumann, Margittai Neumann János Lajos, Johannes Ludwig von Neumann, 1903年12月28日 - 1957年2月8日)はハンガリー出身のアメリカ合衆国の数学者。20世紀科学史における最重要人物の一人。数学・物理学・工学・計算機科学・経済学・気象学・心理学・政治学に影響を与えた。第二次世界大戦中の原子爆弾開発や、その後の核政策への関与でも知られる。.
新しい!!: 擬似乱数とジョン・フォン・ノイマン · 続きを見る »
サイコロ
イコロ(ピップ) サイコロ(算用数字) サイコロ(骰子、賽子)、または賽(さい)、ダイス (dice) は主として卓上遊戯や賭博等に用いる小道具で、乱数を発生させるために使うものである。 多くは正六面体で、転がりやすいように角が少し丸くなっている。各面にその面の数を示す1個から6個の小さな点が記されていて、対面の点の数の和は必ず7となる。この点は“目”、または“ピップ” (pip)、“スポット” (spot)、まれに“ドット” (dot) とも呼ばれる。日本製の場合、1の面の目は赤く着色されていることが多い。ピップではなく算用数字が記されているものもある。 各面に表示される数も“目”と呼ばれ、サイコロを振った結果表示される数を“出目”と呼ぶ。複数のダイスを同時に振ってすべて揃った出目を特に“ゾロ目”と表現し、特にすべてが1の目が揃った場合のことを“ピンゾロ”と表現する。.
Blum-Blum-Shub
Blum-Blum-Shub(B.B.S.)は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。 漸化式は次のような形をしている。 ここで M.
新しい!!: 擬似乱数とBlum-Blum-Shub · 続きを見る »
線形合同法
線形合同法(せんけいごうどうほう、Linear congruential generators, LCGs)とは、擬似乱数列の生成式の一つ。 漸化式 によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。.
新しい!!: 擬似乱数と線形合同法 · 続きを見る »
線形帰還シフトレジスタ
線形帰還シフトレジスタ(せんけいきかんシフトレジスタ、linear feedback shift register, LFSR)は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。 値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。 LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。 LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。.
新しい!!: 擬似乱数と線形帰還シフトレジスタ · 続きを見る »
熱雑音
熱雑音(ねつざつおん、thermal noise)は、抵抗体内の自由電子の不規則な熱振動(ブラウン運動)によって生じる雑音のことをいう。1927年にこの現象を発見した二人のベル研究所の研究者ジョン・バートランド・ジョンソン及びハリー・ナイキストの名前からジョンソン・ノイズまたはジョンソン-ナイキスト・ノイズとも呼ばれる。 抵抗体内で発生する雑音の電圧Vn 、電流In は次式で与えられる。 ここでk B はボルツマン定数、T は導体の温度、Δf は帯域幅、R は抵抗値である。 従ってノイズの大きさPn は次式で与えられる。 また、雑音元(信号元)から回路に入力される雑音電力を入力雑音電力と言い、電気通信分野での増幅器雑音計算には専らこちらが使用される。入力雑音電力N i は次式で与えられる。 入力雑音電力がこの数式で与えられるのは、雑音元を、起電力が上記のV_、内部抵抗がRの電源と考え、負荷につないだときに負荷で消費される電力として計算するからである。入力された電力を、反射することなく負荷で完全に消費するには、負荷のインピーダンスがRである必要があり、その結果として上記の入力雑音電力N_\mathrmが導出される。 ノイズの大きさは温度で決まる。室温(300K)のノイズ(入力雑音電力)の大きさP をデシベル単位(dBm)で表すと である。 熱雑音が問題になるような領域は極めて小さい信号を扱う場合で、そのような場合は、増幅器を極低温まで冷却して極限まで雑音性能を高めることなどがされる。 熱雑音が有効活用される例として、コンピュータの乱数発生器に熱雑音を用いる物がある。.
識別不能
識別不能(しきべつふのう)とは、二つの確率変数を見分けることができないことを意味する。ただ、これらを「見分けようとする人」がどのようにして見分けるのか、どれだけの能力を持っているかによって、見分けられるか・見分けられないかは異なる。そのため、想定する「見分けるために使う能力」により、三つの定義がある。.
Lagged Fibonacci 法
Lagged Fibonacci 法(ラグ付フィボナッチ法)は疑似乱数生成法の1つ。この手法は標準的な線形合同法を改善する事を目的としており、フィボナッチ数の生成法を元にしている。 フィボナッチ数列は以下の漸化式により表現される。 つまり、数列の前二項の和が次の項になる。これは以下のように一般化できる。 ここで、★演算子は一般的な二項演算子を表し、新しい項は以前の何らかの二項を演算して得られる。★演算子は加算にも減算にも乗算にもビット単位の排他的論理和にもなる。m は通常2の累乗(m.
新しい!!: 擬似乱数とLagged Fibonacci 法 · 続きを見る »
M系列
M系列(-けいれつ、m-sequence;maximal length sequence)とは、ガロア体における線形漸化式が生成する数列(sequence)のうち最長の周期(maximal length)を持つもの。MLSと略されることがある。.
Xorshift
Xorshiftは疑似乱数列生成法の1つである。George Marsagliaが2003年に提案した。演算が排他的論理和とビットシフトのみであるため高速であるなどの特徴がある。.
新しい!!: 擬似乱数とXorshift · 続きを見る »
暗号
暗号とは、セキュア通信の手法の種類で、第三者が通信文を見ても特別な知識なしでは読めないように変換する、というような手法をおおまかには指す。いわゆる「通信」(telecommunications)に限らず、記録媒体への保存などにも適用できる。.
暗号学的ハッシュ関数
暗号におけるハッシュ関数(特にSHA-1)の動作の様子。入力の微妙な変化で出力が大きく変化する点に注意(雪崩効果) 暗号学的ハッシュ関数(あんごうがくてきハッシュかんすう、cryptographic hash function)は、ハッシュ関数のうち、暗号など情報セキュリティの用途に適する暗号数理的性質をもつもの。任意の長さの入力を(通常は)固定長の出力に変換する。 「メッセージダイジェスト」は、暗号学的ハッシュ関数の多数ある応用のひとつであり、メールなどの「メッセージ」のビット列から暗号学的ハッシュ関数によって得たハッシュ値を、そのメッセージの内容を保証する「ダイジェスト」として利用するものである。.
新しい!!: 擬似乱数と暗号学的ハッシュ関数 · 続きを見る »
暗号理論
暗号理論(あんごうりろん)の記事では暗号、特に暗号学に関係する理論について扱う。:Category:暗号技術も参照。.
暗号論的擬似乱数生成器
暗号論的擬似乱数生成器(cryptographically secure pseudo random number generator、暗号論的にセキュアな疑似乱数生成器、CSPRNG)とは、暗号技術での利用に適した特性を持つ擬似乱数生成器 (PRNG) である。 暗号の応用では様々な場面で乱数を必要とする。例えば、以下のようなものがある。.
新しい!!: 擬似乱数と暗号論的擬似乱数生成器 · 続きを見る »
楕円曲線暗号
楕円曲線暗号(だえんきょくせんあんごう、Elliptic Curve Cryptography: ECC)とは、楕円曲線上の離散対数問題 (EC-DLP) の困難性を安全性の根拠とする暗号。1985年頃に ビクタ・ミラー (Victor Miller) とニール・コブリッツ (Neal Koblitz) が各々発明した。 具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。DSAを楕円曲線上で定義した楕円曲線DSA (ECDSA)、DH鍵共有を楕円化した楕円曲線ディフィー・ヘルマン鍵共有 (ECDH) などがある。公開鍵暗号が多い。 EC-DLPを解く準指数関数時間アルゴリズムがまだ見つかっていないため、それが見つかるまでの間は、RSA暗号などと比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いことをメリットとして、ポストRSA暗号として注目されている。ただしP.
新しい!!: 擬似乱数と楕円曲線暗号 · 続きを見る »
ここにリダイレクトされます:
擬似ランダム、擬似乱数列、擬似乱数生成器、疑似ランダム、疑似乱数。