擬似乱数

デジタル大辞泉

ぎじ‐らんすう【疑似乱数】

読み方：ぎじらんすう

乱数の代わりに用いられる数字の列。疑乱数。算術乱数。

[補説] コンピューターでは、さいころを振って出る目のような無秩序な数列は生成できないため、計算によってそれに似た数列を作り、乱数の代用とする。電子データの暗号化などに用いられる。

OR事典

擬似乱数

読み方：ぎじらんすう
【英】：pseudo-random numbers

サイコロを振って出る目（数）のようなものを乱数（列）というのに対して， 漸化式のような代数的方法（アルゴリズム）によって作り出される数（列）で， 一見すると乱数（列）のように見えるもののこと． 乱数列のような予測不能性（次に出る数を正確に当てることが不可能という性質）は持っていないが， 一様性などの性質は近似的に満たしていて， モンテカルロ法などでは，特に支障にならないことが多い．

詳しくは一様乱数を見よ

ウィキペディア

擬似乱数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/09/27 00:06 UTC 版)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "擬似乱数" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2016年9月）

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

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

ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを検定と言い、各種の方法が提案されている。

しかし、特に暗号に使用する擬似乱数列については注意が必要であり、シミュレーション等には十分な擬似乱数列生成法であっても、暗号にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については暗号論的擬似乱数の節および暗号論的擬似乱数生成器の記事を参照。

用途

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

なお、暗号生成の際、再現性を利用してシード値の選択を意図的に行われたりすると危険があるといった場合、何らかの方法でそれを排除することが必要な（楕円曲線暗号のパラメータ生成など）用途もある。

主な擬似乱数生成法

様々な擬似乱数生成法が知られている。

• 一般的生成法（方式と過去の出力が既知であれば、未来の出力を予測可能）
  • 古典的^{[注釈 1]}生成法 - 平方採中法
  • 比較的古い^{[注釈 2]}生成法 - 線形合同法（乗算合同法・混合合同法）、線形帰還シフトレジスタ
  • 比較的新しい^{[注釈 3]}生成法 - メルセンヌ・ツイスタ、キャリー付き乗算、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)

詳細は「線形合同法」を参照

線形合同法の

${\displaystyle 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 を暗号論的擬似乱数生成器という。

一方向性関数が存在すれば暗号論的擬似乱数生成器が存在する事が知られている。

実際の生成法としては、一般の擬似乱数列を暗号学的ハッシュ関数に通す、という、簡単な構成法がある。

脚注

[脚注の使い方]

注釈

1. ^ 現代では通常使われない
2. ^ 1980年代以前から使われている
3. ^ 1990年代以降に提案された

ウィキペディア小見出し辞書

擬似乱数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/25 05:10 UTC 版)

「M系列」の記事における「擬似乱数」の解説

重要な応用として擬似乱数列の生成がある。漸化式が原始多項式であることが必要充分条件となっていることから最長周期を数学的に確認することができる特徴がある。M系列を用いた擬似乱数生成法として、線形帰還シフトレジスタやメルセンヌ・ツイスタなどがある。 特に線形帰還シフトレジスタはハード的にもソフト的にも実装が容易で高速であることから広く利用されている。なお線形帰還シフトレジスタにおいては漸化式のことを帰還多項式という。また、帰還多項式が原始多項式ではない線形帰還シフトレジスタも存在する。 線形漸化式が差分方程式の解であることから、単体では暗号論的擬似乱数生成器にはならない。