2010年3月1日 (月) 20:26時点における版編集 DixonDBot (会話 \| 投稿記録) 3,340 回編集 m ロボットによる除去: eo:Vikipedio:Projekto matematiko/Pseŭdohazarda nombra generilo ← 古い編集		2010年10月18日 (月) 07:16時点における版編集取り消し MetaNest (会話 \| 投稿記録) 拡張承認された利用者 21,577 回編集 →‎主な擬似乱数生成法新しい編集 →
11行目: 逆に、再現性を利用して、シード値の選択を意図的（不正に）に行う可能性を排除することが必要な場合もある（[[楕円曲線暗号]]のパラメータ生成など）。 == 主な擬似乱数生成法 == 様々な擬似乱数生成法が知られている。予測可能、再現性あり古典的生成法 - ~~[[擬似乱数\|~~平方採中法]]、[[線形合同法]]~~、[[擬似乱数\|~~（乗算合同法・混合合同法]]）、[[線形帰還シフトレジスタ]] 新しい生成法 - [[メルセンヌ・ツイスタ]]、[[キャリー付き乗算]]、[[Xorshift]]、[[Lagged Fibonacci 法]]、カオス乱数 23行目: 予測不能、再現性なし **[[ハードウェア乱数生成器]] - [[サイコロ]]、[[熱雑音]]、[[宇宙線]]などを利用する物理的暗号 === 混合合同法（mixed congruential method） ===▼ 下の式に適当な ''a''、''p''、''q'' を代入する（必要な桁数が採れれば何でも良い）。求まった ''a' '' の中間あたりの必要な桁数を乱数として採用し、それを新たな ''a'' として、再び下の式に代入する。▼ :''ap'' + ''q'' = ''a' ''▼ （例）5 桁の擬似乱数を作ってみる。ただし、最初は ''a'' = 14992、''p'' = 673、''q'' = 944とし、求まった ''a' '' の、十の位から十万の位までを採用することとする。▼ :14992×673+944 = 10090560 → 09056▼ :09056×673+944 = 06095632 → 09563▼ :09563×673+944 = 06436843 → 43684▼ :43684×673+944 = 29400276 → 40027▼ :40027×673+944 = 26939115 → 93911▼ :…▼ こうして、擬似乱数列 {14992, 9056, 9563, 43684, 40027, 93911, …} を得る。▼ <!-- [[線形合同法]]という記事があったので、コメントアウト▼ == 線形合同法（linear congruential method） ==▼ 1948年、レーマが提案▼ 適当な初期値<math>X_0</math>と、適当な定数<math>a</math>,<math>b</math>,<math>m</math>を定める。▼ <math>X_i = a X_{i-1} + b \mod m</math>▼ として、<math>X</math> を乱数列とする。▼ -->▼ === 平方採中法（middle-square method） === もっとも古い手法で、1946年頃、[[ジョン・フォン・ノイマン\|ノイマン]]が提案した。TAOCPの新しい訳本では二乗中抜き法と呼んでいる。初期値に適当な ''a'' をきめ、それを 2 乗する。求まった値の中央にある、必要な桁数を採って乱数とし、それを 2 乗して求まった値の中央にある必要な桁数を採って次の乱数とする。これを繰り返して乱数列とする方法。ここで「中央」とは、求まった値を必要な桁数の 2 倍の桁数として見た時の中央とする。たとえば、4 桁を必要としていて、求まった値が 7 桁の時は、最上位の前の位（千万の位）に「0」を付け足して 8 桁とする（下の例を参照）。 55 ⟶ 37行目: :4256<sup>2</sup> = 18113536 → 1135 :… こうして、擬似乱数列 {1763, 1081, 1685, 8392, 4256, 1135, …} を得る。 ~~一般的には、~~平方採中法は偶数桁を採る時にしか使えない~~ことと、周期が短い、つ~~。まりた、~~どちらも~~計算の結果、~~ずっと繰り返してい~~過去に現れ~~ばいつかは最初の~~た数~~字に一致する~~と同じ数値が現れるがればループとなり、そ~~れが平方採中法~~の方長さを周期と言うが~~早いことから~~、混合線形合同法を使~~うこと~~えば周期が最長のもの方が~~多いよう~~理論的に可能であるため、現代において平方採中法が利用されることはまずない。 ▲<!-- [[線形合同法]]という記事があったので、コメントアウト ▲== 線形合同法（linear congruential method） == ▲1948年、レーマが提案 ▲適当な初期値<math>X_0</math>と、適当な定数<math>a</math>,<math>b</math>,<math>m</math>を定める。 ▲<math>X_i = a X_{i-1} + b \mod m</math> ▲として、<math>X</math> を乱数列とする。 ▲--> === 線形合同法（linear congruential method） === {{Main\|線形合同法}} ==== 乗算合同法 ==== ▲==== 混合合同法（mixed congruential method） ==== 線形合同法の : <math>X_{n+1} = \left( A \times X_n + B \right) \bmod M</math> において、B = 0 の場合を区別して特に乗算合同法、B > 0 の場合を区別して特に混合合同法と言うことがある。 <!-- ▲下の式に適当な ''a''、''p''、''q'' を代入する（必要な桁数が採れれば何でも良い）。求まった ''a' '' の中間あたりの必要な桁数を乱数として採用し、それを新たな ''a'' として、再び下の式に代入する。 ▲:''ap'' + ''q'' = ''a' '' ▲（例）5 桁の擬似乱数を作ってみる。ただし、最初は ''a'' = 14992、''p'' = 673、''q'' = 944とし、求まった ''a' '' の、十の位から十万の位までを採用することとする。 ▲:14992×673+944 = 10090560 → 09056 ▲:09056×673+944 = 06095632 → 09563 ▲:09563×673+944 = 06436843 → 43684 ▲:43684×673+944 = 29400276 → 40027 ▲:40027×673+944 = 26939115 → 93911 ▲:… ▲こうして、擬似乱数列 {14992, 9056, 9563, 43684, 40027, 93911, …} を得る。 --> === 線形帰還シフトレジスタ === {{Main\|線形帰還シフトレジスタ}} 擬似乱数の生成方式として、[[線形帰還シフトレジスタ]] (LFSR; Linear Feedback Shift Register) を用いた方法が知られている。LFSRはデジタル回路を用いて容易に実装することができる。特性多項式を適切に選択することによって、等頻度性、無相関性及び周期が保障される。乱数とし~~かし、~~ては最長周期を保障する[[M系列]]を使う。LFSRは数学的に容易に解析可能であるため、そのまま暗号に使用することは推奨されない。 == 新しい擬似乱数生成アルゴリズム ==

「擬似乱数」の版間の差分