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

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

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

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

для любого модуля и множитель где каждый , и определим последовательность

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

на единицу -куб, образованный из следующих друг за другом членов последовательности . С таким генератором мультипликативных чисел все -наборы результирующих случайных чисел лежат не более чем в гиперплоскости. Дополнительно для выбора констант которые удовлетворяют сравнению

есть самое большее параллельные гиперплоскости, содержащие все -вырабатываемые генератором пары. Доказательства этих утверждений можно найти в оригинальной статье Марсальи. [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.