algorithm - 不可预测的计数

Question

假设我有一个 32 位整数。最初，我用随机/秘密的东西为这个黑盒子播种。

每次我打电话，前进，我都会得到序列中的下一个数字，但序列中的下一个数字不一定是下一个最大的数字，因为++它是不可预测的。我已经使用置换表完成了这项工作，但这需要大量空间，我想知道是否有人知道一个特定的构造，它可以基于某个种子值以某种确定性顺序为我提供整个范围，然后只产生每个值每个周期恰好一次。

有人知道这样的计划吗？

Answer 1

Thomas Pornin 在crypto.stackexchange.com上的一个问题有一个有趣的答案，该问题涉及如何设计一个安全的交替步进生成器(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，并使用三倍的大型线性反馈移位寄存器 (LFSR)。

您还需要使用最大长度反馈多项式来提高强度。Wikipedia 文章引用了一个PDF，其中列出了最长为 168 位的最大长度反馈多项式。