Nothing Special   »   [go: up one dir, main page]
コンテンツにスキップ

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集
削除された内容 追加された内容
ビジュアルウィキテキスト
 
(10人の利用者による、間の13版が非表示)
2行目: 2行目:
'''擬似乱数'''（ぎじらんすう、''{{lang|en|pseudorandom numbers}}''）は、[[乱数列]]のように見えるが、実際には確定的な計算によって求めている'''擬似乱数列'''による乱数。擬似乱数'''列'''を生成する機器を'''擬似乱数列生成器'''、生成[[アルゴリズム]]を'''擬似乱数列生成法'''と呼ぶ。
'''擬似乱数'''（ぎじらんすう、''{{lang|en|pseudorandom numbers}}''）は、[[乱数列]]のように見えるが、実際には確定的な計算によって求めている'''擬似乱数列'''による乱数。擬似乱数'''列'''を生成する機器を'''擬似乱数列生成器'''、生成[[アルゴリズム]]を'''擬似乱数列生成法'''と呼ぶ。


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


ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。一般に、さまざまな主として統計的な性質が、真の乱数列のそれと同じ（見分けがつかない）かどうかで、その乱数列の使用目的に適しているか否かを判断する。これを'''検定'''と言い、各種の検定法が提案されている。
ある擬似乱数列を、真の乱数列とみなして良いかを確実に決定することはできない。シミュレーション等の一般的な用途には、対象とする乱数列の<!--さまざまな主として-->統計的な性質が、使用対象とする目的に合致しているかどうかを判断する。これを'''検定'''と言い、各種の方法が提案されている。<!--真の乱数列のそれと同じ（見分けがつかない）かどうかで、その乱数列の判断することになるが、これを-->


