Теория Марсальи

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

Например, с RANDU у нас есть $m=2^{32}$, а в трех измерениях это показывает, что все точки попадают не более чем в $floor((2^{31}\times 3!)^{1/3})=2344$ самолеты. Фактический алгоритм RANDU, который использует $k=65539$, гораздо хуже. Все точки фактически попадают в 15 плоскостей.

Трехмерный график из 100 000 значений, созданный с помощью RANDU. Каждая точка представляет собой 3 последовательных псевдослучайных значения. Хорошо видно, что точки лежат в 15 двумерных плоскостях .

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

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

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

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

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

Определите точки

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

на единицу $n$-куб, образованный из последовательных членов последовательности $u$. С таким мультипликативным генератором чисел все $n$-кортежи результирующих случайных чисел лежат не более $(n!m)^{1/n}$ гиперплоскости. Кроме того, для выбора констант $c_{1},c_{2},\ldots ,c_{n}$ которые удовлетворяют сравнению

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

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