可逆伪随机序列发生器

Question

我想要某种方法来创建一个相当长的随机数序列，我可以前后翻转。就像一台带有“下一个”和“上一个”按钮的机器，它会给你随机数。 像 10 位分辨率（即 0 到 1023 范围内的正整数）就足够了，并且序列超过 100k 个数字。它适用于简单的游戏类型应用程序，

我不需要加密强度随机性

或任何东西，但我希望它感觉相当随机。不过，我的可用内存量有限，所以我不能只生成一大块随机数据并浏览它。我需要在“交互时间”中获取数字 - 我可以轻松地花几毫秒思考下一个数字，但不能舒适地超过这个数字。最终它将在某种微控制器上运行，可能只是 Arduino。 我可以用一个简单的线性同余发生器（LCG）来做到这一点。向前移动很简单，要向后移动，我必须缓存最新的数字并每隔一段时间存储一些点，以便我可以从那里重新创建序列。 但是也许有一些伪随机生成器可以让你向后和向前移动？应该可以连接两个线性反馈移位寄存器（LFSR）以向不同方向滚动，不是吗？

或者也许我可以使用某种哈希函数来混淆索引号？我要先尝试一下。

还有其他想法吗？

我在 tigsource 论坛上问了一个

非常类似的问题

Answer 1

哈希 至少在游戏中，哈希函数可能可以满足您的需求。你可以这样做

class ReversibleRNG {
    int x;
public:
    ReversibleRNG(int seed) : x(seed) {}
    int next(){return yourFavoriteHash(++x);}
    int prev(){return yourFavoriteHash(--x);}
};

可逆线性同余发生器（lcg）

正如很多人指出的那样，LCG 确实是可逆的。在 lcg 中，下一个状态的计算如下：

x = (a * prevx + c) mod m

我们可以重新订购：

x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)

由于 a 和 m 在 lcg 中被选为互质，因此我们可以使用扩展欧几里得算法找到逆元。

ainverse = extEuclid(a, m).x;
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)

这意味着

prevx = ainverse * (x - c) mod m

如果仔细选择 m 和 a，算法的周期可以为 2^64

实施

我做了这个算法的

仅标头实现

以防有人感兴趣。

使用非常简单的对称加密算法是最简单的方法之一。每个随机数都是通过使用某个固定密钥加密前一个随机数而形成的，然后只需解密即可返回。

Answer 2

http://en.wikipedia.org/wiki/RC4

查看 RC4 - 代码。您可以使用更小的密钥表来使其完全适合 arduino。

使用任何密码和任何密钥加密序列

1, 2, 3, ...

Answer 3

AES

几乎可用于所有最新的系统，并且速度

闪电

快。 只需颠倒整数递增序列中的位顺序即可。 例如（8 位分辨率）：

Answer 4

0

0

1
• 128<=>
2
• 64<=>
3
• 192<=>
4
• 32<=>
等等
• <=>
在序列中向前和向后移动非常容易，并且比调用加密或哈希函数快得多。它还具有生成最长可能序列的好处。
这绝对不是加密安全的。这是生成值的散点图（同样具有 8 位分辨率）：

您可以很容易地看到模式，尽管它对您来说可能已经足够“随机”了。

如果线性同余发生器足够好，请使用它。它们很容易逆转。重点是反向发电机也是LCG。 LCG 还可以非常快速地在任何方向（向前和向后）跳跃。

Answer 5

计算机编程艺术 - 第 2 卷

特别是 TAOCP 第 3.2.1 页第 10 页的方程 6-8 以及练习 5 给出了所需的结果。如果您无法解决练习，您可以轻松找到解决方案，例如这里

虽然我同意 @BlueRaja 的观点，即您应该在“计数器模式”下使用 AES，并为您的序列随机或基于时间启动，但 AES 在您的嵌入式情况下可能不可用或不可行。

Answer 6

这篇有趣的论文

，讨论了如何构建可逆的 PRNG；它只有 10 页，并且有大量的代码示例。如果 AES 不适合你，请尝试一下。

您也可以使用 LCG 进行倒退，它只是另一个 LCG，使用乘数的倒数以模为模，并加上适当的增量。

Answer 7

除非您的游戏纯粹是为了好玩，不涉及任何类型的赌注，否则我会选择加密安全的方法，例如其他人建议的 AES 方法。 LCG 和其他线性随机数生成器无法抵御智能对手。