Теорема марсалья - Marsaglias theorem

В вычислительная теория чисел, Теорема Марсальи соединяет модульная арифметика и аналитическая геометрия описать недостатки псевдослучайные числа в результате линейный конгруэнтный генератор. Как прямое следствие, сейчас широко считается, что линейные конгруэнтные генераторы являются слабыми для целей генерации случайных чисел. В частности, нецелесообразно использовать их для моделирования с Метод Монте-Карло или в криптографических настройках, таких как выдача сертификат открытого ключа, если не выполняются конкретные количественные требования. Плохо выбранные значения модуля и множителя в Генератор случайных чисел Лемера приведет к короткому периоду для последовательности случайных чисел. Результат Марсальи может быть расширен до смешанного линейного конгруэнтного генератора. ^[1]

Основное заявление

Рассмотрим Генератор случайных чисел Лемера с

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

для любого модуля ${\displaystyle m}$ и множитель ${\displaystyle k}$ где каждый ${\displaystyle 0<r_{i}<m}$, и определим последовательность

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

есть самое большее ${\displaystyle |c_{1}|+|c_{2}|+\cdots +|c_{n}|}$ параллельные гиперплоскости, содержащие все ${\displaystyle n}$-вырабатываемые генератором пары. Доказательства этих утверждений можно найти в оригинальной статье Марсальи. ^[2]

Рекомендации

1. Гринбергер, Мартин (Октябрь 1961 г.). «Априорное определение последовательной корреляции случайных чисел, генерируемых компьютером» (PDF). Американское математическое общество. 15 (76): 383–389. Дои:10.2307/2003027.
2. Марсалья, Джордж (Сентябрь 1968 г.). «Случайные числа выпадают в основном в плоскости» (PDF). PNAS. 61 (1): 25–28. Bibcode:1968ПНАС ... 61 ... 25М. Дои:10.1073 / pnas.61.1.25. ЧВК  285899. PMID  16591687.