AOP_Tom2 (1021737), страница 166
Текст из файла (страница 166)
8. Легко видетгч что аг из 1 (по модулю 8) и а ев 1 (по модулю 16), а г— в 1 (по модулю 32) и т. д. Если а шо64 = 3, то а — 1 —.- удвоенное нечетное число. Таким образом, г'-' -1 (а~ — 1)/(а — 1) ед 0 (по модулю 2') тогда н только тогда, когда (аг — ))/2 ш 0 (по модулю 2'е'/2), что справедливо. 9. Представить выражение для Х„в терминах Ул и упростить его Если Хо по леодулю (шод) 4 = 3, формулы из упражнения неприменимы; однако, они применимы к поеледовательности Я„= (-Х„) шод 2", которая, по существу, ведет себя так же. 10. Только для т = 1, 2, 4, р' н 2р', для нечетных простых р.
Во всех других случаях результат теоремы В является усоверепенствованным вариантом теоремы Эйлера (упр. 1.2.4-28) 11. (а) Каждое число х+ 1 или х — 1 (но не оба) кратно 4. Таким образом, х ~ 1 = 42?, где д — нечетное число и / > 1. (Ь) При данных обстоятельствах / С е н, значит, с > 3.
Получим хх ш 1 (по модулю 2~) и *х ж 1 (по мо;гулю 2ет') и / > 1. Отсюда, -г-! е г*-г применяя лемму Р, находим, что (хх) Ю 1 (по модулю 2'), тогда как х * г' (хх) ш 1 (по модулю 2'). Таким образом, порядок является делителем 2' ?, но не является делителем 2' 7 '. (с) 1 имеет порядок 1: '2' — 1 — порядок 2; максимальный период, где е > 3, равен, следовательно, 2' е, и для г > 4 необходимо, чтобы / = 2, т е. х = 4 х 1 (по модулю 8).
ьр'-' 12. Егли Й вЂ” делитель р — 1 и если о" ш 1 (по модулю р), то по лемме Р аге = 1 (по модулю р'). Аналогично, если аг = 1 (по модулю р ), находим, что аы " = 1 г-' 2 Ш-Ое' (по модулю р'). Таким образом. в данных случаях а не яиляется первообразным элементом. Обратно, егли ог ' ф 1 (по модулю ре), то по теореме 1.2.4Р и лемме Р имеем, ш-пг' ' «-1 что аш ы ~ 1 (по модулю р'), но ош гш = 1 (по модулю р"). поэтому порядок является делителем (р — 1)р', но не (р — 1)р' ~; следовательно, он имеет вид йр', где й делит р — 1 Но, если а является первообразным элементом по модулю р, конгруэнтность -1 аге = а = 1 (по модулю р) влечет й = р — 1.
13. Предположим, а шойр ф О, и пусть Л вЂ” порядок а по модулю р. По теореме 1.2.4Г Л является делителем р — 1. Есзи Л < р — 1, то д имеет прес~ой множитель (р — 1)/Л. 14. Пусть 0 < й < р. Егли о" ' = 1 (по модулю р~), то (а +Лр)" ' = аг ' + (р — 1)аг йр (по модулю р~) и зто выражение ф 1, так как (р — 1)о" ~я не кратно р. Из упр. 12 следует, что о + асср — первообрвзный элемент по модулю р'. 15. (а) Если Л1 =р" ,..р" ,и Лэ =р('.. р(', положим к~ =рэ1'...рн и кэ =р",'., р,"', где д, = ез и 16 = О, если е, < /м д, = О и )Ь =/„если е, >/,. Тогда а",' и аэ' имеют взаимно простые периоды Л1/к1 и Лз/кз соответственно.
К тому же (Л~/к1)(Лг/лз) = Л. Таким образом, достаточно рассмотреть случай, когда Л~ и Лев взаимно простые чигла, т, е. когда Л = ЛгЛю Теперь, поскольку (а~аз) гя 1, получаем А 1 = (а~аз)""' ш аз"', отсюда следует, что ЛЛ~ кратно Ль Это влечет, что Л кратно Лю так как Л| и Лэ — взаимно простые числа. Аналогично Л кратно ЛМ значит, Л кратно Л1Лщ Очевидно, что (а~ аз) ' ' = 1; таким образом, Л = Л1Ль л,х, (Ь) Если а~ имеет порядок Л(ш), аз — порядок Л, из (а) следует, что Л(т) кратно Л. С другой стороны, можно найти элемент более высокого порядка, а именно — порядка 1сш(Л, Л(т)).
16. (а) /(г) = (х — а)(х" '+ (о+с1)х" ~+ + (а" '+. +с«1)) + /(е). (Ь) Утверждение очевидно, когда и = О. Если а является корнем, то /(х) ш (х — а) д(х); поэтому, если а' — какой-нибудь другой корень, то 0 = /(о') вв (о' — а) д(о'), Поскольку а' — а не кратно р, то а' должно быть корнем д(х).
Итак, если /(х) имеет более л различных корней, то д(х) имеет более и — 1 различных корней. (с) Л(р) > р — 1, так как /(г) должен иметь степень > р — 1 для того, чтобы иметь так много корней. Но по теореме 1.2 4Г Л(р) < р — 1 17. Согласно лемме Р 11э = 1 (по модулю 25), 11 ф 1 (по модулю 125), и т. д.; таким образом, порядок 11 есть 5" ' (по модулю 5'). Однако максимальное значение Л(5') = 4 . 5' Но согласно лемме Я общая длина периода я1щяетсл нанменьшим общим кратным периода по модулю 2' (а именно — 2' ~), периода по модулю 5' (а именно — 5' ') и равна 2" 5" ' = Л(10') Период по модулю 5' может быть равен 5' ' или 2 5' ', или 4.
5' не влияя иа длину периода по модулю 10', так как найдено наименьшее общее кратное. Значения первообразных элементов по модулю 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. 187. 197. 18. В соответствии с теоремой С а щос) 8 должно быть равно 3 или 5. Знание периода а по модулю 5 и модулю 25 позволяет применить лемму Р, чтобы определить допустимые значения а шея) 25. Период = 4 5' '. 2, 3, 8, 12, 13, 17, 22, 23; период = 2 5' ': 4, 9, 14, 19; период = 5' ': б, 11, 1б, 21.
Каждое из этих 1б значений дает одно значение а, О < а < 200, такое, что а шея) 8 = 3, и другое значение а, такое, что а щод 8 = 5. 19. Некоторые примеры можно найти в строках 17-20 табл. 3.3.4-1. 20. (а) А1;, + Хо зэ АУ»ез + Хо (по модулю т) тогда и только тогда, когда Р„щ 1'„еь (по модулю т'). (Ь) (1) Очевидно. (8) Теорема А. (1п) (а" — 1)/(а — 1): — 0 (по модулю 2') тогда и только тогда, когда а" щ 1 (по иодулю 2'ь'); если а ~ — 1, порядок а по модулю 2444 ранен удвоенному порядку по модулю 2'.
(гк) (а" — 1)/(а — 1) = 0 (по модулю р') тогда и талы»о тогда, когда а" вз 1. 21. Х +, = Х + Х, согласно равенству 3.2.1-(б), и в является делителем т, так как в— степень р, когда т — степень р. Следовательно, заданное целое число д кратно т/ь тогда и только тогда, когда Х», гя О, а д кратно т/боя)(Х„ т). 22. Алгоритм 4.5.4Р позволяет проверять за приемлемое время, будут ли числа вида т = Ь х Ь х 1 простыми, когда, скажем, Ь 2 и 1 < 6 = 100. Вычисоения могут ь зг производиться в 6-ичной системе счисления, так как особый вид т содействует ускорению операции возведения в квадрат шод т. (Рассмотрим, например, возведение в квадрат шод 9999998999 в десятичной системе счисления.) Алгоритм 4.5 4Р следует, конечно, использовать только тогда, когда известно, что т не имеет палых делителей. Марсзлья и Заман (Апаа)в оу Арр11641 РгоЬвЬвббу 1 (1991), 474 .475) показали, что т = Ь вЂ” Ь + 1 является простым числом с первообрвзным корнем Ь, когда Ь равно простоиу яв и числу 2зг — 5.
Разложение на множители т-1 = Ьгг(Ь вЂ” 1)(Ь +Ь +64+6 +Ь +6+Ц(Ь 44-6 +1) требуется для того, чтобы установить первообразность Ь; один из 17 простых множителей »н — 1 имеет 99 десятичных цифр. В результате иожно быть уверенным, что ногледова- тЕЛЬНОСтЬ Хо = (Хь-и -Х -4З вЂ” С ) ШОС) Ь = Х -гг — Х„-»З — С„+ЬС„Ь1 ИМЕЕТ ПЕрнад;Ьгнпай т — 1 10 для каждого ненулевого выбора начальных зяачений О < х 1,...,х яз < Ь, 414 когда со = О.
Тем не менее 43 является, скорее всего, малым значением 6 с точки зрения шагового критерия "день рождения" (си. раздел 3.3.23) и 22 примерно равно 43/2. Рассмотрев "смесь', можно прийти х выводу, что мы предпочитаем значения )» и 1, для которых несколько первых частичных отношений в цепной дроби 1/й малы. Чтобы избежать возможных проблем с этим генератором, Люшером (Ьйзсйег) была предложена хорошая идея — отбросить несколько чисел (см.
раздел 3.2.2). Здесь приведено несколько простых чисел вида Ь х Ь х 1, удовлетворяющих ограни- 1» чению Ь = 2зг и 50 < 6 < 100. Для вычитания с заимствованием: Ьь» — Ь'г — 1, Ьгз — Ь'г — 1, Ьвь Ьы 1 Ьвв Ьы 1 Ьл Ьвь 1 Ььз Ьзз+ 1 Ьбг бы+1 Ьбв бы+ 1 6»о Ьь» +1 Ьь» — Ьгя+1. для суммирования с переносом. Ььб+Ьгг — 1, Ьб'+Ь»4 — 1, Ь»4+Ь㻠— 1, Ьво+Ьбь — 1. (Неподходящие с точки зрения "смеси" простые чисгза: Ь вЂ” Ьб — 1, Ььь -Ьзг — 1, Ьбь — Ььг — 1, 6»б 611 1 66Я Ьы 1 Ьво 6»г 1 Ьоз Ьщ 1 Ьы Ьв+ 1 Ьво 611+ 1 Ьвг 66+ 1 667 Ьбз 4 1 (зз 614 + 1 Ьбь + Ьг 1 616 611 1 166 4 Ьзо 1 Ьог 646 Для вычиг тенин периода полученной последовательности необходимо знать множители т — 1, но это неосуществимо длн таких больших чисел (разве что нам крайне повезет).
Предположим, что удалось найти простые множители 91,..., 91; тогда вероятностгн что Ьн" '11» шоб) т = 1, является крайне малой, только 1/д, за исключением очень малых простых 9. Следояательно, можно быть совершенно уверенным, что период Ь" щоя) т является очень длинным, несмотря на то что множитель т — 1 неизвестен.
Действительно, период является почти безусловно очень длинным, даже если т— не простое число. Рассмотрим, например, случай для й = 10, ! = 3, Ь = 10 (кото- рый мало подходит для генерирования случайных чисел, но значения Ь, 1 и Ь настолько малы, что можно получить точные результаты). (10" то|1 т) имеет период длиной 1с|п(219,11389520) = 2494304880, где т = 9999998999 = 439 . 2277Я041; 499999Я500, где |л = 9999999001; 5000000499, где т = 10000000999; 1сп|(1,16,2686,12162) = 130668528, где и| = 10000001001 ш 3 17 2687 72973. Некоторые редко встречающиеся наборы начальных значений могут сократить период, когда |л — не простое число. Но можно быть твердо уверенным а получении хорошего результата, если выбрать, скажем, Ь = 1000, 1 = 619 и Ь = 2'в.
РАЗДЕЛ 3.2.1.3 1. с = 1 и  — всегда взаимно простые числа, н каждый простой делитель т = В в в является делителем В. Таким образои, по крайней мере квадрат этого делителя делит число Ь = В|. 2. Только 3. Таким образом, генератор ие рекозеендтется, несмотря на его длинный период. 3. Потенциал равен 18 в обоих случаях (см. следующее упражнение). 4. Так как из того, что а то|1 4 = 1, следует, что а шоб 8 = 1 или 5, получаем Ь |поб 8 = 0 или 4. Если Ь кратно 4, но не кратно 8, а Ь| кратно 8, ясно, что Ь' = 0 (по мо,гулю 2)' влечет Ье| = 0 (по модулю 2)'. Таким образом, Ь| не может иметь потенциал, выше Ь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
