The maximum period of rational number generator

Full Text

Введение
Под генератором псевдослучайных чисел понимаю машинный алгоритм, вычисляющий 
последовательность чисел, обладающую свойствами случайной последовательности, 
например, такими как частотоустойчивость, хаотичность, типичность и непредсказуемость
[1]. Случайные числа находят огромное практическое применение в самых широких областях 
математики, начиная от численного анализа и заканчивая компьютерным 
программированием. При этом к качеству псевдослучайных генераторов предъявляются 
серьезные требования, поскольку от того, насколько «случайной» будет используемая 
последовательность зависит успех в решении той или иной задачи. 
Традиционно псевдослучайные генераторы разделяют на аппаратные, табличные и 
алгоритмические [2]. Один из первых примеров алгоритмического генератора предложил 
Джон фон Нейман в 1946 году, его мысль заключалась в том, чтобы взять некое случайное 
число, возвести его в квадрат и выписать серединные цифры. Другие классические примеры
генераторов псевдослучайных чисел – линейный конгруэнтный и линейный рекуррентный 
методы (источники [3], [4] соответственно), а также линейный обратный конгруэнтный 
генератор. В настоящей работе будет рассмотрен еще один алгоритмический генератор, 
рациональный генератор, являющийся обобщением инверсного конгруэнтного генератора. 
1. Обратный конгруэнтный генератор
Одним из классических методов генерации псевдослучайных чисел является обратный 
конгруэнтный генератор или генератор Айхенауэра–Лена.
Данный генератор основан на использовании обратного, по модулю числа для 
нахождения следующего элемента последовательности.

