Когда а и m - взаимно простые числа, наименьшее число Л, для которого а- = 1 (по модулю т), принято называть порядком а по модулю т. Любое такое значение а, которое имеет максимальный возможный порядок по модулю т, называют первообразным элементом по модулю т.

Обозначим через Л(т) порядок первообразного элемента, а именно - максимальный возможный порядок по модулю тп. Из замечаний следует, что Х{р) является делителем р~(р-1); достаточно легко (см. упр. 11-16, приведенные ниже) можно определить значения Л(т) во всех следующих случаях:

Л(2) = 1, Л(4) = 2, Л(2) = 2-, если е > 3;

Л(р)=р-1(р-1), если р>2; (9)

Л(рГ...рГ)=1ст(Л(рГ),---,А(рГ))-Все сказанное можно подытожить в следующей теореме.

Теорема В. [С. F. Gauss, Disquisitiones Arithmeticae (1801), §90-92.] Maкcямaльifым периодом, возможным, когда с = О, является Х(т), где Л(т) определено в (9). Этот период достигается, если:

i) Ло и т - взаимно простые числа;

ii) а является первообразным элементом по модулю тп.

Заметим, что можно получить период длиной тп - 1, если т - простое число; т. е. это всего на единицу меньше, чем максимальная длина периода. Так что для практических целей такой период может быть настолько длинным, насколько это необходимо.

Теперь возникает вопрос, как найти первообразные элементы по модулю т? В упражнениях, данных в конце раздела, приводится совершенно очевидный ответ на вопрос, когда т является простым числом или степенью простого числа. Результаты сформулированы в следующей теореме.

Теорема С. Число а является первообразным элементом по модулю р тогда я только тогда, когда выполняется одно из следующих условий:

i) р = 2,е = 1-иа - нечетное число;

ii) р = 2, е = 2 и а mod 4 = 3;

iii) р = 2, е = 3иа mod 8 = 3, 5 пли 7;

iv) р = 2, е > 4 и а mod 8 = 3 или 5;

v) р«- нечетное число, е = 1, а О (по модулю р) и а~> 1 (по модулю р) для любого простого делителя q числа р - 1;

vi) р - нечетное число, е > 1, а удовлетворяют условию (v) и а~ 1 (по модулю р). I

Условия (v) и (vi) теоремы легко проверяются на компьютере для больших р. Эффективные методы оценки степени, когда известны множители числа р - 1, обсуждаются в разделе 4.6.3.

Теорема С применима только к степеням простых чисел. Но если заданы значения aj, являющиеся первообразными элементами по модулю р, то можно найти

единственное значение а, такое, что а = Qj (по модулю pj) при \ < j <t, используя китайский алгоритм (алгоритм, построенный на основании китайской теоремы об остатках. - Прим. перев.), рассматриваемый в разделе 4.3.2, Число а будет первообразным элементом по модулю р... р<. Таким образом, существует приемлемый эффективный путь построения множителей, удовлетворяющих условию теоремы В, для любых модулей т умеренной размерности, хотя вычисления в общем случае могут быть весьма длинными.

В распространенном случае, когда m = 2, где е > 4, изложенные выше условия приводят к единственному требованию: а = 3 или 5 (по модулю 8). В этой ситуации четвертая часть всех возможных множителей даст длину периода, равную т/4, а т/4 будет максимальной длиной периода, когда с = 0.

Существует второй, еще более распространенный случай, когда m = 10*. Используя леммы Р и Q, нетрудно получить необходимые и достаточные условия достижения максимального периода для десятичного компьютера (см. упр. 18).

Теорема D. Если тп = 10, е > 5, с = О и Хо не кратно 2 или 5, то период линейноП конгруэнтной последовательности равен 5 х 10*~ тогда и только тогда, когда а mod 200 равно одному in следующих 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.

УПРАЖНЕНИЯ

1. [10] Чему равна длина периода линейной конгруэнтной последовательности с параметрами Ло = 5772156648, о = 3141592621, с = 2718281829 и m = 10000000000?

2. [10] Будут ли следующие два условия гарантировать максимальную длину периода, когда тп является степенью 2? (i) с - нечетное число; (ii) о mod 4 = 1.

3. [13] Предположим, что т = 10", где е > 2, и пусть с - нечетное число, не кратное 5. Покажите, что линейная конгруэнтная последовательность будет иметь период макси-мальной ДЛИНЫ loi да и только тогда, когда а mod 20 = 1.

4. [М20] Предположим, что т = 2 и Хо = О. Если числа а и с удовлетворяют условиям теоремы А, чему равно Xj.-i?

5. [и] Найдите все множители а, удовлетворяющие условиям теоремы А, когда m =

2 + 1. (Простые множители тп можно найти в табл. 3.2.1.1-1.)

