可逆伪随机序列生成器

Question

可逆伪随机序列生成器

27

我想要一种方法来创建一个相当长的随机数序列，我可以向前和向后翻转。就像有"下一个"和"上一个"按钮的机器，会给你随机数。

类似于10位分辨率（即范围在0到1023之间的正整数）就足够了，并且需要一个超过100k个数字的序列。这是为了一个简单的游戏型应用程序，我不需要加密级别的随机性或其他什么，但我希望它感觉相当随机。然而，我的可用内存有限，所以我不能只是生成一大块随机数据并遍历它。我需要在"交互时间"中获取这些数字 - 我可以轻松地花费几毫秒的时间考虑下一个数字，但不舒服地超过那个时间。最终它将在某种微控制器上运行，可能只是Arduino。

我可以使用简单的线性同余生成器（LCG）来实现。向前很简单，要向后走，我需要缓存最近的数字并在一定间隔中存储一些点，以便从那里重新创建序列。

但也许有一些伪随机生成器可以让你向前和向后走？将两个线性反馈移位寄存器（LFSRs）连接起来以不同的方向滚动应该是可能的，对吗？

或者我可以通过使用某种哈希函数来混淆索引号码，这样就可以解决问题了吗？我打算先尝试这个方法。

还有其他的想法吗？

- PapaFreud

为什么不直接使用页面索引作为种子？ - Jp Silver

7个回答

11

使用一个非常简单的对称加密算法是实现此功能最简单的方法之一。每个随机数都是通过使用某个固定密钥对前一个随机数进行加密而形成的，要反向操作只需解密即可。

您可以查看RC4代码，网址为http://en.wikipedia.org/wiki/RC4。您可以使用更小的密钥计划将其适配到arduino上。

- Cullen Fluffy Jennings

6

使用任何密码和任何密钥对序列1, 2, 3, ...进行加密。

高级加密标准（AES）在几乎所有最新的系统中都可用，并且速度非常快。

- BlueRaja - Danny Pflughoeft

3

将一个递增的整数序列中的比特位顺序翻转即可。例如（以8位分辨率为例）：

0 <=> 0
1 <=> 128
2 <=> 64
3 <=> 192
4 <=> 32
等等

在序列中前后移动非常容易，而且比调用加密或哈希函数快得多。它还有一个好处，就是生成最长的可能序列。

它绝对不是加密安全的。这是生成的值的散点图（再次以8位分辨率为例）：

您可以很容易地看到模式，尽管这可能对您来说是足够“随机”的。

- Matt Thomas

1

我没有数学证明，但是生成的序列看起来像是“次随机”的。https://en.wikipedia.org/wiki/Low-discrepancy_sequence 。在许多应用中仍然可以有用。 - alfC

1

@alfC 我的图片确实看起来像Hammersley集合，而Wolfram说你可以通过反转位的顺序生成该集合--我认为这就是你正确的证明。感谢提供链接！ - Matt Thomas

@alfC 我不理解 hash(i + seed) 如何产生低差异序列（使用适当的哈希函数，例如 SHA256）？ - Matt Thomas

我也不是。这是直觉，如果随机数可以那样生成，它就不需要任何内存，那将是奇怪的。如果它不是次随机的，那么它就是一个糟糕的哈希。我的结论是，当应用于编程序列时，哈希会产生次随机序列。 - alfC

@alfC 允许我更加肯定地重申：在某些情况下，计数器的加密哈希也可以作为良好的 CSPRNG（密码学安全伪随机数生成器）基于密码学原语的设计。请注意，使用加密函数而不是哈希函数似乎更为常见，但原理相同。 - Matt Thomas

显示剩余8条评论

2

如果线性同余生成器足够好，就使用它。它们很容易可逆。关键是反向生成器也是线性同余生成器。LCG可以非常快速地向任何方向（前进和后退）跳过。

详细信息可以在计算机程序设计艺术-第2卷的第3.2.1节第10页6-8式中找到，还有练习5给出了所需的结果。如果您无法解决练习，可以轻松地找到其解决方案，例如这里。

- Udo Klein

0

虽然我同意@BlueRaja的观点，你应该只使用“计数器模式”下的AES，使用随机或基于时间的起始序列，但在嵌入式环境中，AES可能不可用或不可行。

我找到了这篇有趣的论文，讨论了如何构建可逆PRNG；它只有10页，并且有大量的代码示例。如果AES对你不起作用，请尝试一下。

- Randolpho

0

你也可以使用LCG进行反向操作，这只是另一个LCG，使用乘数模模数的倒数以及适当的增量。

对于你的小数字，你可以使用暴力搜索来查找倒数，在一般情况下，它可以通过扩展的GCD算法计算得出。

除非你的游戏纯粹是为了娱乐，没有任何涉及利益的风险，否则我建议选择一些具有密码学安全性的方法，例如其他人建议的AES方法。 LCG和其他线性随机数生成器无法抵御聪明的对手。

- starblue

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bobbaluba · Accepted Answer

我曾在tigsource论坛上问过一个非常相似的问题。

哈希

至少在游戏中，哈希函数可能可以实现你想要的功能。你可以这样做：

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是互质的，因此我们可以使用扩展欧几里得算法来找到其逆元。

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的周期。

实现

我进行了这个算法的仅头文件实现，以防有人感兴趣。