乱数生成

乱数生成とは、多くの場合、乱数発生器（RNG：random number generator）を用いて、合理的に予測できないような数字や記号の列を生成する過程のことである。これは、特定の結果には、後知恵では検出可能だが先見性では予測不可能なパターンが含まれることを意味する。真の乱数発生器は、ハードウェア乱数発生器（HRNG：hardware random number generator）であり、各生成は、モデル化が実質的に不可能な方法で絶えず変化する物理的環境の属性の現在値の関数である。これは、PRNGによって行われるいわゆる「乱数生成」とは対照的で、乱数のように見えるだけで、実際には事前に決定された数値を生成する。
ランダム性の様々な応用により、ランダムデータを生成する様々な方法が開発されてきた。サイコロを転がす、コインをはじく、トランプをシャッフルする、易経の鋸草の茎を使うなど、よく知られた例だけでなく、数え切れないほどの技法が古くから存在している。しかし、これらの技法は人力であり統計学で重要な十分な乱数を大量に発生させるには、多くの労力と時間が必要だった。そのため、結果が乱数表として集められ、配布されることもあった。
擬似乱数生成にはいくつかの計算手法が存在する。生成した結果がどの程度予測不可能であるか（＝パターンがどの程度識別可能であるか）を測定することを目的とした乱数性の統計的検定では、成功の程度に差はあるものの、いずれも「真の乱数性」という目標には達していない。このため、一般に暗号などの用途には使えない。しかし、精密に設計された暗号的に安全な擬似乱数生成器（CSPRNGS：cryptographically secure pseudorandom number generators）も存在し、近年開発された暗号技術で使用するために特別に設計された機能を備えている。
用途と使用法.
乱数生成器は、ギャンブル、統計的サンプリング、コンピュータシミュレーション、暗号化、完全ランダム化設計等の予測不可能な結果を生成することが望ましい他の分野での使用が多い。一般的に、セキュリティアプリのような予測不可能性を最重要機能とするアプリでは、実行可能であれば、ハードウェア生成器は、一般的に擬似ランダムアルゴリズムよりも好まれ使用される傾向にある。
乱数生成は、モンテカルロ法によるシミュレーションを開発する際に非常に有用である。同じ乱数値から始めることで、同じ乱数列を再度実行することができ、デバッグが容易になるためである。乱数シードが秘密である限り、暗号にも使われる。送信者と受信者が同じ乱数セットを自動的に生成し、鍵として使用することができる。
疑似乱数生成は、コンピュータ・プログラミングにおいて重要かつ一般的な作業である。暗号技術や他の数値アルゴリズムでは非常に高度な見かけ上のランダム性が要求されるが、多くの演算では、ある程度の予測不可能性があればよい。簡単な例としては、ユーザーに「今日のランダムな言葉」を提示したり、コンピューターゲームでコンピューター制御の敵がどちらに動くかを決定したりすることがある。より弱い形のランダム性は、ハッシュアルゴリズムや、ソートアルゴリズムの作成に使用される。
一見するとランダム化に適しているように見えるアプリでも、実際にはそれほど完全な乱数ではない。例えば、BGMシステムのために音楽トラックを「ランダムに」選択するシステムなどが例である。
「真の」乱数と「疑似」乱数の比較.
乱数の生成には主に2つの方法がある。1つ目の方法は、ランダムであることが予想される物理現象を測定し、測定過程で起こりうる偏りを補正する方法である。例えば、大気による電気回路の乱れ、熱による電気回路の乱れ、その他外部からの電磁現象や量子現象の測定が挙げられる。例えば、短い時間スケールで測定される宇宙背景放射や放射性崩壊は、自然エントロピーの発生源となる。
自然発生源からエントロピーが得られる速度は、測定される根本的な物理現象に依存する。したがって、自然に発生する「真の」エントロピーの発生源は、妨害していると言われるつまり、需要を満たすのに十分なエントロピーが採取されるまで、速度が制限されることになる。ほとんどのLinuxディストリビューションを含むいくつかのUnix系システムでは、擬似デバイスファイル/dev/randomは、環境から十分なエントロピーが採取されるまでブロックする。このブロック動作のため、ハードディスクドライブをランダムビットで満たすような/dev/randomからの大規模な一括読み込みは、このタイプのエントロピーソースを使用するシステムでは、よく遅くなることがあるが決して不具合ではない。
2つ目の方法は、一見ランダムな結果の長いシーケンスを生成できる計算アルゴリズムを使用するもので、実際には、シード値またはキーとして知られる短い初期値によって完全に決定される。その結果、シード値がわかっていれば、一見ランダムに見えるシーケンス全体を再現することができる。この種の乱数発生器は、「擬似乱数発生器」と呼ばれる。このタイプのジェネレーターは通常、自然に発生するエントロピーのソースに依存しないが、例外もある。このタイプのジェネレーターは非妨害性であるため、外部イベントによってレートが制限されることがなく、大規模な一括読み取りが可能である。
乱数システムによっては、利用可能な場合は自然値から採取したランダム性を提供し、定期的に再シード化されるソフトウェアベースの暗号化された機密性な擬似乱数ジェネレータ（CSPRNG：cryptographically secure pseudorandom number generators）に依存するハイブリッドアプローチを採用している。後退が発生するのは、希望するランダム性の読み取り速度が、自然なハーベスティング・アプローチの能力を上回った場合である。このアプローチでは、より低速で純粋な手法に基づく乱数生成器のレート制限によるブロッキング動作を回避することが可能。
決定論のみに基づく疑似乱数生成器は、純粋な意味での「真の」乱数発生源と見なすことはできないが、実際には、要求の厳しいセキュリティアプリでも一般的に十分とされる。実装された擬似乱数生成器は、「黃系アルゴリズム」や「fortuna」のように、セキュリティ・クリティカルな暗号目的でも認証されることがある。それらは「FreeBSD」「AIX」「OSX」「NetBSD」などの /dev/randomはエントロピーの基礎となっている。OpenBSDでは、「arc4random」として知られる擬似乱数アルゴリズムを使用してる。
生成方法.
物理的な方法.
サイコロ、コイントス、ルーレットなど、乱数を発生させる最も初期の方法は、統計学や暗号学のほとんどの用途には時間がかかりすぎる傾向があるが、その結果が出るまでの間での興奮や期待はときに、楽しさに変化する。その為、主にゲームやギャンブルで現在も使用されている。
物理的乱数発生器は、量子力学の法則に従うと予測不可能な、本質的にランダムな原子または素粒子の物理現象に基づくことができる。エントロピーの発生源としては、放射性崩壊、熱雑音、ショット雑音、ツェナー・ダイオードのアバランシェ雑音、クロック・ドリフト、ハードディスクの読み書きヘッドの実際の動きのタイミング、ラジオ雑音などがある。しかし、物理現象やそれを測定するためのツールには、一般的に非対称性や系統的な偏りがあり、その結果は一様ではない。暗号ハッシュ関数のようなランダム性抽出器を使用することで、低いビットレートではあるが、一様でないランダムなソースからのビットの一様分布に近づけることができる。
光化学的カオスや増幅自然放出雑音などの広帯域光エントロピー源の出現は、物理乱数発生器の開発に大いに役立っている。その中でも光化学的カオスは、広帯域で振幅が大きいため、高速な乱数を物理的に生成できる可能性が高い。2013年にカオスレーザーを用いた高速リアルタイム物理乱数生成器のプロトタイプが作られた。
このエントロピー情報を収集する為、さまざまな方法が考案されてきた。その1つが、予測不可能なソースからのビデオストリームのフレームに対してハッシュ関数を実行する技術である。Lavarand氏は、多数の溶岩ランプの画像でこのテクニックを使用した。HotBits氏はガイガーミュラー計数管で放射性崩壊を測定し、Random.orgは通常のラジオで記録された大気中のノイズの振幅の変化を使用している。
一般的なエントロピー源は、システムを利用する人間の行動である。人間は、要求に応じてランダム性を生成するのに適していないが、混合戦略ゲームをする場面では、ランダムな動作をかなりうまく使い試合を展開する。セキュリティ関連のコンピューターソフトウェアの中には、ランダムキーの生成や擬似乱数ジェネレータの初期化に必要な十分なエントロピーを生成するために、ユーザに長時間のマウス操作やキーボード入力を要求するものがある。
計算方法.
ほとんどのコンピュータが生成する乱数はPRNGを使用している。PRNGは、優れたランダム特性を持つ長い乱数を自動的に生成することができるアルゴリズムだが、最終的には乱数列が繰り返される、あるいはメモリ使用量が際限なく増大する。このような乱数は多くの状況では問題ないが、エントロピー源として使用される電磁大気ノイズから生成される数値ほどランダムではない。このようなアルゴリズムによって生成される一連の値は、一般にシードと呼ばれる固定数によって決定される。最も一般的なPRNGの1つは線形合同法であり、これは漸化式を使用する。
ここで、a、b、mは大きな整数である。 formula_2は擬似乱数の系列としてXの次を表す。この式が生成できる乱数の最大数は係数mである。この再帰関係を行列に拡張することで、より長い周期と優れた統計的特性を持つことができる。単一の線形合同発生器の特定の非ランダム特性を避けるために、乗数係数aの値がわずかに異なる複数のこのような乱数発生器を並列に使用することができ、複数の異なる発生器の中から選択する「マスター」乱数発生器を使用することができる。
紙とペンで乱数を生成する簡単な方法は、ジョン・フォン・ノイマン氏が提案したいわゆる二乗法である。実装は簡単だが、その出力は質が低い。周期が非常に短く、出力列がほとんど常にゼロに収束してしまうなどの重大な弱点がある。最近の技術革新は、中間平方とノイマン数列を組み合わせることである。この方法は長い期間を通して高品質の出力を生み出すことが可能である。
ほとんどのコンピュータ・プログラミング言語には、乱数発生器を提供する関数やライブラリ・ルーチンが含まれている。これらは多くの場合、0から1の間で一様に分布するランダムなバイトまたはワード、あるいは浮動小数点数を提供するように設計されている。