Псевдослучайные числа.

[Nogin Anton]

Добрый день!

Появилась необходимость написать генератор Парка-Миллера. На английской википедии нашёл формулу генератора:

$X_{k+1}=g\cdot X_k \mod n$

Не пойму с константой $g$, то есть как она определяется. Вроде это взаимно простое число с $n$. Скажите, я верно понял?

[alisa-lebovski]

По-моему, это называется конгруэнтный метод и число берут просто простое.

[Sonic86]

Я не знаю, что такое генератор Парка-Миллера, но ясно что $X_k = X_0g^k \bmod n$. Качество генератора прежде всего сводится к длине цикла, т.е. к показателю $g$ по модулю $n$. Если $n=p^a;2p^a$, то $\mathbb{Z}_n$ - циклическая и максимальный цикл дает образующая $g$. Если $n=p$, то образующую $g$ можно искать через критерий Лёмера (немного тут есть, но это не то. Критерий простой - просто вычисляем порядок элемента: $g$ - образующая группы $\mathbb{Z}_p^{\times}$ (ее порядок $p-1$) $\Leftrightarrow g^{p-1}\equiv 1 \pmod p \& (\forall q\in\mathbb{P})q\mid p-1\Rightarrow g^{\frac{p-1}{q}}\not\equiv 1\pmod p$). В случае составного $n$ порядок группы равен $\varphi (n)$, где $\varphi$ - функция Эйлера, но максимальный порядок элемента - это функция Кармайкла $\lambda (n)=\lcm\limits_k(p_k^{a_k-1}(p_k-1))<\varphi(n)$ при $n\neq p^a;2p^a$, поэтому длина цикла будет меньше, но в принципе тоже можно юзать.
Читайте также рекомендованный Вам 2-й том Кнута Искусства программирования по ГСЧ. И линейный конгруэнтный генератор вроде круче.
Руст где-то тут утверждал, что если $n$ - простое и в качестве $g$ испытывать последовательные простые числа, то за $O(\ln ^2n)$ испытаний найдем образующую. Но это какой-то очень сложный недоказанный факт, я его не знаю.