является делителем г""-". (с) 1 имеет порядок 1; 2* - 1 - порядок 2; максимальный период, гдее > 3, равен, следовательно, 2*", и для е > 4 необходимо, чтобы / = 2, т. е. а; = 4 ± 1 (по модулю 8).

12. Если к - делитель р - 1 и если а* = 1 (по модулю р), то по лемме Р а* = 1 (по модулю р*). Аналогично, если а" = 1 (по модулю р), находим, что а" = 1 (по модулю р). Таким образом, в данных случаях а не является первообразным элементом. Обратно, если а*" ф 1 (по модулю р), то по теореме 1.2.4F и лемме Р имеем, что а""" ф 1 (по модулю р"), но а-~° = 1 (по модулю р). Поэтому порядок является делителем (р - 1)"", но не (р - следовательно, он имеет вид кр", где к делит р - 1. Но, если а является первообразным элементом по модулю р, конгруэнтность а = а = 1 (по модулю р) влечет к = р - I.

13. Предположим, amodp / О, и пусть А - порядок а по модулю р. По теореме 1.2.4F А является делителем р - 1. Если А < р - 1, то g имеет простой множитель (р - 1)/А.

14. Пусть 0<к <р. Если а" = 1 (по модулю р), то (а + kpf = а" + {р - 1)а~кр (по модулю р) и это выражение 1, так как (р - 1)а"А; не кратно р. Из упр. 12 следует, что а + кр - первообразный элемент по модулю р.

15. (а) Если Al = рр ... р и Аг = р{... р{, положим щ = р*... pf и кг = Pi .. • Pt, где

9j = ej и hj =0, если Cj < fj, Qj =0 a hj = fj, если ej > fj.

Тогда a" и имеют взаимно простые периоды Ai/ki и Аг/кг соответственно. К тому же (Ai/ki)(A2/«2) = А. Таким образом, достаточно рассмотреть случай, когда Ai и Аг - взаимно простые числа, т. е. когда Л = А1Л2. Теперь, поскольку (0102) = 1, получаем 1 = (ахаг) = aj; отсюда следует, что AAi кратно Аг. Это влечет, что А кратно Аг, так как Al и Аг - взаимно простые числа. Аналогично А кратно Ai; значит, Л кратно А1А2. Очевидно, что (0102) = 1; таким образом, А = Л1А2.

(Ь) Если ai имеет порядок А(т), аг - порядок А, из (а) следует, что А(т) кратно Л. С другой стороны, можно найти элемент более высокого порядка, а именно - порядка lcm(A,A(m)).

16. (а) fix) = {х- а)(х"- + (а + ci)x"-2 + ... + (а"" + • • • + c„-i)) + /(а).

(Ь) Утверждение очевидно, когда п = 0. Если о является корнем, то f{x) = {x - a)q{x); поэтому, если а - какой-нибудь другой корень, то

0 = /(а) = (а-а)д(а).

Поскольку а - а не кратно р, то а должно быть корнем q{x). Итак, если f{x) имеет более п различных корней, то q(x) имеет более п-1 различных корней, (с) А(р) > р - 1, так как /(х) должен иметь степень > р - 1 для того, чтобы иметь так много корней. Но по теореме 1.2.4F А(р) < р - 1.

17. Согласно лемме Р 11 = 1 (по модулю 25), ф 1 (по модулю 125), и т. д.; таким образом, порядок 11 есть 5"" (по модулю 5). Однако максимальное значение А(5) = 4 • 5". Но согласно лемме Q общая длина периода является наименьшим общим кратным периода по модулю 2* (а именно - 2"), периода по модулю 5* (а именно - 5*") и равна 2e-2gE-i Л(10). Период по модулю 5* может быть равен 5~ или 2 • 5°~, или 4 • 5"", не влияя на длину периода по модулю Ю, так как найдено наименьшее общее кратное. Значения первообразных элементов по модулю 5* сравнимы с 2, 3, 8, 12, 13, 17, 22, 23 по модулю 25 (см. упр. 12), а именно - 3, 13, 27, 37, 53, 67, 77, 83, 117, 123, 133, 147, 163, 173, 1S7. 197.

18. В соответствии с теоремой С а mod 8 даижно быть равно 3 или 5. Знание периода а по модулю 5 и модулю 25 позволяет применить лемму Р, чтобы определить допустимые значения а mod 25. Период = 4 • 5": 2, 3, 8, 12, 13, 17, 22, 23; период = 2-5"; 4, 9, 14, 19; период = 6, 11, 16, 21. Каждое из этих 16 значений дает одно значение а, О < а < 200, такое, что о mod 8 = 3, и другое значение а, такое, что а mod 8 = 5.

19. Некоторые примеры можно найти в строках 17-20 табл. 33.4-1.

20. (а) AY„ + Хо = АУп+к + Хо (по модулю т) тогда и только тогда, когда Yn = Yn+k (по модулю т). (Ь) (i) Очевидно, (ii) Теорема А. (iii) (а" - 1)/(а - 1) = О (по модулю 2) тогда и только тогда, когда а" = 1 (по модулю 2"*"); если а ф -1, порядок а по модулю 2+1 равен удвоенному порядку по модулю 2. (iv) (о" - 1)/(а - 1) = О (по модулю р") тогда и только тогда, когда а" = 1.

21. Хп+а S Ап + Xs, согласно равенству 3.2.1-(6), и s является делителем т, так как s - степень р, когда m - степень р. Следовательно, заданное целое число q кратно mjs тогда и только тогда, когда А,» = О, а g кратно m/gcd(.y5, m).

22. Алгоритм 4.5.4Р позволяет проверять за приемлемое время, будут ли числа вида m = Ь* ± Ь ± 1 простыми, когда, скажем, 6 и 2 и /< /с и 100. Вычисления могут производиться в Ь-ичной системе счисления, так как особый вид т содействует ускорению операции возведения в квадрат mod m. (Рассмотрим, например, возведение в квадрат mod 9999998999 в десятичной системе счисления.) Алгоритм 4.5.4Р следует, конечно, использовать только тогда, когда известно, что m не имеет малых делителей.

Марсалья и Заман {Annals of Applied Probability 1 (1991), 474-475] показали, что т = b* - b + 1 является простым числом с первообразным корнем Ь, когда b равно простому числу 2-5. Разложение на множители т-1 = b{b-l){b+b+b+b+b+b+l){b+b+l) требуется для того, чтобы установить первообразность 6; один из 17 простых множителей тп - 1 имеет 99 десятичных цифр. В результате можно быть уверенным, что последовательность Хп = (Хп-22-2:п-43-Сп) modb = х„ 22-Хп 4з-с„-1-Ьс„+1 имеет период длиной m - 1 г; Ю для каждого ненулевого выбора начальных значений О < X-i,... ,х 4з < Ь, когда Со = 0.

Тем не менее 43 является, скорее всего, малым значением к с точки зрения шагового критерия "день рождения" (см. раздел 3.3.2J) и 22 примерно равно 43/2. Рассмотрев "смесь", можно прийти к выводу, что мы предпочитаем значения к и I, для которых несколько первых частичных отношений в цепной дроби 1/к малы. Чтобы избежать возможных проблем с этим генератором, Люшером (Liischer) была предложена хорошая идея - отбросить несколько чисел (см. раздел 3.2.2).

Здесь приведено несколько простых чисел вида ± Ь ± 1, удовлетворяющих ограничению 6 = 2 и 50 < /с < 100. Для вычитания с заимствованием: Ь" - - 1, 6 - 6 - 1,

Ь«6 J62 J88 J52 J95 j61 j58 j33 62 jl7 j69 24 70 ,57

687 j24 J д суммирования С переносом: -1, б" -f-b* -1, ЬЧь" -1, b°+b -1.

(Неподходящие с точки зрения "смеси" простые числа: b~b-l, b -b-1, b -b" -1,

66 jl5 i j84 j26 j90 j42 j93 jl8 j52 j8 60 jl2 j67 ftS + 1 j63 i j83 jl4 1. j65 76 ,11 j88 30 92 ,48

Для вычисления периода гюлученной последовательности необходимо знать множители m - 1, но это неосуществимо для таких больщих чисел (разве что нам крайне повезет). Предположим, что удалось найти простые множители gi,..., qt; тогда вероятность, что 6*"-mod m = 1, является крайне малой, только 1/q, за исключением очень малых простых q. Следовательно, .можно быть совершенно уверенным, что период Ь" mod т является очень длинным, несмотря на то что множитель т - 1 неизвестен.

Действительно, период является почти безусловно очень длинным, даже если т - не простое число. Рассмотрим, например, случай для /с = 10, / = 3, 6 = 10 (кото-

рый мало подходит для генерирования случайных чисел, но значения к, I и b настолько малы, что можно получить точные результаты). (10" modm) имеет период длиной 1ст(219,11389520) = 2494304880, где т = 9999998999 = 439-22779041; 4999999500, где т = 9999999001; 5000000499, где т = 10000000999; 1ст(1,16,2686,12162) = 130668528, где т = 10000001001 = 3 • 17 • 2687 • 72973. Некоторые редко встречающиеся наборы начальных значений могут сократить период, когда т - не простое число. Но можно быть твердо уверенным в получении хорошего результата, если выбрать, скажем, к = 1000, / = 619иЬ = 21

РАЗДЕЛ 3.2.1.3

1. с = 1иВ - всегда взаимно простые числа, и каждый простой делитель т = является делителем В. Таким образом, по крайней мере квадрат этого делителя делит число b = В.

2. Только 3. Таким образом, генератор не рекомендуется, несмотря на его длинный период.

3. Потенциал равен 18 в обоих случаях (см. следующее упражнение).

4. Так как из того, что а mod 4 = 1, следует, что о mod 8 = 1 или 5, получаем b mod 8 = 0 или 4. Если b кратно 4, но не кратно 8, а bi кратно 8, ясно, что Ь = О (по модулю 2)* влечет bf = О (по модулю 2). Таким образом, Ь\ не может иметь потенциал, выше Ь.

5. Потенциал равен наименьшему из значений s, таких, что fjS > ej для всех j.

6. Модуль должен делиться на 2 или на р (для нечетных простых р) для того, чтобы потенциал был равен 4. Такими будут только величины m = 2 -I-1 и 10 - 1.

7. о = (l-b-f-Ь----) modm, где члены b,b и т. д. опускаются (если s - потенциал).

8. Так как Хп всегда нечетно,

Хп+2 = (2 -f- 3 • 2* -I- 9)Хп mod 2 = (2 -f- 6X„+i - 9Х„) mod 2. Если даны Yn и F„+i, то возможности для

Yn+2 « (5 + 6(Г„+1 + е,) - 9(Г„ + ег)) mod 10,

О < ei < 1 и О < 62 < 1, ограничены и неслучайны.

Замечание. Если множители, предложенные в упр. 3, были бы, скажем, равны 233 + 2 -I- 1, а не 2 + 2 -1-2-1-1, можно было бы аналогично показать, что Хп+2-WXn+i +25Хп = constant (по модулю 2). Вообще говоря, a±S не должно делиться на высокие степени 2, когда S малб. В противном случае получится "несостоятельность второго порядка". Более подробно этот вопрос обсуждается в разделе 3.3.4.

Генератор из этого упражнения рассматривался в работе Мак-Ларена и Марсалья (MacLaren, Marsaglia, JACM 12 (1965), 83-89). Недостатки таких генераторов , впервые были продемонстрированы М. Гринбергером (М. Greenberger), САСМ 8 (1965), 177-179). Даже через десять лет после появления этой работы подобные генераторы широко использовались (см. обсуждение RANDU в разделе 3.3.4).

РАЗДЕЛ 3.2.2

1. Метод следует применять с большой осторожностью. Прежде всего, aUn, вероятно, будет настолько большим, что добавлять с/т не имеет смысла, и операции по "mod 1" почти уничтожат любые следы оставшихся от добавления значений. Мы заключаем, что необходимо использовать арифметические операции с плавающей запятой с двойной точностью. Даже с двойной точностью нужна уверенность, что нет округления и т. д., иначе последовательность чисел будет вести себя совершенно по-другому, так как нарушатся теоретические основы хорошего поведения последовательности (но см. упр. 23).