擬似ぎじ乱数らんすう

擬似ぎじ乱数らんすう（ぎじらんすう、pseudorandom numbers）は、乱数らんすう列れつのように見みえるが、実際じっさいには確定かくてい的てきな計算けいさんによって求もとめている擬似ぎじ乱数らんすう列れつによる乱数らんすう。擬似ぎじ乱数らんすう列れつを生成せいせいする機器ききを擬似ぎじ乱数らんすう列れつ生成せいせい器き、生成せいせいアルゴリズムを擬似ぎじ乱数らんすう列れつ生成せいせい法ほうと呼よぶ。

真しんの乱数らんすう列れつは本来ほんらい、規則きそく性せいも再現さいげん性せいもないものであるため、本来ほんらいは確定かくてい的てきな計算けいさんによって求もとめることはできない（例れい：サイコロを振ふる時とき、今いままでに出でた目めから次つぎに出でる目めを予測よそくするのは不可能ふかのう）。一方いっぽう、擬似ぎじ乱数らんすう列れつは確定かくてい的てきな計算けいさんによって作つくるので、その数列すうれつは確定かくてい的てきであるうえ、生成せいせい法ほうと内部ないぶ状態じょうたいが既知きちであれば、予測よそく可能かのうでもある。

ある擬似ぎじ乱数らんすう列れつを、真しんの乱数らんすう列れつとみなして良よいかを確実かくじつに決定けっていすることはできない。シミュレーション等とうの一般いっぱん的てきな用途ようとには、対象たいしょうとする乱数らんすう列れつの統計とうけい的てきな性質せいしつが、使用しよう対象たいしょうとする目的もくてきに合致がっちしているかどうかを判断はんだんする。これを検定けんていと言いい、各種かくしゅの方法ほうほうが提案ていあんされている。

しかし、特とくに暗号あんごうに使用しようする擬似ぎじ乱数らんすう列れつについては注意ちゅういが必要ひつようであり、シミュレーション等とうには十分じゅうぶんな擬似ぎじ乱数らんすう列れつ生成せいせい法ほうであっても、暗号あんごうにそのまま使用しようできるとは限かぎらない。暗号あんごうで使用しようする擬似ぎじ乱数らんすう列れつについては暗号あんごう論ろん的てき擬似ぎじ乱数らんすうの節ふしおよび暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器きの記事きじを参照さんしょう。

用途ようと

シミュレーション実験じっけんや、（暗号あんごう論ろん的てき擬似ぎじ乱数らんすうは）暗号あんごうなどに利用りようされている。真しんに良質りょうしつな乱数らんすう列れつを得えようとするのは意外いがいに厄介やっかいであるのに対たいし、擬似ぎじ乱数らんすうでは前提ぜんてい条件じょうけんが同おなじならば、まったく同おなじ乱数らんすう列れつを生成せいせいできる。このため、シミュレーション等とうにおいては同おなじ動作どうさを再現さいげんできるメリットがあるうえ、デバッグも可能かのうとなる。

なお、暗号あんごう生成せいせいの際さい、再現さいげん性せいを利用りようしてシード値ちの選択せんたくを意図いと的てきに行おこなわれたりすると危険きけんがあるといった場合ばあい、何なんらかの方法ほうほうでそれを排除はいじょすることが必要ひつような（楕円だえん曲線きょくせん暗号あんごうのパラメータ生成せいせいなど）用途ようともある。

主おもな擬似ぎじ乱数らんすう生成せいせい法ほう

様々さまざまな擬似ぎじ乱数らんすう生成せいせい法ほうが知しられている。

• 一般いっぱん的てき生成せいせい法ほう（方式ほうしきと過去かこの出力しゅつりょくが既知きちであれば、未来みらいの出力しゅつりょくを予測よそく可能かのう）
  • 古典こてん的てき生成せいせい法ほう - 平方へいほう採と中ちゅう法ほう
  • 比較的ひかくてき古ふるい生成せいせい法ほう - 線形せんけい合同ごうどう法ほう（乗算じょうざん合同ごうどう法ほう・混合こんごう合同ごうどう法ほう）、線形せんけい帰還きかんシフトレジスタ
  • 比較的ひかくてき新あたらしい生成せいせい法ほう - メルセンヌ・ツイスタ、キャリー付つき乗算じょうざん、Xorshift、Lagged Fibonacci 法ほう、RANLUX、Permuted congruential generator
