algorithm - 是否存在没有隐藏状态的 "good"PRNG 生成值？

Question

我需要一些好的伪随机数生成器，它可以像纯函数一样从以前的输出中计算出来，没有任何状态隐藏。在“好”下，我的意思是:

1. 我必须能够以为 2^n 运行它的方式参数化生成器使用任何参数(或其中的一些大子集)的迭代应该覆盖 0 之间的所有或几乎所有值。和 2^n - 1 , 其中n是输出值的位数。

2. n + p 的组合生成器输出位必须涵盖 0 之间的所有或几乎所有值和 2^(n + p) - 1如果我为 2^n 运行它对其参数的每个可能组合进行迭代，其中 p是参数的位数。

例如，LCG可以像纯函数一样计算，它可以满足第一个条件，但不能满足第二个条件。比如说，我们有 32 位 LCG，m = 2^32它是不变的，我们的p = 64 (两个 32 位参数 a 和 c )，n + p = 96 ，因此我们必须从输出中查看三个整数的数据以满足第二个条件。不幸的是，由于输出中奇数和偶数整数的严格交替序列，因此无法满足条件。为了克服这个问题，必须引入隐藏状态，但这使得功能不纯粹并且打破了第一个条件(长隐藏期)。

编辑:严格来说，我想要由 p 参数化的函数族位和 n 的完整状态位，每个生成 p + n 的所有可能的二进制字符串以独特的“随机”方式位，而不仅仅是连续递增 (p + n) -位整数。选择该独特方式所需的参数化。

我是不是想太多了？

Answer 1

您可以使用任何带有固定 key 的分组密码。要生成下一个数字，请解密当前数字，递增它，然后重新加密它。因为 block 密码是 1:1，所以它们必须在重复之前遍历输出域中的每个数字。