伪随机数生成器

周期性

PRNG通过设定随机种子可以从任意初始值开始生成。同样的初始值总是生成同样的序列。PRNG的周期定义为：所有初始值的最大长度的无重复前缀序列。周期受状态数的限制，通常用比特位数表示。然而，每增加一个比特位，周期长度就可能增加一倍，所以构建周期足够长的PRNG对于许多实际应用程序来说是很容易的。
如果PRNG的内部状态包含n位，那么它的周期不会超过2ⁿ，甚至可能非常短。对于大多数PRNG，周期长度的计算并不需要遍历整个周期。线性反馈移位寄存器（LFSR）的周期通常正好是2ⁿ−1。线性同余方法的周期可以通过因式分解进行计算。 尽管PRNG在达到周期之后会出现重复的结果，但重复序列的出现并不意味着到达了一个周期，因为它的内部状态可能比输出要大很多。对于输出为1位的PRNGs，这一点尤其明显。

基于线性递归的生成器

在20世纪下半叶，PRNG的标准算法由线性同余方法（LCG）构成。众所周知，LCG的质量是不够的，但也没有更好的方法。Press et al. (2007) 描述了这种情况：“如果所有因为LCG而受质疑的科学论文从书架上消失，那么每一个架子上都会有一个拳头大小的空隙”。
伪随机生成器构造的重大进展，是在二元域中引入的线性递归技术，这种生成器和线性反馈移位寄存器有关。
1997年发明的Mersenne Twister，避免了很多问题。Mersenne Twister方法的周期长达2¹⁹⁹³⁷−1，被证明在623个维度上是均匀分布的（对于32位数值），同时它的运行速度比其他统计方法快。
在2003年，George Marsaglia提出了xorshift生成器家族，它也基于线性递归。这种生成器的运行速度非常快，再结合非线性操作，通过了强有力的统计测试。
在2006年，WELL家族的生成器被提出。 WELl生成器在某些方面提高了Mersenne Twister的质量，Mersenne Twister具有非常大的状态空间，而且从含有大量0值的状态空间中的恢复非常缓慢。
aphically secure pseudorandom number generators==