• 暗号あんごう学がく的てきに安全あんぜんな生成せいせい法ほう（方式ほうしきと過去かこの出力しゅつりょくから未来みらいの出力しゅつりょくが予測よそく困難こんなんで、現在げんざいの状態じょうたいから過去かこの出力しゅつりょくが予測よそく不可能ふかのう）
  • BBS(Blum-Blum-Shub)、Fortuna
• （参考さんこう）擬似ぎじ乱数らんすうではない、真しんの乱数らんすうの生成せいせい法ほう
  • ハードウェア乱数らんすう生成せいせい器き - サイコロ、熱ねつ雑音ざつおん、宇宙うちゅう線せんなどを利用りようする物理ぶつり乱数らんすう

平方へいほう採と中ちゅう法ほう (middle-square method)

もっとも古ふるい手法しゅほうで、1946年ねん頃ごろ、ノイマンが提案ていあんした。TAOCPの新あたらしい訳本やくほんでは二に乗じょう中ちゅう抜ぬき法ほうと呼よんでいる。

まず、適当てきとうに初期しょき値ちを決きめる。以下いか、その(乱らん)数すうを 2 乗じょうした値ねの中央ちゅうおうにある必要ひつような桁数けたすうを採とって次つぎの乱数らんすうとする。これを繰くり返かえして乱数らんすう列れつとする方法ほうほう。ここで「中央ちゅうおう」とは、求もとまった値ねを必要ひつような桁数けたすうの 2 倍ばいの桁数けたすうとして見みた時ときの中央ちゅうおうである。たとえば、4 桁けたを必要ひつようとしていて、求もとまった値ねが 7 桁けたの時ときは、最さい上位じょういの前まえの位くらい（千万せんまんの位い）に「0」を付つけ足たして 8 桁けたとする（下したの例れいを参照さんしょう）。

（例れい）4 桁けたの擬似ぎじ乱数らんすうを作つくってみる。初期しょき値ちを1763とする。

1763² = 03108169 → 1081

1081² = 01168561 → 1685

1685² = 02839225 → 8392

8392² = 70425664 → 4256

4256² = 18113536 → 1135

…

こうして、擬似ぎじ乱数らんすう列れつ {1763, 1081, 1685, 8392, 4256, 1135, …} を得える。

計算けいさんの結果けっか、過去かこに現あらわれた数かずと同おなじ数すうが現あらわれればループとなり、その長ながさを周期しゅうきと言いうが、線形せんけい合同ごうどう法ほうを使つかえば周期しゅうきが最長さいちょうのものが理論りろん的てきに可能かのうであるため、現代げんだいにおいて平方へいほう採と中ちゅう法ほうが利用りようされることはまずない。

線形せんけい合同ごうどう法ほう (linear congruential method)

詳細しょうさいは「線形せんけい合同ごうどう法ほう」を参照さんしょう

線形せんけい合同ごうどう法ほうの

$X_{n+1}=\left(A\times X_{n}+B\right){\bmod {M}}$

において、B=0 の場合ばあいを区別くべつして特とくに乗算じょうざん合同ごうどう法ほう、B>0 の場合ばあいを区別くべつして特とくに混合こんごう合同ごうどう法ほうと言いうことがある。

線形せんけい帰還きかんシフトレジスタ

詳細しょうさいは「線形せんけい帰還きかんシフトレジスタ」を参照さんしょう

線形せんけい帰還きかんシフトレジスタ (Linear Feedback Shift Register, LFSR) はデジタル回路かいろを用もちいて容易よういに実装じっそうすることができる。特性とくせい多項式たこうしきを適切てきせつに選択せんたくすることによって、等とう頻度ひんど性せい、無む相関そうかん性せい及および周期しゅうきが保証ほしょうされる。乱数らんすうとしては最長さいちょう周期しゅうきを保証ほしょうするM系列けいれつを使つかう。

新あたらしい擬似ぎじ乱数らんすう生成せいせいアルゴリズム

