業界は静止していません。 1990年には、コンピューターによって生成された40ビットもの擬似乱数が数時間で推測できました[1]。 これまで、コンピューター上の擬似ランダム変数の質的特性は、経験豊富な数学者でさえ驚かされました。 乱数生成アルゴリズムのアプリケーションの多くの分野では、それらの生成方法の1つまたは別の欠点に関連する多くの制限があります。 既存の方法の改善は、トピックへの高い関心に貢献し、出版物の数とともに増加します。 この記事を、私の研究開発にとって非常に重要なモデリング手法の開発とランダムプロセスの生成への私の貢献としましょう。
背景
乱数生成方法の歴史を少し逸脱すると、確率論を追求する中で、開発者は極端な手段を講じる準備ができていたことがわかります。 1996年に、Lavarandと呼ばれる乱数ソースが発明され、発売されました。 数字を生成する方法は、装飾ランプ（溶岩ランプ）の写真を処理することに限定されました。溶岩ランプは、予測できない方法で外観を連続的に変化させました[2]。 また、通常のコンピューターの最初のランダム変数ジェネレーターについても言及する価値があります。 それらは1999年にIntelによって開発され、このコンポーネントはファームウェアハブと呼ばれていました。 生成方法は、抵抗の熱ノイズを記録し、その後増幅して、値を「0」と「1」の間で定期的に変更する制御信号として発振器を使用することで構成されました[3]。数字。
真の乱数を生成する主な問題は、アナログ要素の必須の存在のままです。擬似乱数を生成するためのデジタル方式の定性的特性は、国立標準技術研究所の多くの基準を満たしていないため、実際には、暗号化などの多くの応用問題の解決には絶対に不適切です。
図1乱数ジェネレーターのスキーム。
2012年4月、コード名「Ivy Bridge」と呼ばれるマイクロアーキテクチャを備えた最初のプロセッサが発売されました。 このアーキテクチャの特徴は、アナログ熱ノイズを直接使用して乱数を生成できるジェネレーターの存在でした[4]。 図1は、このようなジェネレーターの図を示しています。 一見したところ、理想的すぎます。なぜなら、「0」または「1」の同等の外観は、実際には達成不可能なインバーターの絶対的な同一性によってのみ達成できるからです。 したがって、生成された数値の不均一性を補正する必要があり、これは後処理で行われます。
一様分布則による乱数の生成
おそらく、ランダムプロセスをモデル化するための最も重要で不可欠な方法は、確率分布変数を生成する方法です。これは、任意の分布則でランダムプロセスをモデル化するアルゴリズムのほとんどがそれらに基づいているためです[5]。
ランダム変数を均等に分布させる最も一般的な方法は次のとおりです。
•乱数の表
•物理乱数ジェネレーター（ファームウェアハブや「Ivy Bridge」の乱数ジェネレーターなど）
•数式を使用したデジタルジェネレーターまたはセンサーの使用。
最後の段落で、生成の結果は擬似乱数であると言わなければなりません。 次の文が逆説的に聞こえるかもしれないが、そのような数値の主な欠点は、ほとんどの場合、予測しやすいことであり、いくつかの生成アルゴリズムでは、シーケンスは定期的に繰り返されるという特性も持っています。 いくつかの応用問題ではこれは受け入れられませんが、それにもかかわらず、コンピューターでの実装の単純さのために、最も広く使用されているのは均一分布法則を持つランダム変数を生成するこれらの方法です。
その中で、最も人気のあるものは次のとおりです。
•合同法。
•線形フィードバックシフトレジスタ（LFSR）を使用する方法。
今日まで、線形合同法は、MSVS [6]、MSVB [7]、Java [6]、Borland C / C ++ [6]、GCC [8]などの最も一般的なプログラミング環境で乱数を生成するために使用されます。 この方法の普及は、その有効性を示しています。
このクラスのメソッドの本質は、乱数Y（n）のシーケンスを計算することです。
Y（n + 1）=（x * Y（n）+ c）％m、
ここで、mはシーケンスが形成される値の数（m≥2）、％は除算の剰余、xは係数（0≤x <m）、sは増分（0≤c <m）、Y（0）は初期値です（0≤Y（0）<m）[9]。
得られた数値の確率論の定性的パラメーターは、数値m、x、c、Y（0）の選択に依存します。
おそらく最も一般的に使用されているのは、シフトレジスタを使用するメソッドのクラスです。 暗号化[10]（GSM、Bluetooth）とデジタルデバイステスト[11]の両方に不可欠です。 これらのアルゴリズムの1つをクロック分周器またはカウンターとして使用することへの参照があります[12]。 シフトレジスタを使用するアルゴリズムは、スクランブル問題でも使用されます[13]。
図2フィードバックシフトレジスタのスキーム
このアルゴリズムの最も簡単な実装を図2に示します。 シフトレジスタの初期状態を設定した後、それから各クロックサイクルからすべてランダムなビットが読み取られます。 次に、特定の実装に応じて、数値に対していくつかの数学演算が行われ、その結果はレジスタの「解放」ビットへのシフト後に書き込まれます。
おわりに
もちろん、乱数を生成するすべての方法が考慮されるわけではありません。 しかし、低空飛行ターゲットの角度を決定するためのアルゴリズムの合成のための確率論的な非定常プロセスのモデリングであろうと、暗号化とコードシーケンスのスクランブルであろうと、正確にそれらはさまざまな問題で普遍的に使用されます。 入力データを知らなくても、そのようなアルゴリズムの操作の結果を計算する可能性を考慮して、かなりのリソースを消費しますが、それらの改良の問題は非常に重要です。
使用されるソースのリスト：
[1] Goldberg、I. Randomness and the Netscape Browser / I. Goldberg、D. Wagner // Dr. ドブの日記。 -1996 .-- 1月、P.66-70。
[2]米国特許第7031991 B2アダマール変換オンラインランダムネステスト/ Laszlo Hars 17 apr。 2002年。
[3] 6月、B。Intel乱数ジェネレーター/ B. 6月、P。コッチャー// Cryptography Research Inc. ホワイトペーパー、1999年。
[4] Intelの新しい乱数ジェネレーターの仕組み
[5]モナコフ、A。A.無線工学システムの数学的モデリングの基礎：教科書。 手当/ A. A.モナコフ; GUAP。 SPb。、2005.15秒
[6] ISO / IEC 9899：2011年4月12日の346fの最後の公開委員会ドラフト。
[7] Visual BasicがRND関数の擬似乱数を生成する方法。 Microsoftサポート。 マイクロソフト
[8] GNU Scientific Library：その他の乱数ジェネレーター
[9]ドナルドクナット。 ボリューム2.取得したメソッド//プログラミングの技術。 政令 Op。 -S. 21-37。
[10] Barklan E.、Biham E.、Keller N. GSM暗号化通信の暗号文のみの暗号解読。 -Journal of cryptology No. 21-3、2008。
[11] Larin、A. L.デジタルエレクトロニクスの基礎：トレーニングマニュアル/ A.L. ラリン; M。：MIPT、2008 .-- 314 p。 -ISBN 978-5-7417-0228-4。
[12] 効率的なシフトレジスタ、LFSRカウンター、および長い擬似ランダムシーケンスジェネレーター
[13] Vargauzin、V。デジタルテレビ規格ATSCの原則/ V. Vargauzin-Tele-Sputnik Magazine No. 9（47）、1999年。