Меню

Линейный конгруэнтный генератор мощностью

Линейные конгруентные генераторы

Сегодня очень часто применяются линейные конгруентные генераторы, созданные Лемером. В них последовательность целых чисел Z 1,Z 2,… определяется по формуле

Где m – модуль (деление по модулю означает взятие остатка от деления на m), a – множитель, с – приращение и Z 0 – начальное значение являются неотрицательными целыми числами.

Очевидно, что остаток от деления всегда меньше делителя, поэтому . Чтобы получить случайные числа в интервале [0,1), примем U i=Z i/m.

Если с=0, то линейный конгруентный генератор называется мультипликативным, а при c>0 – смешанным. Мультипликативные генераторы появились раньше и использовались более интенсивно. Большинство генераторов, которые применяются сегодня, являются мультипликативными. У них не может быть полного периода, однако они более изучены и факт улучшения эффективности в связи с введением смешанных генераторов пока не доказан.

Пусть n – число битов в слове компьютера, которые действительно доступны для хранения данных. Например, если в компьютере используются 32 — битные слова, а крайний левый бит является знаковым то n=31. Модуль стараются выбрать равным m=2 n =2 31 . В этом случае избегают явного деление на m, которое заменяется обработкой ситуации переполнения разрядной сетки.

В качестве параметра a обычно выбирают числа вида 8k+3 или 8k+5. В этом случае для мультипликативного генератора можно получить период 2 n-2 , причем операция умножения заменяется сдвигом и сложением (умножение на степень двойки – это, по сути, сдвиг числа в разрядной сетке).

Например, в одном из предлагаемых в литературе генераторов a=1073741821, с=0, m=2 31 , Z 0=65539. Используются 32-разрядные числа, причем первый разряд интерпретируется как знаковый. Полный период такого генератора равен 2 31-2 .

Потоки случайных чисел (независимые последовательности) в линейном конгруентном генераторе задаются посредством определения начального числа каждого потока. Например, если нам нужны потоки в 100000 чисел каждый, то зададим для первого потока Z 0 =произвольное значение, для второго потока возьмем начальное значение Z 100000 , а для третьего – начальное значение Z 200000 и т.д. Т.е., в качестве потоков выступают непересекающиеся смежные последовательности случайных чисел.

В системе GPSS World используется мультипликативный конгруентный генератор с периодом 2 31-2 . Он выдает равномерно распределенные числа в интервале [1, 2 147 483 647], которые затем нормируются и преобразуются в числа из интервала 0 – 0,999999 включительно либо в числа от 0 до 999, в зависимости от контекста использования.

Можно использовать любое количество генераторов без специального их объявления, обращаясь к стандартному числовому атрибуту (системной переменной) RNj. Т.е., RNj – это значение генератора случайных чисел, равномерно распределенных на интервале [0,1). Номер генератора j является одновременно и его начальным значением (Z 0). Таким образом, каждый генератор задает отдельный поток случайных чисел. Изменить начальное значение генератора в процессе его работы можно только для первых 7 генераторов (с номерами 1 ÷ 7) с помощью оператора

Источник

Конгруэнтные генераторы

Линейные конгруэнтные генераторы

Пусть x, a, c Є Vn — случайно фиксированные элементы. Обычно говорят, что последовательность x1, x2, … Є Vn создается линейным конгруэнтным генератором с параметрами (xn, a, c, N), если такая последовательность удовлетворяет рекуррентному соотношению:

Характеристика x Є Vn называют начальным параметров, a ≠ 0 — множителем, с — приращением, N — сила алфавита за модулем. Если c = 0, то (формула №1) определяет мультипликативный конгруэнтный генератор, а если c ≠ 0 — смешанный конгруэнтный генератор. Нужно отметить, что Д. Лемер предложил мультипликативный конгруэнтный генератор в 1948 году, а У. Томсон смешанный конгруэнтный генератор в 1958 году.

