線性同餘方法

線性同餘方法(LCG)是個產生偽隨機數的方法。

它是根據以下的遞迴關係式

其中是產生器設定的常數。

LCG的週期最大為,但大部分情況都會少於M。要令LCG達到最大週期,應符合以下條件:

  1. 互質
  2. 的所有質因數都能整除
  3. 是4的倍數也是;
  4. 都比小;
  5. 是正整數。

随机性

因为通过线性同余方法构建的伪随机数生成器的内部状态可以轻易地由其输出演算得知,所以此种伪随机数生成器属于统计学伪随机数生成器。

设计密码学的应用必须至少使用密码学安全伪随机数生成器,故需要避免由线性同余方法获得的随机数在密码学中的应用。

參見

參考文獻

外部連結