乱数生成

乱数生成（らんすうせいせい、Random number generation）とは、多くの場合、乱数発生器（RNG：random number generator）を用いて、先験的に予測できないような数値や記号を生成する過程のことである。これは、特定の結果には、後知恵では検出可能だが先見性では予測不可能なパターンが含まれることを意味する。真の乱数発生器は、ハードウェア乱数生成器（HRNG：hardware random number generator）であり、各生成は、モデル化が実質的に不可能な方法で絶えず変化する物理的環境の属性の現在値の関数である。

サイコロは機械的乱数発生器の一例である。通常、サイコロを振ると、1から6までの乱数が得られる。

ランダム化などの様々な応用により、ランダムデータを生成する様々な方法が開発されてきた。サイコロを転がす、コインをはじく、トランプをシャッフルする、易経の鋸草の茎を使うなど、よく知られた例だけでなく、数え切れないほどの技法が古くから存在している。しかし、これらの技法は人力であり統計学で重要な十分な乱数を大量に発生させるには、多くの労力と時間が必要だった。そのため、結果が乱数表として集められ、配布されることもあった。

一方の、擬似乱数の生成手法もいくつも提案されている。それらが生成した結果がどの程度予測不可能であるか（＝パターンがどの程度識別可能であるか）を測定することを目的とした乱数性の統計的検定も多数提案されているが、程度に差はあるものの、これを達成すれば「真の乱数といえる」というような唯一の指標といったようなものは無い（不可能である）。そのため、暗号などの用途によっては擬似ではない乱数が必要である。暗号でも用途によっては決定的な暗号論的擬似乱数生成器（CSPRNGS：cryptographically secure pseudorandom number generators）でもよく、それらは暗号技術で使用するために特別に設計され、必要な能力を持っている。

用途と使用法

乱数生成器は、ギャンブル、統計的サンプリング、コンピュータシミュレーション、暗号化、完全ランダム化設計等の予測不可能な結果を生成することが望ましい他の分野での使用が多い。一般的に、セキュリティのような予測不可能性を最重要機能とする用途では、必要な場合には、ハードウェア生成器が、一般的に擬似乱数よりも使用される。

擬似乱数は、モンテカルロ法によるシミュレーションを開発する際に非常に有用である。同じ種（シード。しばしばランダムシードと呼ばれる）から始めることで、同じ乱数列を再度実行することができ、デバッグが容易になるためである。暗号では、シードを秘密にし、また暗号的な強度のある乱数列生成器を使用する。送信者と受信者が同じシードを「鍵」として使用する（ストリーム暗号）。

擬似乱数の生成は、コンピュータ・プログラミングにおいて重要かつ一般的な作業である。暗号技術や他の数値アルゴリズムでは非常に高度な見かけ上のランダム性が要求されるが、多くの演算では、ある程度の予測不可能性があればよい。簡単な例としては、ユーザーに「今日のランダムな言葉」を提示したり、コンピューターゲームでコンピューター制御の敵がどちらに動くかを決定したりすることがある。アルゴリズムの視点からは、ハッシュ関数には用途により弱いあるいは強いランダム性が必要であり、乱択アルゴリズムではランダムさの品質が結果に影響することがある。

一見するとランダム化に適しているように見えるアプリでも、実際にはそれほど完全な乱数ではない。例えば、BGMシステムのために音楽トラックを「ランダムに」選択するシステムなどが例である。

「真の」乱数と「疑似」乱数の比較

乱数生成、すなわち乱数列の生成には主に2つの方法がある。1つ目の方法は、ランダムであることが予想される物理現象を測定し、測定過程で起こりうる偏りを補正する方法である。例えば、大気による電気回路の乱れ、熱による電気回路の乱れ、その他外部からの電磁現象や量子現象の測定が挙げられる。例えば、短い時間スケールで測定される宇宙背景放射や放射性崩壊は、自然エントロピーの発生源となる。

自然発生源からエントロピーが得られる速度は、測定される根本的な物理現象に依存する。したがって、自然に発生する「真の」エントロピーの発生源は、妨害していると言われるつまり、需要を満たすのに十分なエントロピーが採取されるまで、速度が制限されることになる。ほとんどのLinuxディストリビューションを含むいくつかのUnix系システムでは、擬似デバイスファイル/dev/randomは、環境から十分なエントロピーが採取されるまでブロックする。このブロック動作のため、ハードディスクドライブをランダムビットで満たすような/dev/randomからの大規模な一括読み込みは、このタイプのエントロピーソースを使用するシステムでは、よく遅くなることがあるが決して不具合ではない。

2つ目の方法は、一見ランダムな結果の長いシーケンスを生成できる計算アルゴリズムを使用するもので、その乱数列は擬似乱数列と呼ばれる。擬似乱数列は、シード値またはキーとして知られる短い初期値によって完全に決定される。その結果、シード値がわかっていれば、一見ランダムに見えるシーケンス全体を再現することができる。この種の乱数発生器を、擬似乱数発生器と呼ぶ。このタイプのジェネレーターは非妨害性であるため、外部イベントによってレートが制限されることがなく、大規模な一括読み取りが可能である。

