25

我想要某种方法来创建一个相当长的随机数序列，我可以前后翻阅。就像一台带有“下一个”和“上一个”按钮的机器，它会给你随机数。

像 10 位分辨率（即 0 到 1023 范围内的正整数）之类的东西就足够了，并且有 >100k 的数字序列。这是一个简单的游戏类型的应用程序，我不需要加密强度随机性或任何东西，但我希望它感觉相当随机。不过，我的可用内存量有限，所以我不能只生成一大块随机数据并遍历它。我需要在“交互时间”中获取数字——我可以轻松地花几毫秒思考下一个数字，但不会比这更舒服。最终它将在某种微控制器上运行，可能只是一个 Arduino。

我可以用一个简单的线性同余生成器（LCG）来做到这一点。向前走很简单，向后走我必须缓存最近的数字并每隔一段时间存储一些点，这样我就可以从那里重新创建序列。

但也许有一些伪随机生成器可以让你前进和前进？应该可以连接两个线性反馈移位寄存器 (LFSR) 以向不同方向滚动，不是吗？

或者也许我可以使用某种散列函数来混淆索引号？我要先试试。

还有其他想法吗？

4

7 回答 7

26

我在 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)

由于在 lcg 中 a 和 m 被选择为互质，因此我们可以使用扩展的 euclid 算法找到逆。

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

执行

如果有人感兴趣，我对这个算法做了一个只有标题的实现。

于 2013-05-19T01:11:17.640 回答
11

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

您可以查看http://en.wikipedia.org/wiki/RC4上的 RC4 代码。您可以使用更小的密钥计划来使其完全适合 arduino。

于 2010-05-28T13:58:50.980 回答
6

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

AES几乎可以在所有最新的系统上使用，而且速度快如闪电。

于 2010-05-28T14:00:47.947 回答
2

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

详细信息可以在计算机编程的艺术 - 第 2 卷中找到

特别是第 10 页第 10 页的第 3.2.1 节，TAOCP 的公式 6-8 和练习 5 给出了预期的结果。如果你不能解决这个练习，你可以很容易地找到它的解决方案，例如这里

于 2017-05-02T13:02:40.817 回答
2

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

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

在序列中向前和向后移动非常容易，并且比调用加密或散列函数要快得多。它还具有生成最长可能序列的好处。

它绝对不是加密安全的。这是生成值的散点图（同样是 8 位分辨率）：

的散点图

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

于 2017-01-18T19:47:27.917 回答
0

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

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

于 2010-05-28T14:14:20.260 回答
0

您也可以使用 LCG 倒退，它只是另一个 LCG，它使用乘数模模的倒数以及适当的增量。

对于您的小数字，您可以使用蛮力来搜索逆，通常可以使用扩展的 GCD 算法来计算。

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

于 2010-05-29T12:45:13.993 回答