Для любых K ≥ 1, t ≥ 0 общий показатель конгруэнтной последовательности (формула №1) удовлетворяет соотношению xi+k:

  • (xi +kc) mod N, если a = 1
  • (a k xi + (a k -1)/(a-1)×c) mod N, если a > 1
  • Формула №2

при этом будет такой номер 0 ≤ T ≤ N — 1, что последовательность (формула №1), начиная с этого номера T, зацикливается с периодом 1 ≤ U ≤ N, таким, что T + U ≤ N:

Доказательство

Соотношение (формула №2) получается К-кратным рекурсивной реализации соотношение (формула 1) с учетом известного равенства:

  • 1+ a + a 2 + … + a k-1 = (a k -1)/(a-1)

Факт зацикливания последовательности t> вытекает из вида рекуррентного соотношения (формула 1). Действительно, множество разрешимых значение xt, не может иметь других элементов, кроме элементов множества <0, 1, …, N — 1>силы N. Однако, если для некоторого наименьшего значения индекса t` совпали компоненты последовательности xt` = x, где t« — t` = U, то такое соотношение сохранится и для следующих значений индексов:

Из (формула №2) видно, что при a = 1 нецелесообразно реализовывать для имитации РРСП.

Следствие теоремы 1

Для любого k ≥ 1 при a > 1 подпоследовательность [x, xk,x2k, x3k…] взятая из конгруэнтной последовательности (формула 1) удалением всех членов с номерами, не кратными k, является линейной смешанной конгруэнтной последовательностью с параметрами (x,a¬,c¬,N), где a¬ = a k mod N, c¬ = (a k -1)/(a-1) mod N.

Доказательство

Исследуемую подпоследовательность обозначим xi = xik, i = 0,2. Тогда (формула №2) будет иметь вид:

Что и видно, согласно (формула 1), конгруэнтную последовательность с новыми параметрами.

Следствие 2

Для общего члена линейной смешанной конгруэнтной последовательности (формула 1) при a > 1:

  • xk = ((a k x) + (a k -1)/(a-1) × C) mod N, k = 1,2..
  • Формула №4

Доказательство

Полагая в (формула 2) t = 0, получаем (формула 4).

Следствие 3

Максимальное возможный период конгруэнтной последовательности (формула 4) не превышает силы текущего алфавита Umax ≤ N.

Доказательство

Из теоремы 1, U ≤ N — T, где 0 ≤ T ≤ N — 1. Поэтому Umax ≤ N.

Одной из главных задач при создании конгруэнтного генератора является поиск значений x,a,c для которых период достигает максимально разрешимого значение Tmax. Тонкости программного использования такого генератора (формула 1) приводит к трём самым реализуемым вариантам задания модуля N:

  • N = 2 q , где q + 1: число двоичных разрядов ЭВМ, нужных для целочисленной арифметики
  • N = 10 q , q ≥ 1
  • N — простое число
Читайте также:  Как мощность двигателя зависит от смеси топлива

Для линейной конгруэнтной последовательности (формула 1) максимальное значение периода Umax = N достигается, когда выполнены следующие условия:

  • c и N — взаимно простые числа
  • число b = a — 1 кратно P для любого числа P, являющегося делителем N
  • число b кратно 4, если N кратно 4

Если с = 0, то максимально возможный период мультипликативной конгруэнтной последовательности равен Umax = λ(N) и достигается, если x и N — взаимно простые числа и а — первообразный элемент по модулю N (a λ(N) )

Следствие 4

Если N = 2 q , q ≥ 4, то максимальное значение периода Umax = 2 q-2 = N/4 достигается, если x ≥ 1 — нечётное число и a (mod8) Є <3,5>.

Если c = 0, N = 10 q , q ≥ 5 и x не кратно двум или пяти, то максимально разрешимое значение периода Umax = 5 × 10 q-2 = N/20 достигается тогда, когда вычет a (mod 200) принимает одно из следующих 32 магических значений:

  • 3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91, 109, 117, 123, 131, 133, 139, 141, 147, 163, 171, 173, 179, 181, 187, 189, 197

Если c = 0, x и N — простое число, то максимально разрешимое значение периода Umax = N — 1 достигается, если a (mod N) ne; 0 и :

где p1… ps — простые числа, определяющие каноническое разложение числа N — 1: N — 1 = p1 m1 …, а m1.. — некоторые натуральные числа.

N = 2 5 — 1 = 31, N — 1 = 2 × 3 × 5, так что s = 3, p1 = 2, p2 = 3, p3 = 5. Согласно теореме 5, получаем следующие ограничения на выбор множителя a:

  • a ≠ 0 (mod 31), a 15 — 1 ≠ 0 (mod 31)
  • a 10 — 1 ≠ 0 (mod 31), a 6 — 1 ≠ (mod 31)

Нужно отметить, что в мультипликативных конгруэнтных генераторах РРСП для ПК Pentium часто используют модуль N = 2 31 — 1 = 2147483647. При этом рекомендуемыми значениями множителя а являются следующие числа:

  • 16807, 630360016, 1078318381, 1203248318, 397204094, 2027812808, 13232572445, 764261123, 112718

При этом достигается максимальное значение периода Umax = N — 1

Линейные конгруэнтные генераторы псевдослучайных последовательностей имеют слабость, которая может быть взята в основу криптоатак. Если смотреть последовательность биграммы (z1, z2): z1 = xt, z2 = xt+1, то в силу (формула 1) на плоскости R2 точки (z1,z2) будут лежать на прямых семейства:

Если бы t> являлась РРСП, то точки z1,z2 были бы распределены равномерно. На рис.1 видна диаграмма рассеяния для простого смешанного конгруэнтного генератора (для 64 последовательных значений).

Диаграмма рассеяния конгруэнтного генератора

Рисунок — 1, Диаграмма рассеяния для М = 64

На рис.2 показано диаграмма рассеяния для генератора 500 значения:

Диаграмма рассеяния конгруэнтного генератора

Рисунок 2, Диаграмма рассеяния для M = 2 31 — 1

Для скрытия этих недостатков реализуют нелинейные конгруэнтные генераторы.

Нелинейные конгруэнтные генераторы

Квадратичный конгруэнтный метод

  • zt+1 = (dx2t + axt + c) mod N, t = 0,1,2…

Характеристики (x, a, c, d, N) Є V 4 N × N квадратичной конгруэнтной последовательности (следствие 5) реализует максимально возможный период Umax, определяются теоремой 6.

Квадратичная конгруэнтная последовательность (следствия 5) имеет самый больший период Umax = N тогда, когда реализованы следующие 4 условия:

  • c и N — взаимно простые числа
  • d и a — кратные Р, где Р — любой нечётные простой делитель для N
  • d — чётное число, причём d = a — 1 (mod 4), если N кратно 4, и d = a-1 (mod 2), если N кратно двум
  • если N кратно девяти, то либо d (mod 9) = 0, либо d (mod 0) = 1 и cd(mod9) = 6

Следствие 5

Если N = 2 q , q ≥ 2, то самый больший период Umax = 2 q для квадратичной конгруэнтной последовательности, достигается тогда, когда C нечётно, d чётно, а a — нечётное число:

  • a = ( d + 1) mod 4

Квадратный метод Ковэю

  • xt+1 = (xt(xt+1))mod2 q , t = 0,1,2..

Где модуль N = 2 q , q ≥ 2, а начальное значение x выбирается так, что x (mod 4) = 2. Максимальное значение периода Umax = 2 q-2 = N/4. Для повышения компьютерного быстродействия этого нелинейного генератора целесообразно выбирать q равным числу двоичных разрядов, нужных для записи целого числа в ЭВМ (к примеру q = 31)

Метод середины квадрата

  • xt+1 = (xt 2 (mod 2 3q ) — xt 2 (mod 2 q ))/2 q , t = 0,1,2..

где q, x — параметры этого нелинейного генератора псевдослучайной последовательности. Начальное значение x ≠ 1 выбирается среди натуральных чисел, не превосходящих числа 2 2q — 1, так, чтобы x 2 (mod 2 q ) ≠ 0. Этот метод первым предложил Джоном фон Нейманом в 1946 году.

Источник



Конгруэнтные генераторы. Линейные конгруэнтные генераторы.

Все конгруэнтные генераторы используют для получения нового состояния рекуррентную формулу вида \[s_ = f(s_i) \mod m,\] где \(m\) – модуль, являющийся положительной целой степенью простого числа. Выходная последовательность обычно совпадает с последовательностью состояний.

Семейство конгруэнтных генераторов определяется общим видом функции \(f: S\to S\) , например, линейные конгруэнтные генераторы используют линейную функцию \(f\) . Конкретный генератор в семействе определяется конкретными параметрами функции \(f\) .

Линейные конгруэнтные генераторы (ЛКГ)

ЛКГ используют рекуррентную формулу вида \[s_ = a\cdot s_i + c \mod m,\] где \(m\) – модуль, \(s_i\) – состояния, \(a\) – “множитель”, \(c\) – “приращение”. Так же необходимо задать \(s_0\) – начальное состояние.

Конкретный генератор из семейства задаётся значениями \(a\) , \(c\) , \(m\) .

Если \(c = 0\) , такие генераторы называются мультипликативными, или генераторами Лемера.

Длина периода

Удачный выбор параметров ЛКГ даёт известную и достаточно большую длину периода. Однако, на практике, неудачный выбор параметров сделать гораздо проще, чем удачный. Так, например, при \(a=1, c=1\) , ЛКГ превращается в обычный счётчик по модулю \(m\) , который явно не похож на случайную последовательность.

Читайте также:  Физика мощность печи для

Исторически, неудачный выбор параметров приводил к крайне сомнительным результатам. Одним из примеров является генератор RANDU, разработанный в IBM и широко использовавшийся в 1970-х годах (в частности, компиляторами FORTRAN). В нём использовались параметры \(a=65539=2^<16>+3, c=0, m=2^<31>\) , и чётным начальным значением. Хотя этот метод даёт равномерно распределённые значения, они крайне очевидно не являются независимыми. Действительно, рассмотрим последовательность 3 значений \(\, s_\>\) :

\[s_ = (2^<16>+3)s_ = (2^<16>+3)^2 s_\] \[s_ = (2^<16>+3)s_ = (2^<32>+6 \cdot 2^<16>+9) s_\] Т.к. \(2^ <32>\mod 2^31 = 0\) , \[s_ = (6 \cdot 2^<16>+9) s_\] Учитывая \(s_ = (2^<16>+3) s_\) , можем записать \[s_ = [6 (2^ <16>+ 3) — 9] s_\] \[s_ = 6 s_ — 9 s_\]

То есть каждое третье значение однозначно определяется двумя предыдущими. По сути, это уравнение описывает плоскость в 3-мерном пространстве, и если рассматривать каждые три последовательных числа как координаты точки, то все эти точки будут лежать на такой плоскости (технически, из-за модульной арифметики, это семейство 15 плоскостей)

Нормированное распределение точек в RANDU

Существует три варианта выбора параметров. Рассмотрим каждый из них отдельно.

\(m\) простое, \(c=0\)

Этот случай соответствует генератору Лемера. Если \(a\) является примитивным элементом мультипликативной группы целых по модулю \(m\) , то период генератора очевидно равен \(m-1\) . Начальное состояние \(s_0\neq 0\) .

Один из недостатков простого модуля в том, что при использовании двоичной арифметики при вычислениях, в отличие от случая \(m=2^n\) , необходим явный шаг вычисления модуля, и двойной объем памяти при умножении.

Второй недостаток заключается в том, что если необходимо получить равномерно распределённую последовательность бит, числа в диапазоне \([1,m)\) не всегда тривиально можно преобразовать.

В качестве \(m\) часто выбираются числа Мерсенна, например \(2^<31>-1\) или \(2^<61>-1\) .

Для вычисления в ограниченном числе разрядов можно применить алгоритм Шража 1 . Представим \(m\) в виде \[m = qa+r,\] \(q = \left\lfloor \frac \right\rfloor\) , \(r = m \mod a\) .

Затем рассчитаем \[as \mod m = a(s \mod q) − r \left\lfloor \frac \right\rfloor\]

Поскольку \(s\mod q , первый член строго меньше чем \(am/a = m\) . Если выбрать \(a\) таким образом, чтобы \(r \le q\) (т.е. \(r/q \le 1\) ), то второй член так же меньше \(m\) : \[r \left\lfloor \frac \right\rfloor \le r\frac ≤ x

Тогда оба этих члена можно вычислить в том же числе разрядов, в которых представимо \(m-1\) , а их разность лежит в пределах \([1−m, m−1]\) , который легко привести к диапазону \([0, m−1]\) , просто прибавляя \(m\) , если первый член меньше второго.

\(m=2^n\) , \(c=0\)

Если \(m=2^n\) , то при использовании двоичной арифметики в \(n\) разрядах, вычисление резко упрощается. Действительно, поскольку беззнаковые вычисления в \(n\) разрядах по сути являются арифметикой \(\mod n\) , для вычисления достаточно одного умножения.

Есть, однако, обратная сторона.

Возьмём ЛКГ \[s_ = as_i \mod 2^n\] и рассмотрим младшие \(l\) бит состояния \(s_i\) : \[t_i = s_i \mod 2^l.\] Тогда \[t_ = (as_i \mod 2^n) \mod 2^l\] \[t_ = at_i \mod 2^l,\] и тогда младшие \(l\) бит тоже образуют линейную конгруэнтную последовательность с меньшим модулем. А поскольку период меньше модуля, то в лучшем случае, младший бит никогда не меняется, второй по старшинству бит меняется каждый раз, и так далее. Таким образом младшие биты оказываются значительно менее “случайными”, чем старшие.

\(c\neq 0\)

При корректном выборе параметров и \(c\neq 0\) , длина периода может достигать \(m\) .

Теорема Халла-Добелла

ЛКГ, задаваемый рекуррентным соотношением \[s_ = a s_i + c \mod m,\] \(c \neq 0\) достигает периода \(m\) iff:

  1. \(m\) и \(c\) взаимно простые
  2. \(a-1\) делится на все простые множители \(m\)
  3. \(a-1\) делится на 4, если \(m\) делится на 4.

Лемма 1

Пусть \(p\) – простое число, а \(e\) – положительное целое число, такое, что \(p^e > 2\) . Если \[x = 1 \mod p^e,\] \[x\neq 1 \mod p^,\] то \[x^p = 1 \mod p^,\] \[x^p \neq 1 \mod p^.\]

\(\Delta\) : По условию теоремы, \(x = 1 + qp^e\) для некого целого \(q\) . Тогда \[x^p = (1+qp^e)^p = 1 + C_p^1 qp^e + \ldots + C_p^q^p^+q^pp^,\] где \(C_n^k = \frac\) – биномиальный коэффициент. \[x^p = 1 + qp^(1 + C_p^2 q p^ + \ldots + C_p^q^p^+q^ p^).\] Выражения вида \[C_p^k q^ p^\] должны делиться на \(p^\) . Действительно, для \(1 \(C_p^k\) делится на \(p\) .

Последний член \(q^ p^\) так же делится на \(p\) , поскольку \(e(p-1) > 1\) при \(p^e>2\) (что легко проверить перебором, при \(e=1\) , \(p>2\) , при \(e=2\) , \(p\ge 2\) ).

Таким образом, все члены в скобках кроме \(1\) делятся на \(p\) и тогда \[x^p = 1+qp^ \mod p^.\] \(\not \Delta\)

Пусть число \(m\) раскладывается на простые множители \[m=p_1^ \ldots p_t^.\] Тогда длинна периода \(\lambda\) линейной конгруэнтной последовательности, определяемой параметрами \((s_0, a, c, m)\) , является наименьшим общим кратным длин \(\lambda_j\) периодов линейных конгруэнтных последовательностей \((s_0 \mod p_j^, a \mod p_j^, c \mod p_j^, p_j^)\) , \(1 \le j \le t\) .

\(\Delta\) : Используя индукцию по \(t\) , достаточно доказать лемму для \((s_0, a, c, m_1m_2)\) , где \(m_1\) и \(m_2\) – взаимно простые. Тогда \(\lambda\) будет НОК \(\lambda_1\) последовательности \((s_0 \mod m_1, a \mod m_1, c \mod m_1, m_1)\) и \(\lambda_2\) последовательности \((s_0 \mod m_2, a \mod m_2, c \mod m_2, m_2)\) . Отметим, что если элементы этих последовательностей обозначены соответственно \(x_i\) , \(y_i\) , \(z_i\) , то справедливы равенства \[y_n = x_n \mod m_1,\] \[z_n = x_n \mod m_2.\] Действительно, \[y_0 = x_0 \mod m_1,\] \[y_1 = (a y_0 + c) \mod m_1 = (a x_0 + c) \mod m_1,\] по индукции, \[y_n = (a x_ + c) \mod m_1 = x_n \mod m_1.\]

Читайте также:  Стабилизатор напряжения мощность 3000 вт

Аналогично для \(z_n\) .

Тогда \(\forall k\) , \[x_n = x_k \mod m_1m_2 \iff\] \[y_n = y_k \mod m_1,\] \[z_n = z_k \mod m_2.\]

Пусть теперь \(\lambda’\) – НОК( \(\lambda_1\) , \(\lambda_2\) ). Докажем, что \(\lambda’ = \lambda\) . Так как \(x_n = x_\) для всех достаточно больших \(n\) , то \(y_n = y_\) и \(z_n = z_\) , следовательно, \(\lambda\) кратно \(\lambda_1\) и \(\lambda_2\) , и следовательно \(\lambda \ge \lambda’\) . С другой стороны, \(y_n = y_\) и \(z_n = z_\) для достаточно больших \(n\) и следовательно \(x_n = x_\) , и тогда \(\lambda \le \lambda’\) .

Из леммы 2 следует, что теорему достаточно доказать для случая, когда \(m\) – степень простого числа, поскольку \[m = p_1^ \ldots p_t^ = \lambda = НОК(\lambda_1,\ldots,\lambda_t)\le\lambda_1\ldots\lambda_t\le p_1^ \ldots p_t^\] iff \(\lambda_j = p_j^\) для \(1\le j \le t\) .

Поэтому положим \(m=p^e\) , где \(p\) – простое, а \(e\) – натуральное. Для \(a=1\) утверждение теоремы достаточно очевидно, поэтому рассмотрим случай \(a>1\) . Период имеет длину \(m\) iff каждое целое \(0\le x встречается в последовательности ровно один раз. Действительно, никакое значение не может встретиться более одного раза и значений \(\mod m\) ровно \(m\) . Тогда без ограничения общности можем положить \(s_0 = 0\) . Рассмотрим общую формулу для \(s_n\) : \[\begin s_ & = as_+c \mod m \\& = a^2s_+ac+c \mod m \\& = a^3s_+a^2c+ac+c \mod m \\& = \ldots \\& = a^ks_+c\sum_^a^k \mod m \\& = a^ks_+c\frac \mod m. \end\] Тогда при \(s_0=0\) имеем \[s_n = c\frac \mod m.\] Если \(c\) и \(m\) не являются взаимно простыми, то \(s_n \neq 1\) , то есть условие (1) теоремы является необходимым. Период по определению есть наименьшее положительное \(n\) , для которого \(s_n = s_0 = 0\) . Тогда теорема сводится к следующей лемме:

Пусть \(1 , где \(p\) – простое число. Если \(\lambda\) есть наименьшее натуральное число, для которого \[\frac = 0 \mod p^e,\] то \(\lambda = p^e\) iff \(a=1 \mod p\) при \(p>2\) и \(a=1\mod 4\) при \(p=2\) .

Положим \(\lambda=p^e\) и при этом \(a\neq 1 \mod p\) . Тогда \[\frac = 0 \mod p^e,\] iff \[a^\lambda-1 = 0 \mod p^e,\] и \[a^\lambda = a^ = 1 \mod p^e,\] но по теореме Ферма \(a^n = a \mod n\) , что приводит к противоречию. Если \(p=2\) и \(a\neq 1 \mod 4\) , то \(a=3\mod 4 \neq 1 \mod 2^e\) для \(e>1\) и \[a^ <2^e>= 1 \mod 2^e.\]

Следовательно, чтобы \(\lambda=m\) , условия (2,3) теоремы необходимы. То есть, необходимо, чтобы \(a=1+qp^f\) , где \(p^f>2\) и \(q\) не кратно \(p\) .

Остаётся доказать, что это условие достаточно. Применяя лемму 1, находим, что \(\forall g\ge 0\) : \[a^ = 1 \mod p^,\] \[a^ \neq 1 \mod p^,\] и тогда \[\frac-1> = 0 \mod p^, \tag<*>\] \[\frac-1> \neq 0 \mod p^,\tag<**>\] в частности, это верно для \(g=e\) . Для последовательности \((0, a, 1, p^e)\) , справедливо \[s_n = \frac \mod p^e.\] Но это значит, что период этой последовательности есть \(\lambda\) . То есть \(s_n = 0\) iff \(n\) кратно \(\lambda\) . Но поскольку \[\frac-1> = 0 \mod p^,\] то \(p^e\) кратно \(\lambda\) . Поскольку \(p\) – простое, это возможно только если \(\lambda=p^g\) для некоторого \(g\) . Но \(\lambda\) – наименьшее число, для которого верно \[\frac = 0 \mod p^e,\] и тогда индуктивные рассуждения для \((*)\) и \((**)\) показывают, что \(\lambda = p^e\) . \(\not \Delta\)

Следствия теоремы

Из доказательства теоремы Халла-Добелла прямо следуют так же выражения максимального периода для случая \(c=0\) .

Действительно, если \(c=0\) , то \(x_n = a^n x_0 \mod m\) . По лемме 2, период любой ЛКП зависит от длин последовательностей при \(m=p^e\) . Если \(x_n = a^n x_0 \mod p^e,\) и \(a\) кратно \(p\) , период будет иметь длину не более \(e\) . Поэтому рассмотрим случай, когда \(a\) и \(p\) – взаимно простые. Тогда период \(\lambda \in \mathbb N\) – это наименьшее число, такое, что \[x_0 = a^\lambda x_0 \mod p^e.\] Если теперь \(p^f = НОД(x_0, p^e)\) , то это требование эквивалентно \[a^\lambda = 1 \mod p^.\] По теореме Эйлера, \(a^ <\varphi(m)>= 1 \mod m\) , поэтому \(\lambda\) является делителем \(\varphi(p^)\) , \[\varphi(p^) = p^(p-1).\] Eсли \(x_0\) и \(p^e\) взаимно простые, \(p^f=1\) , \(f=0\) и \[\varphi(p^) = p^(p-1).\]

Это позволяет определить \(\lambda(m)\) : \[\lambda(m) = \left\lbrace\begin 1, && m=2 \\ 2, && m=4 \\ 2^, && m=2^e, e\ge3 \\ p^(p-1), && m=p^e, p>2 \\ p^(p-1), && m=p^e, p>2 \\ НОК(\lambda(p_1^),\ldots,\lambda(p_n^)), && m = p_1^\ldots p_n^ \end\right.\tag<*>\]

Вышеперечисленные рассуждения можно кратко сформулировать следующим образом.

Максимальным периодом, возможным при \(c=0\) является \(\lambda\) , определённое в \((\text<*>)\) . Этот период достигается, если:

  1. \(x_0\) и \(m\) – взаимно простые
  2. \(a\) является первообразным элементом мультипликативной группы по модулю \(m\) .

В случае \(m=2^e\) , имеем \[\lambda = p^ = m/4,\] а требования на множитель сводятся к \(a = 3 \mod 8\) или \(a=5\mod 8.\)

Источник