Определение 1. Обратной конгруэнтной последовательностью называется
последовательность следующего вида:
????????+1 = (????????????
−1 + ????) (???????????? ????), (1)
где ???? −простое, ????, ???? ∈ ????, 0 ≤ ???? < ????, 0 ≤ ???? < ????.
Элементы последовательности ???????? принимают значения {0,1, … , ???? − 1, ∞}, а обращение 
определено как 0
−1 = ∞, ∞−1 = 0.
Будем в дальнейшем считать, что p – простое число.
Главной и наиболее трудоемкой задачей при построении этой последовательности 
является нахождение ????????
−1
в конечном простом поле, сделать это можно используя, например,
расширенный алгоритм Евклида.
Одним из основных качественных требований, предъявляемых к источнику 
псевдослучайных чисел, является достаточно большая длина периода, гарантирующая, что для 
данной решаемой задачи не произойдет быстрого зацикливания. Более того, большая длина 
периода должна быть математически обоснованной. Подобные результаты об оценках длин 
периодов различных псевдослучайных последовательностей можно легко найти в литературе, 
например, [5]
Заметим, для любой последовательности ????????+1 = ????(????????
) ???????????? ????, где f – целочисленная 
функция, длина периода ≤ ????. Тогда для обратного конгруэнтного генератора можно 
утверждать, что длина его периода не превосходит числа всех различных элементов 
последовательности, то есть ???? + 1. 
Напомним критерий максимальности длины периода обратной конгруэнтной 
последовательности. Следующая теорема была доказана Ю. Айхенауэром и Ю. Леном в 1986 
году, [6].
Теорема 1. Последовательность (1), определяемая параметрами a,c,p, ????0 имеет 
максимальную длину периода, равную ???? + 1 тогда и только тогда, когда характеристический 
многочлен ????(????) = ????
2 − ???????? − ???? удовлетворяет свойствам
1) ????
????+1 ≡ ????(???????????? ????(????), ????), где ???? ≠ 0;
2) ????
????+1
???? ≡ ???????? + ????(???????????? ????(????), ????), где ???? −любое простое число, такое, что ???? делит ???? + 1 и 
???? ≠ 0. 
Доказательство теоремы можно разбить на промежуточные этапы, которые удобно 
сформулировать в виде следующих лемм.
Лемма 1.
(
0 1
???? ????
)
????
= (
????????????−1 ????????
???????????? ????????+1
),
при этом ????0 = 0; ????1 = 1; ????????+1 = ???????????? + ????????????−1.
В лемме 1 строится вспомогательная последовательность ????????. Следующая лемма 2 
показывает, как произвольный элемент обратной конгруэнтной последовательности явно 
выражается через элементы ????????.
Лемма 2. Положим ????????+1 = ????????????
−1 + ????(???????????? ????), тогда
???????? =
????????+1????0 + ????????????
????????????0 + ????????????+1
(???????????? ????).
Далее, обозначим ????(????) = ????
2 − ???????? − ????????. Оказывается, что остаток при делении ????
???? на 
многочлен ????(????) зависит от элементов построенной выше вспомогательной 
последовательности.
Лемма 3. Для любого натурального числа n имеет место
????
???? ???????????? ????(????) = ???????????? + ????????????+1.
Ниже будет показано, как можно обобщить приведенные результаты.
2. Рациональный генератор
Рассмотрим следующее обобщение обратного конгруэнтного генератора.
Определение 2. Рациональной последовательностью будем называть
последовательность, определяемую следующим образом:
????????+1 =
???????????? + ????
???????????? + ????
(???????????? ????), (2)
где ???? − простое, ????, ????, ????, ???? ∈ ????. Обращение 0 и ∞ определяется также, как сказано выше.
Рассмотрим предыдущий член последовательности ????????, 
???????? =
????????????−1 + ????
????????????−1 + ????
;
подставим в (2):
????????+1 =
????
????????????−1 + ????
????????????−1 + ????
+ ????
????
????????????−1 + ????
????????????−1 + ????
+ ????
=
????(????????????−1 + ????) + ????(????????????−1 + ????)
????(????????????−1 + ????) + ????(????????????−1 + ????)
=
(????
2 + ????????)????????−1 + (???????? + ????????)
(???????? + ????????)????????−1 + (???????? + ????
2)
.
Рассмотрим матрицу 
???? = (
???? ????
???? ????
),
возведем ее в степень n, и обозначим элементы получившейся матрицы следующим образом:
(
???? ????
???? ????
)
????
= (
???????? ????????
???????? ????????
),
считаем по определению ????1 = ????; ????1 = ????; ????1 = ????; ????1 = ????. Вычислим, как связаны элементы 
матриц ????
???? и ????
????+1
, 
(
????????+1 ????????+1
????????+1 ????????+1
) = (
???? ????
???? ????
)
????
(
???? ????
???? ????
) = (
???????? ????????
???????? ????????
) (
???? ????
???? ????
) = (
???????????? + ???????????? ???????????? + ????????????
???????????? + ???????????? ???????????? + ????????????
).
Отсюда имеем 
????????+1 = ???????????? + ????????????, ????????+1 = ???????????? + ????????????,
????????+1 = ???????????? + ????????????, ????????+1 = ???????????? + ????????????.
(3)
Таким образом, доказано утверждение, которое является аналогом Леммы 1 для 
рационального генератора.
Утверждение 1. Для матрицы
(
???? ????
???? ????
)
????
= (
???????? ????????
???????? ????????
)
элементы ????????, ????????, ????????, ???????? вычисляются рекуррентно по формулам (3).
Следующее утверждение является переносом леммы 2 на случай рационального 
генератора.
Утверждение 2. Для рациональной последовательности, определенной в (2), имеет 
место
???????? =
????????????0 + ????????
????????????0 + ????????
(???????????? ????).
Доказательство данного утверждения проводится методом математической индукции.
База индукции очевидна, при ???? = 1 доказываемая формула совпадает с определением,
????1 =
????1????0 + ????1
????1????0 + ????1
=
????????0 + ????
????????0 + ????
(???????????? ????).
Предположим, что доказываемое равенство верно для любых натуральных чисел, 
меньших ????. По определению рациональной последовательности для любого ???? верно
???????? =
????????????−1 + ????
????????????−1 + ????
.
Далее, по предположению индукции верно
????????−1 =
????????−1????0 + ????????−1
????????−1????0 + ????????−1
Подставим это представление ????????−1 в последнюю формулу для ????????, раскроем скобки и приведем 
подобные слагаемые, сократим знаменатели:
???????? =
(????????−1???? + ????????−1????)????0 + (????????−1???? + ????????−1????)
(????????−1???? + ????????−1????)????0 + (????????−1???? + ????????−1????)
Используя формулы (3), получим
???????? =
????????????0+????????
????????????0+????????
(???????????? ????).
Определим для рациональной последовательности следующие два характеристических 
многочлена
????(????, ????) = ????
2 − ???????? − ????????,
????(????, ????) = ???????? − ???????? − ????????.
Будем говорить, что многочлен ℎ(????1, ????2, … , ????????
) при делении на многочлены ????1
(????1, ????2, … , ????????
) и 
????2
(????1, ????2, … , ????????
) дает остаток ????(????1, ????2, … , ????????
), если найдутся многочлены ℎ1
(????1, … , ????????
) и 
ℎ2
(????1, … , ????????
), такие, что
ℎ(????1, … , ????????
) = ????1
(????1, … , ????????
)ℎ1
(????1, … , ????????
) + ????2
(????1, … , ????????
)ℎ2
(????1, … , ????????
) + ????(????1, … , ????????
)
и суммарная степень ????(????1, … , ????????
) строго меньше, чем суммарная степень ℎ(????1, … , ????????
). Кроме 
того, при делении с остатком будем вычислять все числовые коэффициенты по простому 
модулю.
Утверждение 3. Одночлены ????
????+1 и ????
???????? при делении с остатком на многочлены ????(????, ????)
и ????(????, ????) в остатке дают следующие линейные функции:
????
????+1 ≡ ???????????? + ????????????(???????????? ????(????, ????), ????(????, ????), ????); (4)
????
???????? ≡ ???????????? + ????????????(???????????? ????(????, ????), ????(????, ????), ????). (5)
Доказательство. Так как вычисления проводятся по модулям ????(????, ????) и ????(????, ????), то можно 
отождествить ????
2 ≡ ???????? + ???????? и ???????? ≡ ???????? + ???????? по ???????????? ????(????, ????), ????(????, ????), ????.
Доказательство утверждения проведем по индукции. Сначала докажем сравнение (4).
База индукции тривиальна, действительно, при ???? = 1 имеем
????
2 ≡ ???????? + ???????? = ????1???? + ????1????.
Можно выполнить вычисления и для n=2:
????
3 ≡ ????????
2 + ???????????? = ????(???????? + ????????) + ????(???????? + ????????) = (????
2 + ????????)???? + (???????? + ????????)???? = ????2???? + ????2????.
Предположим, что для номера ???? − 1 доказываемое верно, т.е.
????
???? ≡ ????????−1???? + ????????−1???? (???????????? ????(????, ????), ????(????, ????), ????).
Покажем, что верно и для ????:
????
????+1 = ????????
???? ≡ ????(????????−1???? + ????????−1????) = ????????−1????
2 + ????????−1???????? ≡ ????????−1
(???????? + ????????) + ????????−1
(???????? + ????????)
= (????????−1???? + ????????−1????)???? + (????????−1???? + ????????−1????)???? (???????????? ????(????, ????), ????(????, ????), ????),
используя формулы (3), последнее выражение можно заменить так
????
????+1 ≡ ???????????? + ???????????? (???????????? ????(????, ????), ????(????, ????), ????).
Аналогично доказывается сравнение (5).
База проверяется очевидно:
???????? ≡ ???????? + ???????? = ????1???? + ????1????;
????
2???? = ???????????? ≡ ????(???????? + ????????) = ????????
2 + ???????????? ≡ с(???????? + ????????) + ????(???????? + ????????) = ???????????? + ???????????? + ???????????? + ????????????
= (???????? + ????????)???? + (???????? + ????????)???? = ????1???? + ????1???? (???????????? ????(????, ????), ????(????, ????), ????).
Аналогично выполняется шаг индукции,
????
???????? = ????????
????−1???? ≡ ????(????????−1???? + ????????−1????) = ????????−1????
2 + ????????−1???????? ≡ ????????−1
(???????? + ????????) + ????????−1
(???????? + ????????)
= ????????−1???????? + ????????−1???????? + ????????−1???????? + ????????−1????????
= (????????−1???? + ????????−1????)???? + (????????−1???? + ????????−1????)???? (???????????? ????(????, ????), ????(????, ????), ????),
из формул (3), получаем
????
???????? ≡ ???????????? + ???????????? (???????????? ????(????, ????), ????(????, ????), ????).
Полученные промежуточные утверждения о свойствах рационального генератора 
позволяют прейти к теореме о длине максимального периода, аналогичной теореме 1.
Теорема 2. Последовательность (2) имеет максимальный период равный ???? + 1 в том и 
только в том случае, если для многочленов ????(????, ????) = ????
2 − ???????? − ???????? и ????(????, ????) = ???????? − ???????? − ????????
выполняются условия
1) ????
????+2 = ???????? (???????????? ????(????, ????), ????(????, ????), ????);
2) для любого простого ????, делящего (???? + 1), имеет место
????
????+1
????
+1
≡ ???????? + ???????? (???????????? ????(????, ????), ????(????, ????), ????), где ???? ≠ 0.
Доказательство. Сначала докажем необходимость. Обозначим через ???? длину периода 
рациональной последовательности (2). Пусть последовательность (2) имеет период ???? + 1, 
тогда ????????+1 = ????0 или, другими словами, выполняется
????0 =
????????+1????0 + ????????+1
????????+1????0 + ????????+1
.
Если ???? = ???? + 1, то в периоде встречаются все возможные значения: ∞,0,1,… , ???? − 1. Тогда 
без ограничения общности можно считать, что ????0 = 0. Значит 
????????+1
????????+1
= 0,
то есть ????????+1 = 0, ????????+1 ≠ 0. Из утверждения 3 следует
????
????+2 ≡ ????????+1???? + ????????+1???? (???????????? ????(????, ????), ????(????, ????), ????) = ????????+1???? (???????????? ????(????, ????), ????(????, ????), ????),
получили первое условие в формулировке теоремы. 
Покажем, что также выполняется второе условие. Предположим противное, пусть для 
некоторого простого q, делящего (p + 1), верно 
????
????+1
????
+1
≡ ???????? (???????????? ????(????, ????), ????(????, ????), ????).
Значит из утверждения 3 имеем
????
????+1
????
+1
≡ ????????+1
????
???? (???????????? ????(????, ????), ????(????, ????), ????)
и ????????+1
????
= 0. Из утверждения 2 следует, что при ????0 = 0 выполняется
????????+1
????
=
????????+1
????
????????+1
????
= 0(???????????? ????).
Получаем, что ????????+1
????
= ????0 и, значит, период ???? < ???? + 1, противоречие. Окончательно получаем, 
что условие ???? = ???? + 1 влечет выполнение условий 1 и 2 теоремы.
Докажем в обратную сторону. Пусть ???? − период рациональной последовательности, и 
выполняются условия 1 и 2. Покажем, что ???? = ???? + 1.
Предположим, что ???? < ???? + 1, тогда при ????0 = 0 имеем ???????? = ????0 = 0, следовательно,
???????? =
????????
????????
= 0.
Из последнего получаем ???????? = 0, ???????? ≠ 0, значит в силу утверждения 3 имеет место
????
????+1 ≡ ???????????? + ???????????? = ???????????? (???????????? ????(????, ????), ????(????, ????), ????).
так-как
????
????+2 ≡ ????????+1???? + ????????+1???? (???????????? ????(????, ????), ????(????, ????), ????),
то из условия теоремы 1, ????
????+2 ≡ ????????+1???? вытекает ????????+1 = 0. 
Тогда 
????????+1 =
????????+1
????????+1
= 0,
откуда получаем, что ???? делит ???? + 1. Таким образом, можно считать, что ???? =
????+1
????
для 
некоторого ????, делящего ???? + 1. Из этого следует
????
????+1 = ????
????+1
????
+1
≡ ????????+1
????
???? + ????????+1
????
???? = ???????????? + ???????????? = ???????????? (???????????? ????(????, ????), ????(????, ????), ????),
что противоречит условию 2, поскольку коэффициент перед переменной y равен нулю: ???????? =
0. Значит предположение ???? < ???? + 1 не верно, и теорема доказана.
Заключение
Приведенное в заметке доказательство критерия максимальной длины периода 
рассмотренной рациональной последовательности позволяет утверждать, что введенный 
рациональный генератор имеет максимально возможную длину периода и тем самым 
удовлетворяет одному из основных требований, которые предъявляются к псевдослучайным 
последовательностям. В процессе работы рациональный генератор был успешно 
протестирован на случайность с помощью классических методов Пирсона, КолмогороваСмирнова, а также показал хорошие результаты при проверке критериями перестановок, 
максимум-t и монотонности. Поэтому можно утверждать о возможности практического 
использования рационального генератора наравне с обратным конгруэнтным. 

About the authors

Anton Fedotov

Author for correspondence.
Email: tony.fedotoff2016@yandex.ru
443086, Russia, Samara, Moscow Shosse, 34.

References

Supplementary files