線形合同法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
線形合同法（せんけいごうどうほう;Linear congruential generators,LCGs）とは、擬似乱数列を生成するアルゴリズムの一つ。
漸化式
によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B>0である。C言語等のプログラミング言語で擬似乱数生成のアルゴリズムとして採用されているが、暗号論的には安全な擬似乱数とは言えず、暗号技術には利用されるべきではないアルゴリズムである。
目次 |
生成
上の式で、
が、乱数の種であり、これに数を代入すると、
が得られる。さらに
を生成する場合には、を使う。以後、同様に行うのである。
例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種=8とすると、（上の式においてはXn+1を左辺に置いたが、今回は便宜上、右辺に置く）
次に乱数を生成する際は前回生成された乱数（今回は3）を使って、
以下、同じように、
となる。
周期性
生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。
- BとMが互いに素である。
- A-1が、Mの持つ全ての素因数で割りきれる。
- Mが4の倍数である場合は、A-1も4の倍数である。
- MはXnよりも大きい。
A=13、B=5、M=24の組み合わせなどがそれに当たる。
長所
- ほとんど記憶領域を必要としない。実用的な擬似乱数アルゴリズムでは最少である。
- 低機能なプロセッサ上でも極めて高速である。素朴な実装では乗算と除算が必要だが、有限代数を使って回避できる。
- 単純な演算しか使わないため専用回路化が容易である。
- 問題点は多いが、どのような問題があるか、どうやって回避すればいいかが十分に研究されている。
欠点
線形合同法で生成された乱数列から、次に出現する数を予測できる為、線形合同法は、擬似乱数のアルゴリズムとしてはあまり良いものではなく、暗号技術に使われるべきではない。また、下位ビットのランダム性は低く、下位nビットに注意すれば周期性はせいぜい2kである。よって最下位ビットは、同じものが出続けるか、0と1が交互にでるかのどちらかである。これは、最下位ビットが結果的に、奇数か偶数かを示しているため、偶数ばかりが出る、奇数ばかりが出る、偶数と奇数が交互に出る、という意味である。しかし、Cのrand関数を始めとして様々なプログラミング言語に付属の擬似乱数生成器では線形合同法がよく用いられており、この欠点を知らぬまま使われていることも多い。
モンテカルロ法に使うときは、下位ビットの非ランダム性はほとんど問題にならない。しかし、大量の擬似乱数を使う科学技術シミュレーションでは、周期の短さ（32ビットで最大約4億のオーダー）や、多次元の不均等分布（前後の数値の独立性が低いことに由来する）が問題になる。
参考文献
- 結城浩著『暗号技術入門 - 秘密の国のアリス』、ソフトバンク、ISBN 4-7973-2297-7、pp.305-307.
Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !