（ c ）
乱数は、データを交換できる各マシンによって常に生成されます。 また、データを交換しない場合でも、各コンピューターはメモリ内のプログラムを配布するためにランダム性が必要です。 この場合、もちろん、決定論的なシステムとしてのコンピューターは、真の乱数を作成できません。
ランダム（または擬似ランダム）番号ジェネレーターになると、ストーリーは常に真のランダム性の検索を中心に構築されます。 真剣な数学者は何十年もの間、事故と見なされるものについて議論してきたが、実際には、「正しい」エントロピーを使用することを長い間学んできた。 ただし、「ノイズ」は氷山の一角にすぎません。
最も強力なPRNGおよびTRNGアルゴリズムのもつれを解明したい場合、どこから始めればよいでしょうか？ 実際、どのアルゴリズムを扱っていても、シード、事前定義された定数のテーブル、および数式の3つの柱があります。
シードが何であれ、真の乱数ジェネレーターに関係するアルゴリズムはまだあり、そのようなアルゴリズムは決してランダムではありません。
ランダム性とは
ランダムシーケンスの最初の適切な定義は、20世紀で最も偉大な数学者の1人であるAndrei Kolmogorovの学生であるスウェーデンの統計学者PerMartin-Löfによって1966年に与えられました。 以前は、研究者はランダムシーケンスを、すべてのランダムテストに合格したシーケンスとして定義しようとしました。
Martin-Löfの主なアイデアは、 計算可能性理論を使用して、ランダム性テストの概念を正式に定義することでした。 これは、確率の可能性という考えとは対照的です。 この理論では、サンプリング空間の特定の要素をランダムと呼ぶことはできません。
Martin-Löfのアイデアの「ランダムシーケンス」は典型的なものである必要があります。 個別の特徴を持たないようにしてください。
Martin-Löfのランダム性は、多くの同等の特性を認めることが示されました。それぞれの特性は、ランダムシーケンスが持つべき特性に関する直感的なアイデアを満たします。
- 非圧縮性;
- ランダム性の統計的検定に合格。
- 予測の難しさ。
Martin-Löfのランダム化の複数の定義の存在と、異なる計算モデルでのこれらの定義の安定性は、Martin-Löfのランダム性が数学の基本的な特性であることを示しています。
シード：擬似ランダムアルゴリズムの基礎
乱数を生成する最初のアルゴリズムは、乗算、除算、加算、減算、平均値の取得など、いくつかの基本的な算術演算を実行しました。 今日、FortunaやYarrow（FreeBSD、AIX、Mac OS X、NetBSDで使用）などの強力なアルゴリズムは、妄想のための乱数ジェネレーターのように見えます。 たとえば、Fortunaは、220バイトのランダムデータに対する各要求を満たした後、さらに256ビットの擬似ランダムデータが生成され、新しい暗号化キーとして使用される暗号ジェネレーターです。古いキーは毎回破棄されます。
最も単純なアルゴリズムが暗号的に堅牢な擬似乱数ジェネレーターに進化するまでに何年もかかりました。 部分的にこのプロセスは、Cの1つの数学関数の操作の例で追跡できます。
rand（）関数は、Cで最も単純な乱数生成関数です。
#include <stdio.h> #include <stdlib.h> int main() { int r,a,b; puts("100 Random Numbers"); for(a=0;a<20;a++) { for(b=0;b<5;b++) { r=rand(); printf("%dt",r); } putchar('n'); } return(0); }
このランダム化の例では、ネストされたループを使用して100個のランダムな値を表示します。 rand（）関数は多くのランダムな値を作成するのに適していますが、それらは予測可能です。 結論を予測しにくくするには、乱数ジェネレータにシードを追加する必要があります-これはsrand（）関数を使用して行われます。
シードは開始番号であり、擬似乱数列が開始するポイントです。 疑似乱数ジェネレーターは、単一の初期値を使用します。この初期値から、疑似乱数が生成されます。 真の乱数ジェネレーターは、常に最初にさまざまなエントロピーのソースによって提供される高品質のランダム変数を持っています。
#include <stdio.h> #include <stdlib.h> int main() { unsigned seed; int r,a,b; printf("Input a random number seed: "); scanf("%u",&seed); srand(seed); for(a=0;a<20;a++) { for(b=0;b<5;b++) { r=rand(); printf("%dt",r); } putchar('n'); } return(0); }
srand（）は数値を受け取り、それを開始点として配置します。 シードが設定されていない場合、プログラムが起動するたびに同じ乱数が取得されます。
「古典」からの単純な乱数式の例は次のとおりです。KerniganとRichieの著書「Programming Language C」は、1978年にすでに出版されています。
int rand() { random_seed = random_seed * 1103515245 +12345; return (unsigned int)(random_seed / 65536) % 32768; }
この式は、もともといくつかの番号で指定されたrandom_seedと呼ばれる変数の存在を前提としています。 変数random_seedは1 103 535 245で乗算され、12 345が結果に追加されます。 random_seedは、この新しい値に置き換えられます。 これは実際にはかなり良い擬似乱数ジェネレータです。 これを使用して0〜9の乱数を作成すると、シード= 10のときに返される最初の20個の値は次のようになります。
44607423505664567674
0から9までの10,000個の値がある場合、分布は次のようになります。
0-10151-10242-10483-9964-9885-10016-9967-10068-9659-961
擬似乱数式は、初期値に依存します。 1台のコンピューターでrand（）seed 10関数を提供し、それが生成する数値のストリームを見ると、結果は、seed 10を持つ他のコンピューターで作成された「ランダムシーケンス」と同じになります。
残念ながら、乱数ジェネレータには別の弱点があります。以前に起こったことに基づいて、次に何が起こるかをいつでも予測できます。 シーケンスの次の番号を取得するには、ジェネレーターの最後の内部状態、いわゆる状態を常に覚えておく必要があります。 状態がなければ、同じ答えを得るために同じ数字で同じ数学演算を再び行います。
各ケースでシードを一意にする方法は？ 最も明らかな解決策は、現在のシステム時間を計算に追加することです。 これは、time（）関数を使用して実行できます。
#include <stdio.h> #include <stdlib.h> #include <time.h> int main() { int r,a,b; srand((unsigned)time(NULL)); for(a=0;a<20;a++) { for(b=0;b<5;b++) { r=rand(); printf("%dt",r); } putchar('n'); } return(0); }
time（）関数は、現在の時刻に関する情報、常に変化する値を返します。 型キャストメソッドは、time（）関数によって返される値が整数であることを保証します。
したがって、「ランダムな」システム時間を追加した結果、rand（）関数は、最初の例で取得した値よりもランダムな値を生成します。
ただし、この場合、シードはシステム時間またはアプリケーションの起動時間を知ることで推測できます。 原則として、乱数が絶対に重要なアプリケーションでは、代替ソリューションを見つけることが最善です。
.netフレームワークには System.Security.Cryptography.RandomNumberGenerator 関数があり、次の要素が計算で考慮されます。
- 現在のプロセスのID。
- 現在のスレッドID。
- ロード後のサンプル数。
- 現在の時刻。
- プロセッサパフォーマンスのさまざまな高精度カウンタ。
- ユーザー環境のMD4ハッシュ（ユーザー名、コンピューター名など）。
ただし、これらの数値はすべてランダムではありません。
決定論的な擬似乱数ジェネレータでできる最善のことは、物理現象のエントロピーを追加することです。
発電機の期間（サイクル）
擬似乱数を生成するために最も一般的に使用される方法の1つは、 線形合同法のさまざまな変更です。
X n + 1 =（aX n + c）mod m。ここで、mは係数、aは係数、cは増分、modは除算の剰余を取る操作です。 さらに、m> 0、0 <a≤m、0 <c≤m、初期値X 0も指定されます：0 <X 0≤m。
線形合同法は反復シーケンスを提供します—合同シーケンスは常に「ループ」を形成します。 無限の回数繰り返されるこのサイクル（期間）は、X n + 1 = f（n）の形式のすべてのシーケンスのプロパティです。
Cでは、線形合同法は、すでによく知っているrand（）関数で実装されます。
#define RAND_MAX 32767 unsigned long next=1; int rand(void) { next=next*1103515245+12345; return((unsigned int)(next/65536)%RAND_MAX);} void srand(unsigned int seed) { next=seed; }
乱数に関するループとは何ですか？ ピリオドは、同じシーケンスで戻る前に生成される番号の数です。 たとえば、A5暗号の期間の数は平均2 23であり、攻撃の複雑さは240です。これにより、任意のパーソナルコンピューターで暗号を解読できます。
シードが1で、期間が100（Haskellの場合）の場合を考えます。
random i = (j, ans) where j = 7 * i `mod` 101 ans = (j — 1) `mod` 10 + 1 — just the ones place, but 0 means 10
その結果、次の答えが得られます。
random 1 —> ( 7, 7) random 7 —> (49, 9) random 49 —> (40, 10) random 40 —> (78, 8) random 78 —> (41, 1) random 41 —> (85, 5) random 85 —> (90, 10) random 90 —> (24, 4) random 24 —> (67, 7) random 67 —> (65, 5) random 65 —> (51, 1)
これは単なる例であり、実際の生活では同様の構造を使用していません。 Haskellでは、ランダムシーケンスを作成する場合、次のコードを使用できます。
random :: StdGen —> (Int, StdGen)
ランダムなIntを選択すると、Intと新しいStdGenが返されます。これを使用して、より多くの擬似乱数を取得できます。 Haskellを含む多くのプログラミング言語には、状態を自動的に記憶する乱数ジェネレータがあります（Haskellでは、これはrandomIOです）。
期間が長いほど、適切なランダム値を作成する信頼性は高くなりますが、数十億サイクルの場合でも、信頼できるシードを使用することは非常に重要です。 実際の乱数ジェネレーターは通常大気ノイズを使用します（ユーザーのマウスの動きから放射性崩壊まであらゆる物理現象を入れます）が、最後の心拍ストリーム間の間隔の長さや時間など、さまざまな破片の非同期ストリームをシードに追加することでソフトウェアメソッドを使用してチートすることもできます相互排除の期待（またはすべてを一緒に追加する方がよい）。
真のビットランダム性
したがって、実際の物理現象からのデータの混合物のシードを受け取った（または考えられる最大のソフトウェアデブリフローのセットで将来のクラッカーの寿命を可能な限り複雑にした）、値を繰り返して暗号アルゴリズムを追加する（または複雑な数学的な問題）エラーを保護するために状態を設定する、ランダムなシーケンスと見なすデータセットを取得します。 次は？
次に、最初の基本的な要件の1つであるテストに戻ります。
米国国立標準技術研究所は、「 暗号化アプリケーション用のランダムおよび擬似ランダム数ジェネレーターのための統計的テストスイート 」に15の基本チェックを投資しました。 それらは制限できますが、このパッケージはランダム性テストの「トップ」ではありません。
最も厳密な統計的検定の1つは、フロリダ州立大学のGeorge Marsaglia教授によって提案されました。 ダイハードテストには17種類のチェックが含まれ、そのうちのいくつかは非常に長いシーケンス（最低268メガバイト）を必要とします。
ランダム性は、モントリオール大学のPierre L'EcouilletとRichard Simardによって提示されたTestU01ライブラリを使用して確認できます。これには、古典的なテストといくつかのオリジナルのテストが含まれます。
ランダム性を定量化するための別の便利なサービス 。