擬似乱数
 | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 (2016年9月) |
擬似乱数（ぎじらんすう、pseudorandom numbers）は、乱数列のように見えるが、実際には確定的な計算によって求めている擬似乱数列による乱数。擬似乱数列を生成する機器を擬似乱数列生成器、生成アルゴリズムを擬似乱数列生成法と呼ぶ。
真の乱数列は本来、規則性も再現性もないものであるため、本来は確定的な計算によって求めることはできない（例：サイコロを振る時、今までに出た目から次に出る目を予測するのは不可能）。一方、擬似乱数列は確定的な計算によって作るので、その数列は確定的であるうえ、生成法と内部状態が既知であれば、予測可能でもある。
ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。
しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。
用途
シミュレーション実験や、（暗号論的擬似乱数は）暗号などに利用されている。真に良質な乱数列を得ようとするのは意外に厄介であるのに対し、擬似乱数では前提条件が同じならば、まったく同じ乱数列を生成できる。このため、シミュレーション等においては同じ動作を再現できるメリットがあるうえ、デバッグも可能となる。
なお、暗号生成の際、再現性を利用してシード値の選択を意図的に行われたりすると危険があるといった場合、何らかの方法でそれを排除することが必要な（楕円曲線暗号のパラメータ生成など）用途もある。
主な擬似乱数生成法
様々な擬似乱数生成法が知られている。
- 一般的生成法（方式と過去の出力が既知であれば、未来の出力を予測可能）
- 古典的[注釈 1]生成法 - 平方採中法
- 比較的古い[注釈 2]生成法 - 線形合同法（乗算合同法・混合合同法）、線形帰還シフトレジスタ（M系列）
- 比較的新しい[注釈 3]生成法 - メルセンヌ・ツイスタ、キャリー付き乗算、Xorshift、Lagged Fibonacci 法、RANLUX、Permuted congruential generator、64ビット最適均等分布F2-線形発生法
- 暗号学的に安全な生成法（方式と過去の出力から未来の出力が予測困難で、現在の状態から過去の出力が予測不可能）
- BBS(Blum-Blum-Shub)、Fortuna
- （参考）擬似乱数ではない、真の乱数の生成法
- ハードウェア乱数生成器 - サイコロ、熱雑音、宇宙線などを利用する物理乱数
平方採中法 (middle-square method)
もっとも古い手法で、1946年頃、ノイマンが提案した。TAOCPの新しい訳本では二乗中抜き法と呼んでいる。
まず、適当に初期値を決める。以下、その(乱)数を 2 乗した値の中央にある必要な桁数を採って次の乱数とする。これを繰り返して乱数列とする方法。ここで「中央」とは、求まった値を必要な桁数の 2 倍の桁数として見た時の中央である。たとえば、4 桁を必要としていて、求まった値が 7 桁の時は、最上位の前の位（千万の位）に「0」を付け足して 8 桁とする（下の例を参照）。
（例）4 桁の擬似乱数を作ってみる。初期値を1763とする。
- 17632 = 03108169 → 1081
- 10812 = 01168561 → 1685
- 16852 = 02839225 → 8392
- 83922 = 70425664 → 4256
- 42562 = 18113536 → 1135
- …
こうして、擬似乱数列 {1763, 1081, 1685, 8392, 4256, 1135, …} を得る。
計算の結果、過去に現れた数と同じ数が現れればループとなり、その長さを周期と言うが、線形合同法を使えば周期が最長のものが理論的に可能であるため、現代において平方採中法が利用されることはまずない。
線形合同法 (linear congruential method)
線形合同法の
- 擬似乱数生成器のページへのリンク
