质量PRNG只有32位状态
我试图实现rand_r接口的可容忍质量版本，它具有不幸的接口要求，它的整个状态存储在一个unsigned类型的单个对象中，这对我来说意味着正好是32位。 另外，我需要它的输出范围是[0,2³¹-1] 。 标准解决方案是使用LCG并丢弃低位（具有最短的周期），但是这对于接下来的几位仍然留下很差的周期。
我最初的想法是使用LCG的两到三次迭代来生成输出的高/低或高/中/低位。 但是，这种方法并不能保留非偏向分布; 而不是每个具有相同频率的输出值，许多发生多次，并且根本不会发生。
由于状态只有32位，因此PRNG的周期以2 3 2为界，而为了使其无偏差，PRNG必须在全周期内输出两次，如果周期为2 3 1，则必须正好输出一次。 较短的时间段不能没有偏见。
是否有任何符合这些标准的已知PRNG算法？
一种好的（但可能不是最快的）可能性，提供非常高的质量，将是在CTR模式下使用32位块密码。 基本上，你的RNG状态只不过是一个32位的计数器，对于每个RNG调用都会增加一个，并且输出将是使用具有任意选择的固定密钥的分组密码对该计数器值进行加密。 对于额外的随机性，你甚至可以提供一个（非标准）函数来让用户设置一个自定义键。
常用的32位块密码并不多，因为这种短块的大小会给密码的使用带来问题。 （基本上，生日悖论可以让你在只有大约216 = 65536个输出后以不可忽略的概率区分这样一个密码的输出和一个随机函数，并且在232个输出之后，非随机性显然变得确定）。然而，一些密码使用可调节的块大小，比如XXTEA或HPC，可以让你下降到32位，并且应该适合你的目的。
（ 编辑：我的坏，XXTEA只能下降到64位，但正如CodesInChaos在评论中所建议的，Skip32可能是另一种选择，或者你可以建立你自己的32位Feistel密码。）
CTR模式构造保证RNG将具有232个输出的完整周期，而（非破坏的）分组密码的标准安全要求基本上是将它们的输出与该组的随机置换区分开来在计算上是不可行的32位整数。 （当然，如上所述，这样的置换仍然可以轻易地从32位值的随机函数中区分开来。）
使用CTR模式还提供了一些您可能会觉得方便的额外功能（即使它们不属于您正在开发的官方API的一部分），例如只需添加或快速查找RNG输出流中的任意点即可从状态中减去。
另一方面，您可能不想遵循通过将内部状态设置为种子值来播种RNG的常见做法，因为这会导致从附近种子生成的输出流高度相似（基本上就是相同的流被种子的差异所改变）。 避免这个问题的一种方法是在种子过程中增加一个额外的加密步骤，即用密码加密种子，并设置内部计数器值等于结果。
详细阐述我的评论...
在计数器模式下的分组密码以近似以下形式给出生成器（除了使用更大的数据类型）：
uint32_t state = 0;
uint32_t rand()
{
state = next(state);
return temper(state);
}
由于没有指定加密安全性（在32位中它会或多或少徒劳无益），所以更简单的特殊调试函数应该能够做到这一点。
一种方法是next()函数很简单（例如， return state + 1; ）和temper()通过复杂（如块密码）进行补偿。
一个更平衡的方法是在next()实现LCG，因为我们知道它也访问所有可能的状态，但是以一个随机（ish）的顺序，并且找到一个实现temper() ，问题与LCG。
Mersenne Twister在其输出中包含了这样一种调节功能。 这可能是合适的。 此外，这个问题要求满足要求的操作。
我有一个最喜欢的，它是对这个单词进行位反转，然后乘以一些常数（奇数）。 如果位反转不是您架构上的本机操作，那可能会过于复杂。
32位最大周期Galois LFSR可能适合您。 尝试：
r = (r >> 1) ^ (-(r & 1) & 0x80200003);
LFSR的一个问题是你不能产生0值。所以这个值的范围是1到2 ^ 32-1。 你可能想调整输出或者坚持一个好的LCG。
链接地址: http://www.djcxy.com/p/6361.html