-1

32 ビット整数があるとします。最初に、このブラック ボックスにランダム/シークレットをシードします。

事前に呼び出すたびに、シーケンスの次の番号を取得しますが、シーケンスの次の番号は、++予測できないものであるため、必ずしも次の最大の番号であるとは限りません。私は順列テーブルを使用してこれを行いましたが、それには多くのスペースが必要であり、シード値に基づいて決定論的な順序で範囲全体を提供し、各値のみを生成する特定の構造を誰かが知っているかどうか疑問に思っていましたサイクルごとに正確に 1 回。

そのようなスキームを知っている人はいますか？

4

1 に答える 1

0

crypto.stackexchange.com の Thomas Porninによる質問に対する興味深い回答があり、安全な交互ステップ ジェネレータ(ASG)の設計方法について説明しています。

これは私の問題に対する最速の解決策ではありませんが、うまくいくと思います。

私は自分の理論をテストするためにこのコードを書きました

struct Lfsr
{
    public readonly int State;

    public Lfsr(int seed)
    {
        this.State = seed;
    }

    public Lfsr Advance()
    {
        var bit = ((State >> 30) ^ (State >> 27)) & 1; //  ^ (State >> 1) ^ (State >> 0)
        return new Lfsr(((State << 1) | bit) & 0x7fffffff);
    }
}

static void Main(string[] args)
{
    var n = 0;

    var lfsr = new Lfsr(1);

    do
    {
        lfsr = lfsr.Advance();

        ++n;
    }
    while (lfsr.State != 1);

    Console.WriteLine(n);
}

私のマシンでは、2147483647 のカウント数の周期で循環するのに約 7 秒かかりました。安全にするには、これらを ASG に結合し、3 倍の大きな線形フィードバック シフト レジスタ (LFSR) を使用する必要があります。

また、強度のために最大長のフィードバック多項式を使用する必要があります。ウィキペディアの記事では、長さが 168 ビットまでの最大長フィードバック多項式をリストしたPDFを参照しています。

于 2013-05-15T17:19:40.567 に答える