寻找可重放/有点无状态的 PRNG 算法

Question

我正在寻找一个"可重放"和"无状态"的伪随机数生成器。让我详细说明一下：我需要能够根据随机函数的参数重新获取伪随机数。例如（C 样式伪代码）：

int x1 = random(1);
int x2 = random(2);
// and so on with lots of random() calls in between
int new_x1 = random(1);
// now new_x1 is like a "replay" of x1, so x1 == new_x1

参数的类型无关紧要（我可以对任何需要的东西进行类型转换），返回值不必int;最终我需要8位值。

问题是：满足下一个伪随机值由参数控制而不是由每次调用时更新的内部状态控制的要求的好 PRNG 算法是什么？我不知道如何使用如下所示的糟糕解决方案：

int random(int input) {
    srand(input);
    return rand();
}

这必须在每次调用时初始化 PRNG，这似乎成本很高。（我用标准srand() / rand()来说明这一点，我知道有更好的算法，比如Mersenne Twister，但想法仍然是一样的。

Answer 1

在这里可能有效的一种方法是使用像AES或三重DES这样的分组密码。然后，您的伪随机生成器可能是

int pseudorandomValue(int input) {
    return encryptUsingAES(input);
}

这是无状态的、伪随机的（因为 AES 的输出在统计上应该与随机无法区分）和无状态。

希望这有帮助！

Answer 2

您可以使用基于 Xorshift[1,2] 的 PRNG。此 PRNG 使用上一个随机数生成下一个随机数。与 AES 相比，该实施非常有效。

对于 32 位实现：

uint32_t next_rand(uint32_t prev)
{
   prev ^= prev << 13;
   prev ^= prev >> 17;
   prev ^= prev << 5;
   return prev;
}

对于 64 位实现：

uint64_t next_rand(uint64_t prev)
{
   prev ^= prev << 21;
   prev ^= prev >> 35;
   prev ^= prev << 4;
   return prev;
}

随机数序列是"可重放的"，无状态的，并且仅取决于初始值，即种子。

引用：

维基

1. ：维基。

2. 一篇带有详细数学的论文：论文。