Marsagliasova věta - Marsaglias theorem - Wikipedia

v výpočetní teorie čísel, Marsagliova věta spojuje modulární aritmetika a analytická geometrie popsat nedostatky pomocí pseudonáhodná čísla vyplývající z a lineární shodný generátor. Jako přímý důsledek se nyní obecně předpokládá, že lineární kongruentní generátory jsou slabé pro účely generování náhodných čísel. Zejména se nedoporučuje používat je pro simulace s Metoda Monte Carlo nebo v kryptografických nastaveních, jako je vydávání a certifikát veřejného klíče, pokud nejsou splněny konkrétní číselné požadavky. Špatně zvolené hodnoty pro modul a multiplikátor v a Generátor náhodných čísel Lehmer povede ke krátké době pro posloupnost náhodných čísel. Výsledek Marsaglie lze dále rozšířit na smíšený lineární kongruentní generátor. ^[1]

Hlavní prohlášení

Zvažte a Generátor náhodných čísel Lehmer s

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

pro libovolný modul ${ displaystyle m}$ a multiplikátor ${ displaystyle k}$ kde každý ${ displaystyle 0$a definujte sekvenci

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

Definujte body

${ 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}$

na jednotku ${ displaystyle n}$-krychle vytvořená z po sobě jdoucích podmínek posloupnosti ${ displaystyle u}$. S takovým multiplikativním generátorem čísel vše ${ displaystyle n}$- n-tic výsledných náhodných čísel leží maximálně ${ displaystyle (n! m) ^ {1 / n}}$ hyperplanes. Navíc pro výběr konstant ${ displaystyle c_ {1}, c_ {2}, ldots, c_ {n}}$ které uspokojují shodu

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

je jich nanejvýš ${ displaystyle | c_ {1} | + | c_ {2} | + cdots + | c_ {n} |}$ paralelní hyperplány, které obsahují všechny ${ displaystyle n}$-tuple produkované generátorem. Důkazy pro tato tvrzení lze nalézt v původním dokumentu Marsaglia. ^[2]

Reference