► 6. [20] Найдите все множители а, удовлетворяющие условиям теоремы А, когда т = 10® - 1 (см. табл. 3.2.1.1-1).

► 7. [MS3] Период конгруэнтной последовательности не должен начинаться с Хо, но всегда можно найти индексы > О и А > О, такие, что А„+л = Хп при всех п > ц, и для которых /и и А являются наименьшими возможными значениями с этими свойствами (см. упр. 3.1-6 и 3.2.1-1). Если fij и Aj - индексы, соответствующие последовательностям

(Хо modру, а mod р, с mod р, р),

и если/1 и А соответствуют составной последовательности {Хо,а,с,р\... р), то согласно формулировке леммы Q А является наименьшим общим кратным Ai,..., Af. Чему равно значение р, в терминах значений /ii,... ,;(? Чему равно максимально возможное значение fi, получаемое путем варьирования Хо, о и с, когда ш = ... pi фиксировано?

8. [М20] Покажите, что если о mod 4 = 3, то (о 1)/(о -1) = О (по модулю 2), когда е > 1. (Воспользуйтесь леммой Р.)

► 9. [М22] (В. Э. Томсон (W. Е. Thomson).) Когда с = О и m = 2 > 16, теоремы В и С утверждают, что период имеет длину 2~ тогда и только тогда, когда множитель о удовлетворяет равенствам о mod 8 = 3 или о mod 8 = 5. Покажите, что каждая такая последовательность, по существу, является линейной конгруэнтной последовательностью с т = 2~, имеющей полный период, в следующем смысле:

a) если X„+i = {Ас + \ )Хп mod 2 и Хп = 4У„ + 1, то

Уп+1 = ((4с + 1)Уп + с) mod 2-;

b) еслиХп+1 =(4c-l)X„mod2" и Хп = ((-1)"(4У„ + 1)) mod 2% то

Уп+1 = ((1-4с)Уп - с) mod2-

[Замечание. В этих формулах с есть нечетное целое число. В литературе содержится достаточно утверждений о том, что последовательности с с = О, удовлетворяющие теореме В, так или-иначе являются более случайными, чем последовательности, удовлетворяющие условиям теоремы А, вопреки тому факту, что период - это только четверть длины периода, получаемого в условиях теоремы В. В данном упражнении такие утверждения опровергаются; в сущности, следует удалить два разряда длины слова, чтобы сохранить возможность прибавить с, когда т будет степенью 2.]

10. [М21] Для каких значений m справедливо А(т) = (т)?

► 11. [М25] Пусть X - нечетное целое число, большее, чем 1. (а) Покажите, что существует единственное целое число / > 1, такое, что х = 2- ± 1 (по модулю 2+). (Ъ) Дано, что 1<х<2 - 1и что / является соответствующим целым числом п. (а). Покажите, что порядок X по модулю 2 равен 2~. (с) В частности, это доказывает утверждения (i)-(iv) теоремы С.

12. Пусть р - простое нечетное число. Если е > 1, докажите, что о является первообразным элементом по модулю р тогда и только тогда, когда а - первообразный элемент по модулю р и а""" ф 1 (по модулю р). (Предположите, что \{р) - р~{р - 1). Этот факт доказан в упр. 14 и 16 ниже.)

13. [М22] Пусть р - простое число. Задано, что о не является первообразным элементом по модулю р. Покажите, что каждое о кратно р или о" = 1 (по модулю р) для некоторых простых чисел q, делящих р - I.

14. [Ml 8] Предположим, что е > 1, р - нечетное простое число и о - первообразный элемент по модуж> р. Докажите, что либо а, либо а + р является первообразным элементом по модулю р*. [Указание. См. упр. 12.]

15. [М29] (а) Пусть oi и 02 взаимно просты с m и пусть их порядки по модулю m равны соответственно Ai и А2. Предположим, что А является наименьшим общим кратным Ai и А2. Докажите, что аа имеют порядок А по модулю m для соответствующих целых чисел «1 и «2- [Указание. Рассмотрите сначала случай, когда Ai и А2 - взаимно простые числа.) (Ь) ПуЬть А(т) - максимальный порядок любого элемента по модулю т. Докажите, что А(т) кратно порядку каждого элемента по модулю т, т. е. что о" = 1 (по модулю т) всегда, когда а и т - взаимно простые числа. (Не используйте теорему В.)

► 16. [М24] {Существование первообразных корней.) Пусть р - простое число.

а) Рассмотрим полином /(ж) = х" -t- cix"" -t- • -t- с„, где а - целые числа. Дано, что о - целое число, для которого /(о) = О (по модулю р). Покажите, что существует полином

q{x) = х"- -t- gix"- + • -t- gn-i

с целыми коэффициентами, такой, что /(х) = (х - a)q{x) (по модулю р) для всех целых x.