線性同餘方法

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

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

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

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

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

隨機性

因為通過線性同餘方法構建的偽隨機數生成器的內部狀態可以輕易地由其輸出演算得知,所以此種偽隨機數生成器屬於統計學偽隨機數生成器。

設計密碼學的應用必須至少使用密碼學安全偽隨機數生成器,故需要避免由線性同餘方法獲得的隨機數在密碼學中的應用。

參見

參考文獻

外部連結