乱数システムによっては、利用可能な場合は自然値から採取したランダム性を利用し、定期的に再シード化されるソフトウェアベースの擬似乱数ジェネレータにをバックアップに利用するハイブリッドアプローチを採用している。フォールバックが発生するのは、希望するランダム性の読み取り速度が、自然なハーベスティング・アプローチの能力を上回った場合である。このアプローチでは、より低速で純粋な手法に基づく乱数生成器のレート制限によるブロッキング動作を回避することが可能である。

決定論のみに基づく疑似乱数生成器は、純粋な意味での「真の」乱数発生源と見なすことはできないが、要求の厳しいセキュリティアプリでも一般的に十分な場合もある。そういった場合に必要とされる乱数生成器は暗号論的擬似乱数生成器と呼ばれ、Yarrow algorithmやfortunaのように、セキュリティ・クリティカルな暗号目的でも利用可能だと認証されている。それらは「FreeBSD」「AIX」「OSX」「NetBSD」などの /dev/randomが提供するエントロピーの基礎となっている。OpenBSDでは、「arc4random」として知られる擬似乱数アルゴリズムを使用している。

生成方法

物理的な方法

「ハードウェア乱数生成器」も参照

サイコロ、コイントス、ルーレットなど、乱数を発生させる最も初期の方法は、統計学や暗号学のほとんどの用途には時間がかかりすぎる傾向があるが、その結果が出るまでの間での興奮や期待はときに、楽しさに変化する。その為、主にゲームやギャンブルで現在も使用されている。

物理的乱数発生器は、量子力学の法則に従うと予測不可能な、本質的にランダムな原子または素粒子の物理現象に基づくことができる。エントロピーの発生源としては、放射性崩壊、熱雑音、ショット雑音、ツェナー・ダイオードのアバランシェ雑音、クロック・ドリフト、ハードディスクの読み書きヘッドの実際の動きのタイミング、ラジオ雑音などがある。しかし、物理現象やそれを測定するためのツールには、一般的に非対称性や系統的な偏りがあり、その結果は一様ではない。暗号ハッシュ関数のようなランダム性抽出器を使用することで、低いビットレートではあるが、一様でないランダムなソースからのビットの一様分布に近づけることができる。

光化学的カオスや増幅自然放出雑音などの広帯域光エントロピー源の出現は、物理乱数発生器の開発に大いに役立っている。その中でも光化学的カオスは、広帯域で振幅が大きいため、高速な乱数を物理的に生成できる可能性が高い。2013年にカオスレーザーを用いた高速リアルタイム物理乱数生成器のプロトタイプが作られた。

このエントロピー情報を収集する為、さまざまな方法が考案されてきた。その1つが、予測不可能なソースからのビデオストリームのフレームに対してハッシュ関数を実行する技術である。Lavarand氏は、多数の溶岩ランプの画像でこのテクニックを使用した。HotBits氏はガイガーミュラー計数管で放射性崩壊を測定し、Random.orgは通常のラジオで記録された大気中のノイズの振幅の変化を使用している。

一般的なエントロピー源は、システムを利用する人間の行動である。人間は、要求に応じてランダム性を生成するのに適していないが、混合戦略ゲームをする場面では、ランダムな動作をかなりうまく使い試合を展開する。セキュリティ関連のコンピューターソフトウェアの中には、ランダムキーの生成や擬似乱数ジェネレータの初期化に必要な十分なエントロピーを生成するために、ユーザに長時間のマウス操作やキーボード入力を要求するものがある。

擬似乱数

「擬似乱数」を参照

ほとんどのコンピュータが生成する乱数は擬似乱数生成器（PseudoRandom Number Generator: 以下PRNG）を使用している。PRNGは、優れたランダム特性を持つ長い乱数を自動的に生成することができるアルゴリズムだが、最終的には乱数列が繰り返される、あるいはメモリ使用量が際限なく増大する。このような乱数は多くの状況では問題ないが、エントロピー源として使用される電磁大気ノイズから生成される数値ほどランダムではない。このようなアルゴリズムによって生成される一連の値は、一般にシードと呼ばれる固定数によって決定される。最も一般的なPRNGの1つは線形合同法であり、これは漸化式を使用する。

$X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m$

ここで、a、b、mは大きな整数である。 $X_{n+1}$は擬似乱数の系列としてXの次を表す。この式が生成できる乱数の最大数は係数$m-1$である。この再帰関係を行列に拡張することで、より長い周期と優れた統計的特性を持つことができる。単一の線形合同発生器の特定の非ランダム特性を避けるために、乗数係数aの値がわずかに異なる複数のこのような乱数発生器を並列に使用することができ、複数の異なる発生器の中から選択する「マスター」乱数発生器を使用することができる。

紙とペンで乱数を生成する簡単な方法は、ノイマンが提案したいわゆる二乗中抜き法である。実装は簡単だが、その出力は質が低い。出力列の周期が非常に短いか、不意にゼロに縮退してしまうなどの重大な弱点がある。

ほとんどのコンピュータ・プログラミング言語には、乱数発生器を提供する関数やライブラリ・ルーチンが含まれている。これらは多くの場合、0から1の間で一様に分布するランダムなバイトまたはワード、あるいは浮動小数点数を提供するように設計されている。