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

---

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

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

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

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

---