可逆的伪随机序列发生器
我想要一些方法来创build一个相当长的随机数字序列 ，我可以翻转来回 。 就像一台带有“下一个”和“上一个”button的机器，它会给你随机的数字。
像10位分辨率（即在从0到1023的范围内的正整数）就足够了，并且一个> 100k数字的序列就足够了。 这是一个简单的游戏types的应用程序， 我不需要encryption强度随机性或任何东西，但我希望它感觉相当随机。 虽然我有一个有限的内存 ，所以我不能只生成一大块随机数据，并通过它。 我需要在“互动时间”中得到这些数字 – 我可以轻松地花几个小时来思考下一个数字，但是不能轻松得多。 最终它会运行在某种微控制器上，可能只是一个Arduino。
我可以用一个简单的线性同余发生器（LCG）来完成。 向前走是简单的，为了倒退，我不得不caching最近的数字，并间隔存储一些点，所以我可以从那里重新创build序列。
但也许有一些伪随机发生器，让你去前锋和前锋？ 应该可以连接两个线性反馈移位寄存器（LFSR）以便在不同的方向上滚动，否？
或者，也许我可以通过使用某种哈希函数篡改索引号？ 我要先尝试一下。
任何其他的想法？
我在tigsource论坛上问了一个非常类似的问题 。
哈希
至less在游戏中，哈希函数可能可以做你想要的。 你可以这样做
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
我们可以重新sorting：
x ≡ a * prevx + c (mod m) x - c ≡ a * prevx (mod m)
由于a和m在lcg中被select为相对的，所以我们可以通过使用扩展的euclidalgorithm来find逆。
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
如果仔细selectm和a，algorithm可以有2 ^ 64的周期
履行
如果有人感兴趣，我只做了这个algorithm的头部实现 。
使用一个非常简单的对称encryptionalgorithm是最简单的方法之一。 每个随机数是由一个固定的密钥对前一个密钥进行encryption，然后向后解密。
你可以看看http://en.wikipedia.org/wiki/RC4上的RC4 – Code。 你可以使用一个更小的关键时间表，以适应所有的arduino。
用任何密码和任何密钥encryption序列1, 2, 3, ...
几乎每一个最近的系统都可以使用AES ，而且闪电般快。
只要在递增的整数序列中颠倒位的顺序即可。 例如（8位分辨率）：
- 0 <=> 0
- 1 <=> 128
- 2 <=> 64
- 3 <=> 192
- 4 <=> 32
- 等等
在序列中前后移动非常容易，而且比调用encryption或散列函数要快得多。 它也有产生最长可能序列的好处。
这绝对不是密码安全的。 这里是生成值的散点图（同样是8位分辨率）：
你可以很容易地看到模式，虽然它可能是“随机”足够你。
如果线性同余发生器足够好使用它。 他们很容易扭转。 关键是反向发电机也是一个LCG。 LCG也可以非常快地向任何方向（向前和向后）跳跃。
细节可以在“计算机编程艺术 – 第二卷”中find
特别是第3.2.1节和TAOCP第6-8节的练习5给出了预期的结果。 如果你不能解决这个问题，你可以很容易地find答案，例如这里
虽然我同意@BlueRaja，你应该在“计数器模式”中使用AES，并且随机或基于时间的序列启动，但AES可能无法在您的embedded式环境中使用或不可行。
我find了这个有趣的论文 ，讨论如何build立一个可逆的PRNG; 它只有10页，并有大量的代码示例。 试一试，如果AES不适用于你。
你也可以用LCG后退，它只是另一个LCG，使用乘法器模数的倒数和一个合适的增量。
对于你的小数字，你可以使用蛮力来search逆，一般来说，它可以用一个扩展的GCDalgorithm来计算。
除非你的游戏只是为了好玩，不涉及任何types的赌注，否则我会select密码保密的东西，比如其他人build议的AES方法。 LCG和其他线性随机数发生器不能承受智能对手。