ただし、特に暗号に関する擬似乱数列については、他の用途とは異なる注意が必要である。一般に、一般のシミュレーション等には十分な性能を持った擬似乱数列生成法であっても、[[暗号]]の応用には不適であり、そのまま使用してはならない。暗号で使用する擬似乱数列については[[#暗号論的擬似乱数|暗号論的擬似乱数の節]]および[[暗号論的擬似乱数生成器|暗号論的擬似乱数生成器の記事]]を参照。
しかし、特に暗号に使用する擬似乱数列については注意が必要であり、<!--他の用途とは異なる注意が必要である。一般に、一般の-->シミュレーション等には十分な<!--性能を持った-->擬似乱数列生成法であっても、[[暗号]]にそのまま使用できるとは限らない。暗号で使用する擬似乱数列については[[#暗号論的擬似乱数|暗号論的擬似乱数の節]]および[[暗号論的擬似乱数生成器|暗号論的擬似乱数生成器の記事]]を参照。


== 用途 ==
== 用途 ==
シミュレーション実験や、（暗号論的擬似乱数は）暗号などに利用されている。「真の」乱数の生成は、特に良質な乱数列を得ようとするのは意外に厄介であるのに対し、擬似乱数では、全く同じ初期状態から始めれば、全く同じ乱数列を生成できるため、シミュレーション等では再現ができるというメリットがある（シミュレーション自体、あるいはデバック等のために）。なお、暗号等には、再現性を利用してシード値の選択を意図的に行われたりすると危険があるといった場合、何らかの方法でそれを排除することが必要な（[[楕円曲線暗号]]のパラメータ生成など）用途もある。
シミュレーション実験や、（暗号論的擬似乱数は）暗号などに利用されている。真に良質な乱数列を得ようとするのは意外に厄介であるのに対し、擬似乱数では前提条件が同じならば、<!--初期状態から始めれば、-->まったく同じ乱数列を生成できる。このため、シミュレーション等においては同じ動作を再現できるメリットがあるうえ、<!--シミュレーション自体のみならず、-->デバッグも可能となる。
なお、暗号生成の際、再現性を利用してシード値の選択を意図的に行われたりすると危険があるといった場合、何らかの方法でそれを排除することが必要な（[[楕円曲線暗号]]のパラメータ生成など）用途もある。


== 主な擬似乱数生成法 ==
== 主な擬似乱数生成法 ==
様々な擬似乱数生成法が知られている。
様々な擬似乱数生成法が知られている。
*一般的生成法（方式と過去の出力が既知であれば、未来の出力を予測可能）
*一般的生成法（方式と過去の出力が既知であれば、未来の出力を予測可能）
**古典的<ref>現代では通常使われない</ref>生成法 - 平方採中法
**古典的<ref group="注釈">現代では通常使われない</ref>生成法 - 平方採中法
**比較的古い<ref>1980年代以前から使われている</ref>生成法 - [[線形合同法]]（乗算合同法・混合合同法）、[[線形帰還シフトレジスタ]]
**比較的古い<ref group="注釈">1980年代以前から使われている</ref>生成法 - [[線形合同法]]（乗算合同法・混合合同法）、[[線形帰還シフトレジスタ]]（[[M系列]]）
**比較的新しい<ref>1990年代以降に提案された</ref>生成法 - [[メルセンヌ・ツイスタ]]、[[キャリー付き乗算]]、[[Xorshift]]、[[Lagged Fibonacci 法]]<!--、カオス乱数--><!--←カオスについて、古典的方法に比べて良い乱数が得られるする出典があるまでは外して良いでしょう-->
**比較的新しい<ref group="注釈">1990年代以降に提案された</ref>生成法 - [[メルセンヌ・ツイスタ]]、[[キャリー付き乗算]]、[[Xorshift]]、[[Lagged Fibonacci 法]]<!--、カオス乱数--><!--←カオスについて、古典的方法に比べて良い乱数が得られるする出典があるまでは外して良いでしょう-->、[[RANLUX]]、[[Permuted congruential generator]]、[[64ビット最適均等分布F2-線形発生法]]
*[[暗号論的擬似乱数生成器|暗号学的に安全な生成法]]（方式と過去の出力から未来の出力が{{仮リンク|予測可能性|en|predictability|label=予測困難}}で、現在の状態から過去の出力が{{仮リンク|予測可能性|en|predictability|label=予測不可能}}）<!-- 有限の周期が存在する実装では「条件付き」で「実用上」は予測不可能であるが完全に「予測不可能」とはならない。 -->
*[[暗号論的擬似乱数生成器|暗号学的に安全な生成法]]（方式と過去の出力から未来の出力が{{仮リンク|予測可能性|en|predictability|label=予測困難}}で、現在の状態から過去の出力が{{仮リンク|予測可能性|en|predictability|label=予測不可能}}）<!-- 有限の周期が存在する実装では「条件付き」で「実用上」は予測不可能であるが完全に「予測不可能」とはならない。 -->
**BBS([[Blum-Blum-Shub]])、Fortuna
**BBS([[Blum-Blum-Shub]])、Fortuna
22行目: 24行目:
**[[ハードウェア乱数生成器]] - [[サイコロ]]、[[熱雑音]]、[[宇宙線]]などを利用する物理乱数
**[[ハードウェア乱数生成器]] - [[サイコロ]]、[[熱雑音]]、[[宇宙線]]などを利用する物理乱数


=== 平方採中法 (middle-square method) ===
=== 平方採中法 ({{en|middle-square method}}) ===
もっとも古い手法で、1946年頃、[[ジョン・フォン・ノイマン|ノイマン]]が提案した。TAOCPの新しい訳本では二乗中抜き法と呼んでいる。
もっとも古い手法で、1946年頃、[[ジョン・フォン・ノイマン|ノイマン]]が提案した。[[The Art of Computer Programming|TAOCP]]の新しい訳本では二乗中抜き法と呼んでいる。


まず、適当に初期値を決める。以下、その(乱)数を 2 乗した値の中央にある必要な桁数を採って次の乱数とする。これを繰り返して乱数列とする方法。ここで「中央」とは、求まった値を必要な桁数の 2 倍の桁数として見た時の中央である。たとえば、4 桁を必要としていて、求まった値が 7 桁の時は、最上位の前の位（千万の位）に「0」を付け足して 8 桁とする（下の例を参照）。
まず、適当に初期値を決める。以下、その(乱)数を 2 乗した値の中央にある必要な桁数を採って次の乱数とする。これを繰り返して乱数列とする方法。ここで「中央」とは、求まった値を必要な桁数の 2 倍の桁数として見た時の中央である。たとえば、4 桁を必要としていて、求まった値が 7 桁の時は、最上位の前の位（千万の位）に「0」を付け足して 8 桁とする（下の例を参照）。
37行目: 39行目:


<!--丁度中央にある丁度半分の桁数を取り出すことに数理的理由があるわけではないので、奇数桁取り出すような実装に問題はない、ためコメントアウト MetaNest → --><!--平方採中法は偶数桁を採る時にしか使えない。また、-->計算の結果、過去に現れた数と同じ数が現れればループとなり、その長さを周期と言うが、線形合同法を使えば周期が最長のものが理論的に可能であるため、現代において平方採中法が利用されることはまずない。<!-- [[線形合同法]]という記事があったので、コメントアウト
<!--丁度中央にある丁度半分の桁数を取り出すことに数理的理由があるわけではないので、奇数桁取り出すような実装に問題はない、ためコメントアウト MetaNest → --><!--平方採中法は偶数桁を採る時にしか使えない。また、-->計算の結果、過去に現れた数と同じ数が現れればループとなり、その長さを周期と言うが、線形合同法を使えば周期が最長のものが理論的に可能であるため、現代において平方採中法が利用されることはまずない。<!-- [[線形合同法]]という記事があったので、コメントアウト
== 線形合同法（linear congruential method） ==
== 線形合同法（{{en|linear congruential method}}） ==
1948年、レーマが提案
1948年、レーマが提案
適当な初期値<math>X_0</math>と、適当な定数<math>a</math>,<math>b</math>,<math>m</math>を定める。
適当な初期値<math>X_0</math>と、適当な定数<math>a</math>,<math>b</math>,<math>m</math>を定める。
44行目: 46行目:
-->
-->


=== 線形合同法 (linear congruential method) ===
=== 線形合同法 ({{en|linear congruential method}}) ===
{{Main|線形合同法}}
{{Main|線形合同法}}
線形合同法の
線形合同法の
63行目: 65行目:
=== 線形帰還シフトレジスタ ===
=== 線形帰還シフトレジスタ ===
{{Main|線形帰還シフトレジスタ}}
{{Main|線形帰還シフトレジスタ}}
[[線形帰還シフトレジスタ]] (LFSR; Linear Feedback Shift Register) はデジタル回路を用いて容易に実装することができる。特性多項式を適切に選択することによって、等頻度性、無相関性及び周期が保障される。乱数としては最長周期を保障する[[M系列]]を使う。
[[線形帰還シフトレジスタ]] ({{en|Linear Feedback Shift Register, LFSR}}) はデジタル回路を用いて容易に実装することができる。特性多項式を適切に選択することによって、等頻度性、無相関性及び周期が保証される。乱数としては最長周期を保証する[[M系列]]を使う。


== 新しい擬似乱数生成アルゴリズム ==
== 新しい擬似乱数生成アルゴリズム ==
上記のような古典的擬似乱数生成法の欠点を克服した、新しい擬似乱数生成法がいくつか考案されている。
上記のような古典的擬似乱数生成法の欠点を克服した、新しい擬似乱数生成法がいくつか考案されている。


メルセンヌ・ツイスタの他、[[キャリー付き乗算]]、[[Xorshift]]、[[Lagged Fibonacci 法]] など。
メルセンヌ・ツイスタの他、[[キャリー付き乗算]]、[[Xorshift]]、[[Lagged Fibonacci 法]]、[[Permuted congruential generator]] など。


=== メルセンヌ・ツイスタ ===
=== メルセンヌ・ツイスタ ===
75行目: 77行目:
== その他の生成法 ==
== その他の生成法 ==
=== カオス乱数 ===
=== カオス乱数 ===
非線形微分方程式の解は[[カオス]]で、即ち初期値敏感性等の性質を持つ。これを漸化式として、カオス的な関数を得る。よく使われる関数に[[ロジスティック写像]]や[[テント写像]]がある。[[ロジスティック写像#擬似乱数生成器]]を参照。
非線形微分方程式の解は[[カオス理論|カオス]]で、即ち初期値敏感性等の性質を持つ。これを漸化式として、カオス的な関数を得る。よく使われる関数に[[ロジスティック写像]]や[[テント写像]]がある。[[ロジスティック写像#擬似乱数生成器]]を参照。


== 暗号論的擬似乱数 ==
== 暗号論的擬似乱数 ==
85行目: 87行目:
暗号理論では擬似乱数に厳密な定義が与えられている。&Sigma; = {0,1}とする。自然数 ''k'' に対し、&Sigma;<sup>''k''</sup> 上の一様分布を ''U''<sub>''k''</sub> と表す。確率変数の族 {''X''<sub>''k''</sub>}<sub>''k''&isin;'''N'''</sub> が、一様分布の族 {''U''<sub>''k''</sub>}<sub>''k''&isin;'''N'''</sub> と[[計算量的識別不能]]な時、族 {''X''<sub>''k''</sub>}<sub>''k''&isin;'''N'''</sub> は'''暗号論的擬似乱数'''であるという。
暗号理論では擬似乱数に厳密な定義が与えられている。&Sigma; = {0,1}とする。自然数 ''k'' に対し、&Sigma;<sup>''k''</sup> 上の一様分布を ''U''<sub>''k''</sub> と表す。確率変数の族 {''X''<sub>''k''</sub>}<sub>''k''&isin;'''N'''</sub> が、一様分布の族 {''U''<sub>''k''</sub>}<sub>''k''&isin;'''N'''</sub> と[[計算量的識別不能]]な時、族 {''X''<sub>''k''</sub>}<sub>''k''&isin;'''N'''</sub> は'''暗号論的擬似乱数'''であるという。


次に暗号論的擬似乱数生成器の厳密な定義をする。''l''(''k'') を ''l''(''k'') &gt; ''k'' を満たす多項式とする。''G'' を[[多項式時間]]アルゴリズムで、''G'' に ''k'' ビットのビット列を入力をすると ''l''(''k'') ビットの出力を返すものとする。すると ''G''(''U''<sub>''k''</sub>) は &Sigma;<sup>''l''(''k'')</sup> 上の確率分布である。確率分布の族 {''G''(''U''<sub>''k''</sub>)}<sub>''k''&isin;'''N'''</sub> が暗号論的擬似乱数である時、[[多項式時間]]アルゴリズム ''G'' を'''暗号論的擬似乱数生成機'''という。
次に暗号論的擬似乱数生成器の厳密な定義をする。''l''(''k'') を ''l''(''k'') &gt; ''k'' を満たす多項式とする。''G'' を[[多項式時間]]アルゴリズムで、''G'' に ''k'' ビットのビット列を入力をすると ''l''(''k'') ビットの出力を返すものとする。すると ''G''(''U''<sub>''k''</sub>) は &Sigma;<sup>''l''(''k'')</sup> 上の確率分布である。確率分布の族 {''G''(''U''<sub>''k''</sub>)}<sub>''k''&isin;'''N'''</sub> が暗号論的擬似乱数である時、[[多項式時間]]アルゴリズム ''G'' を'''暗号論的擬似乱数生成器'''という。


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


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


== 注 ==
== 脚注 ==
{{脚注ヘルプ}}
<references/>
=== 注釈 ===
{{Notelist}}


{{DEFAULTSORT:きしらんすう}}
{{DEFAULTSORT:きしらんすう}}

2024年9月4日 (水) 08:25時点における最新版

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

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

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

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

用途

[編集]

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

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

主な擬似乱数生成法

[編集]

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

平方採中法 (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)

[編集]
詳細は「線形合同法」を参照

線形合同法の

において、B=0 の場合を区別して特に乗算合同法、B>0 の場合を区別して特に混合合同法と言うことがある。

線形帰還シフトレジスタ

[編集]
詳細は「線形帰還シフトレジスタ」を参照

線形帰還シフトレジスタ (Linear Feedback Shift Register, LFSR) はデジタル回路を用いて容易に実装することができる。特性多項式を適切に選択することによって、等頻度性、無相関性及び周期が保証される。乱数としては最長周期を保証するM系列を使う。

新しい擬似乱数生成アルゴリズム

[編集]

上記のような古典的擬似乱数生成法の欠点を克服した、新しい擬似乱数生成法がいくつか考案されている。

メルセンヌ・ツイスタの他、キャリー付き乗算、Xorshift、Lagged Fibonacci 法、Permuted congruential generator など。

メルセンヌ・ツイスタ

[編集]
詳細は「メルセンヌ・ツイスタ」を参照

その他の生成法

[編集]

カオス乱数

[編集]

非線形微分方程式の解はカオスで、即ち初期値敏感性等の性質を持つ。これを漸化式として、カオス的な関数を得る。よく使われる関数にロジスティック写像やテント写像がある。ロジスティック写像#擬似乱数生成器を参照。

暗号論的擬似乱数

[編集]
詳細は「暗号論的擬似乱数生成器」を参照

一般の擬似乱数は、その方式と過去の出力が既知であれば、未来の出力を予測可能であるため、暗号の用途には不適（暗号学的に安全ではないと言う）である。

暗号理論では擬似乱数（生成器）に明確な定義がある。すなわち、多項式時間の計算機が乱数列と識別不能な列を出力する機器のことを、暗号論的擬似乱数生成器と呼び、この列に含まれる数を暗号論的擬似乱数という。いかなる数列であれば乱数列であるか、議論のあるところではあるが、一様分布であることと過去の数から次の数が予測不能であることは同値であることが示されている（Yao）。そこで過去の数から次の数が予測不能であるかで、暗号論的擬似乱数か否かを区別する。

暗号理論では擬似乱数に厳密な定義が与えられている。Σ = {0,1}とする。自然数 k に対し、Σk 上の一様分布を Uk と表す。確率変数の族 {Xk}k∈N が、一様分布の族 {Uk}k∈N と計算量的識別不能な時、族 {Xk}k∈N は暗号論的擬似乱数であるという。

次に暗号論的擬似乱数生成器の厳密な定義をする。l(k) を l(k) > k を満たす多項式とする。G を多項式時間アルゴリズムで、G に k ビットのビット列を入力をすると l(k) ビットの出力を返すものとする。すると G(Uk) は Σl(k) 上の確率分布である。確率分布の族 {G(Uk)}k∈N が暗号論的擬似乱数である時、多項式時間アルゴリズム G を暗号論的擬似乱数生成器という。

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

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

脚注

[編集]
[脚注の使い方]

注釈

[編集]
  1. ^ 現代では通常使われない
  2. ^ 1980年代以前から使われている
  3. ^ 1990年代以降に提案された
「https://ja.wikipedia.org/w/index.php?title=擬似乱数&oldid=101718995」から取得