7

状態を隠すことなく、前の出力から純粋関数のように計算できる、優れた疑似乱数ジェネレーターが必要です。「良い」とは、次のことを意味します。

  1. 2^n任意のパラメーター（またはそれらの大きなサブセット）を使用して反復でジェネレーターを実行する0と、との間のすべてまたはほぼすべての値をカバーするようにジェネレーターをパラメーター化できる必要があります。2^n - 1ここnで、は出力値のビット数です。

  2. ビットの結合されたジェネレーター出力は、そのパラメーターのすべての可能な組み合わせに対して反復で実行する場合、n + pすべてまたはほぼすべての値をカバーする必要があり0ます。ここで、はパラメーターのビット数です。2^(n + p) - 12^np

たとえば、LCGは純粋関数のように計算でき、最初の条件を満たすことはできますが、2番目の条件を満たすことはできません。たとえば、32ビットLCGがm = 2^32あり、それは一定であるためp = 64（2つの32ビットパラメーターaとc）n + p = 96、、 2番目の条件を満たすには、出力から3intずつデータをピークする必要があります。残念ながら、出力の奇数と偶数のintのシーケンスが厳密に交互になっているため、条件を満たせません。これを克服するには、隠された状態を導入する必要がありますが、それは機能を純粋ではなく、最初の条件（長い隠された期間）を壊します。

編集：厳密に言えば、ビットによってパラメーター化され、pビットの完全な状態を備えた関数ファミリーが必要です。各関数は、 -bit intを連続的にインクリメントするだけでなく、一意の「ランダムな」方法nでビットのすべての可能なバイナリ文字列を生成します。そのユニークな方法を選択するために必要なパラメータ化。p + n(p + n)

欲しすぎですか？

4

2 に答える 2

2

固定キーを使用して、任意のブロック暗号を使用できます。次の番号を生成するには、現在の番号を復号化し、インクリメントして、再度暗号化します。ブロック暗号は 1:1 であるため、反復する前に出力ドメイン内のすべての数値を反復する必要があります。

于 2010-05-20T20:55:47.390 に答える
1

LFSRを試す
必要なのは原始多項式のリストだけです。
このように有限体を生成する周期は、大きさ 2^n-1 の体を生成します。しかし、この手順を一般化して、k^n-1 の周期で何かを生成することができます。

私はこれが実装されているのを見たことがありませんが、実装する必要があるのは、gcd(s,2^n-1) == 1 である小さい数 s>n だけ数値をシフトすることだけです。gcd は最大公約数を表します。

于 2010-05-20T19:53:53.223 に答える