b является примитивным корнем, когда его порядок равен p-1, поэтому b ^ k может принимать любое значение от 1 до p-1, в зависимости от значения k.
Порядок элемента равенминимум s с b ^ s = 1 (мод р).b является примитивным корнем тогда и только тогда, когда b ^ (phi (p) / k)! = 1 (! = означает различное) для каждого k делителя phi (p) и phi (p) = (p-1) - это функция Эйлера (http://en.wikipedia.org/wiki/Euler%27s_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), есть некоторыеЗначения а, б и т. Периоды, которые птакже не полностью пригодился (см. статью).
База b = 2 ^ 32 не имеет полного периода, но возвращает целые числа от 0 до 2 ^ 32-1.База b = 2 ^ 32-1 не может вернуть несмещенные 32-битные целые числа (никогда не вернется число 2 ^ 31-1 = 4294967295).