#random #computer-science
#Случайный #информатика
Вопрос:
Я пытаюсь выяснить, каким был бы период конкретного генератора псевдослучайных чисел CMWC.
На странице википедии есть несколько примеров периода с различными параметрами как для стандартного MWC, так и для CMWC, но на самом деле не объясняется, как это вычисляется.
Есть ли простой способ вычислить это для заданного множителя, r числа начальных значений и базы b?
Допустим, у меня есть следующие параметры (для CMWC):
b=2^32-1
a=4294966362
r=32
Я проверил, что p=a*b^r 1 является простым.
редактировать: упс, скопировано неправильное значение a. Исправлено, так что теперь p должно быть простым.
Ответ №1:
b является примитивным корнем, когда его порядок равен p-1, поэтому b ^ k может принимать любое значение от 1 до p-1, в зависимости от значения k .
Порядок элемента равен минимальному s при b^ s =1 (mod p). b является примитивным корнем тогда и только тогда, когда b ^(phi(p) /k) != 1 (!= означает разное) для каждого k делителя phi(p), а phi(p) = (p-1) является общей функцией Эйлера (http://en.wikipedia.org/wiki/Euler’s_totient_function ).
В вашем примере:
— phi (p) = a * b ^ r = p — 1.
— Делителями a являются {1, 2, 3, 31, 23091217, 4294966362}.
— Делители b равны {1, 3, 5, 17, 257, 65537, 4294967295}.
Итак, (p-1) = 2*(3^33)*(5^32)*(17^32)*31*(257^32)*(65537^32)*23091217.
p-1 имеет 322,570,512 делителей (http://en.wikipedia.org/wiki/Divisor_function )
При модульном возведении в степень можно видеть, что b ^ ((p-1) / 3) = 1 (mod p), поэтому порядок b отличается от p-1.
Лучше выбирать числа a и b с несколькими делителями, тогда у p-1 также будет несколько делителей, и будет легко вычислить (phi (p) / k) для каждого делителя k. Порядок b будет min{phi (p) / k} = min{(p-1) / k}.
В статье Марсальи «О случайности числа Пи и других десятичных разложений» (http://interstat.statjournals.net/YEAR/2005/articles/0510005.pdf ), есть некоторые значения a, b и r. Периоды, которые не заполнены, также полезны (см. Статью).
База b = 2 ^ 32 не имеет полного периода, но она возвращает целые числа от 0 до 2 ^ 32-1. База b = 2 ^ 32-1 не может возвращать несмещенные 32-разрядные целые числа (она никогда не вернет число 2 ^ 31-1 = 4294967295).
Комментарии:
1. 1 сводит всю математику в одно место. Мне пришлось часами искать все это вместе.
Ответ №2:
Я неправильно понял, что требуется для получения полного периода:
b также должен быть примитивный корень из p , чего, я думаю, здесь не происходит (честно говоря, у меня нет математического образования, чтобы даже начать понимать, что такое примитивный корень). Если есть полный период, период будет a*b^r . Насколько я могу судить, невозможно (или, по крайней мере, очень сложно) определить, каким был бы период в противном случае (и, откровенно говоря, это бесполезно, потому что на практике требуется полный период).
Источник: Журнал современных прикладных статистических методов