マルサリアの定理

計算数論において、マルサリアの定理はモジュラー算術と解析幾何学を結び付けて、線形合同型生成器から生じる疑似乱数の欠陥を記述する。その直接的な結果として、線形合同型生成器は乱数生成の目的には弱いと現在広く考えられている。特に、特定の数値要件が満たされない限り、モンテカルロ法によるシミュレーションや公開鍵証明書の発行などの暗号化設定にそれらを使用することはお勧めできません。レーマー乱数生成器の係数と乗数の値が適切に選択されていないと、乱数列の周期が短くなります。マルサリアの結果は、混合線形合同型生成器にさらに拡張される可能性があります。 ^[1]

たとえば、RANDUではとなり、3 次元ではすべての点が最大で個の平面に収まることがわかります。 を使用する実際の RANDU アルゴリズムは、これよりはるかに悪いです。すべての点は実際には 15 個の平面に収まります。 ${\displaystyle m=2^{32}}$${\displaystyle floor((2^{31}\times 3!)^{1/3})=2344}$${\displaystyle k=65539}$

レーマー乱数生成器を 考えてみましょう。

${\displaystyle r_{i+1}\equiv kr_{i}\mod m}$

任意の係数と乗数に対して、各、およびシーケンスを定義する。 ${\displaystyle m}$${\displaystyle k}$${\displaystyle 0<r_{i}$

${\displaystyle u_{1}={\frac {r_{1}}{m}},u_{2}={\frac {r_{2}}{m}},u_{3}={\frac {r_{3}}{m}},\ldots }$

ポイントを定義する

${\displaystyle \pi _{1}=(u_{1},\ldots ,u_{n}),\pi _{2}=(u_{2},\ldots ,u_{n+1}),\pi _{3}=(u_{3},\ldots ,u_{n+2}),\ldots }$

の連続項から形成される単位立方体上の。このような乗法型数生成器では、結果として生じる乱数の組はすべて、最大で 個の超平面上に存在する。さらに、合同性を満たす 定数を選択することで、${\displaystyle n}$${\displaystyle u}$${\displaystyle n}$${\displaystyle (n!m)^{1/n}}$${\displaystyle c_{1},c_{2},\ldots ,c_{n}}$

${\displaystyle c_{1}+c_{2}k+c_{3}k^{2}+\cdots +c_{n}k^{n-1}\equiv 0\mod m,}$

生成器によって生成されたすべての -組を含む平行超平面は最大で存在する。これらの主張の証明は、Marsagliaの元の論文に記載されている。^[2]${\displaystyle |c_{1}|+|c_{2}|+\cdots +|c_{n}|}$${\displaystyle n}$