上記じょうきのような古典こてん的てき擬似ぎじ乱数らんすう生成せいせい法ほうの欠点けってんを克服こくふくした、新あたらしい擬似ぎじ乱数らんすう生成せいせい法ほうがいくつか考案こうあんされている。

メルセンヌ・ツイスタの他ほか、キャリー付つき乗算じょうざん、Xorshift、Lagged Fibonacci 法ほう、Permuted congruential generator など。

メルセンヌ・ツイスタ

詳細しょうさいは「メルセンヌ・ツイスタ」を参照さんしょう

その他たの生成せいせい法ほう

カオス乱数らんすう

非線形ひせんけい微分びぶん方程式ほうていしきの解かいはカオスで、即すなわち初期しょき値ち敏感びんかん性せい等とうの性質せいしつを持もつ。これを漸やや化か式しきとして、カオス的てきな関数かんすうを得える。よく使つかわれる関数かんすうにロジスティック写像しゃぞうやテント写像しゃぞうがある。ロジスティック写像しゃぞう#擬似ぎじ乱数らんすう生成せいせい器きを参照さんしょう。

暗号あんごう論ろん的てき擬似ぎじ乱数らんすう

詳細しょうさいは「暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器き」を参照さんしょう

一般いっぱんの擬似ぎじ乱数らんすうは、その方式ほうしきと過去かこの出力しゅつりょくが既知きちであれば、未来みらいの出力しゅつりょくを予測よそく可能かのうであるため、暗号あんごうの用途ようとには不適ふてき（暗号あんごう学がく的てきに安全あんぜんではないと言いう）である。

暗号あんごう理論りろんでは擬似ぎじ乱数らんすう（生成せいせい器き）に明確めいかくな定義ていぎがある。すなわち、多項式たこうしき時間じかんの計算けいさん機きが乱数らんすう列れつと識別しきべつ不能ふのうな列れつを出力しゅつりょくする機器ききのことを、暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器きと呼よび、この列れつに含ふくまれる数かずを暗号あんごう論ろん的てき擬似ぎじ乱数らんすうという。いかなる数列すうれつであれば乱数らんすう列れつであるか、議論ぎろんのあるところではあるが、一様いちよう分布ぶんぷであることと過去かこの数かずから次つぎの数かずが予測よそく不能ふのうであることは同値どうちであることが示しめされている（Yao）。そこで過去かこの数かずから次つぎの数かずが予測よそく不能ふのうであるかで、暗号あんごう論ろん的てき擬似ぎじ乱数らんすうか否ひかを区別くべつする。

暗号あんごう理論りろんでは擬似ぎじ乱数らんすうに厳密げんみつな定義ていぎが与あたえられている。Σしぐま = {0,1}とする。自然しぜん数すう k に対たいし、Σしぐま^k 上うえの一様いちよう分布ぶんぷを U_k と表あらわす。確かく率りつ変数へんすうの族ぞく {X_k}_k∈N が、一様いちよう分布ぶんぷの族ぞく {U_k}_k∈N と計算けいさん量的りょうてき識別しきべつ不能ふのうな時とき、族ぞく {X_k}_k∈N は暗号あんごう論ろん的てき擬似ぎじ乱数らんすうであるという。

次つぎに暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器きの厳密げんみつな定義ていぎをする。l(k) を l(k) > k を満みたす多項式たこうしきとする。G を多項式たこうしき時間じかんアルゴリズムで、G に k ビットのビット列びっとれつを入力にゅうりょくをすると l(k) ビットの出力しゅつりょくを返かえすものとする。すると G(U_k) は Σしぐま^l(k) 上うえの確かく率りつ分布ぶんぷである。確かく率りつ分布ぶんぷの族ぞく {G(U_k)}_k∈N が暗号あんごう論ろん的てき擬似ぎじ乱数らんすうである時とき、多項式たこうしき時間じかんアルゴリズム G を暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器きという。

一方いっぽう向性こうせい関数かんすうが存在そんざいすれば暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器きが存在そんざいする事ことが知しられている。

実際じっさいの生成せいせい法ほうとしては、一般いっぱんの擬似ぎじ乱数らんすう列れつを暗号あんごう学がく的てきハッシュ関数かんすうに通とおす、という、簡単かんたんな構成こうせい法ほうがある。