AOP_Tom2 (1021737), страница 31
Текст из файла (страница 31)
Покажите.,что линейная конгруэнтная последовательность будет иметь период максиыяльной длины ил да и только тогда, когда и п4од 20 = 1 4. [М20] Предполоясим, что эп = 2' и Хэ = О. Если числа а и г удовлетворяют условиям теоремы А, чему равно Хэ. 5. [(Д найдите все множители а, улоялетяорявщие условияы теоремы л, когда гп = 2м + 1. (Простые множители т можно найти в табл. 3.2.1.1-1.) 6.
[20) Найдите все множители а, удовлетворяющие условиям теоремы А, когда т = 10' — 1 ( . 6 . 3.23 1-Ц. 7. [мЯУ) период конгруэнтной последовательности пе должен начинаться с ха, но всегда можно найти индексы и > 0 и Л > О, такие, что Л'„.~л = Л„при всех п > и, и для которых р и Л являются наименьшими возможными значениями с этими свойствами (см. упр. 3.1-6 и 3.2.1 — 1). Если р, н Лэ — индексы, соответствующие последовательностям (Ха щось р", а шо6р,', с шо6р"., р.'), и если и н Л соответствуют составной последовательности (Ха, а, с, р",... р' ), то согласно формулировке леммы С1 Л является наименьшим общим кратным Лп..., Ль Чему равно значение и в терминах значений рп, Ю? Чему равно максимально возможное значение и, получаемое путем варьирования Лщ а и с, когда тп = р",...
р" ,фиксировано? 2' 8. [МЯО) Покажите, что если ашо64 = 3, то (а~ — 1)/(а — 1) гя 0 (по модулю 2'), когда е > 1. (Воспользуйтесь леммой Р.) 9. [Мйй[ (В, Э. Томсон (ЪЧ, Е. ТЬопшоп),) Когда с = О и т = 2' > 16, теоремы В и С утверждают, что период имеет д,чину 2' э тогда и только тогда> когда множитель а удовлетворяет равенствам а шоб8 = 3 или о гпос18 = 5. Покажите, что каждая такая последовательность, по существу, является линейной конгруэнтной последовательностью с т = 2' ~, имеющей полный период, в следующем смысле: а) если Х„ы = (4с+ 1)Х„шоб 2' н Х„= 4У + 1, то У„е~ — ((4с+ 1)У„+ с) шоб 2' Ь) если Х ь~ = (4с — 1)Х„шоб 2' и Х„= ((-1)" (41'„+ 1)) шоб 2', то У э.~ = ((1 — 4с)1' — с) шоб 2' [Замечание. В этик форыулах с есть нечетное целое число.
В литературе содержится достаточно утверждений о том, что последовательности с с = О, удовлетворяющие теореме В, так илге иначе являются более случайными, чем последовательности, удовлетворяющие условиям теоремы А, вопреки тому факту, что период — зто только четверть длины периода, получаемого в условиях теоремы В.
В данном упражнении такие утверждения опровергаются, в сущности, следует удалить два разряда длины слова, чтобы сохранить возможность прибавить с, когда т будет степенью 2.[ 10. [М01[ Для каких значений тп справедливо Л(т) = ш(ш)1 ь 11. [М28) Пусть х — — нечетное целое число, большее, чем 1. (а) Покажите, что существует единственное целое число у > 1, такое, что к э— з 21 х 1 (по модулю 2г+'). (Ь) Дано, что 1 < х < 2' — 1 и что 1 является соотнетствующнм целым числом п. (а). Покюките, что порядок к по модулю 2' равен 2' г.
(с) В частности, это доказывает утверждения В)- (!г) теоремы С. 12. [Мйб) Пусть р — простое нечетное число. Если е > 1, докажите, что а является первообразным элементом по модулю р' тогда и только тогда, когда а — первообразный элемент по модулю р и а" ' ж 1 (по модулю рэ). (Предположите, что Л(р') = р' '(р — 1).
Этот факт доказан в упр. 14 и 16 ниже.) 13. [Мйй[ Пусть р — простое число. Задано, что а не является первообразным элементом по модулю р. Покажите, что каждое а кратно р или а~""П~э ш 1 (по лгодулю р) для некоторых простых чисел «, делящих р — 1, 14.
[М18[ Предположим, что е > 1, р --- нечетное простое число и а — первообрвзный элемент по молушо р. Докажите, что либо а, либо а« р является первообраэным элементом по модулю р'. [Укаэонпе. См. упр. 12.[ 16. [МЯ«[ (а) Пусть а~ и аг взаимно просты с ш и пусть их порядки по модулю пз равны соответственно Л~ и Лз.
Предположим, что Л является наименьшим общим кратным Л~ и Лш Докажите, что а" ,а"' имеют порядок Л по модулю гл для соответствующих целых чисел н~ и кш [Указание. Рассмотрите сначала случай, когда Л~ и Лэ — взаимно простые числа.) (Ь) П11ть Л(т) — максимальный порядок любого элемента по модулю ьч Докажите, что Л(т) кратно порядку каждого элемента по модулю т, т е. что а"пы ш 1 (по модулю т) всегда, когда а н т — взаимно простые числа. (Не используйте теорему В.) э' 16. [М24 [ (Существование переообразнмх корней.) Пусть р — простое число. а) Рассмотрим полипом /(я) = х" +с~х" '+ +с„, где с, — целые числа.
Дано, что а — целое число, для которого 1(а) = О (по модулю р). Покажите, что существует полипом «(х) = з" ' «- « х" ' + " + «. с целыми коэффициентами, такой, что 1(х) = (х — а)«(х) (по модулю р) для всех целых х. 3.2.1.3. Потенциал. В предыдущем разделе было показано, что максимальный период может быть достигнут, когда 6 = а — 1 кратно каждому простому делителю т, и 6 должно быть также кратно 4, если т кратно 4. Если х — основание системы счисления машины (х = 2 для бинарного компьютера и х = 10 для десятичного компьютера), тл — длина слова в компьютере х', множитель а=в~+1, 2</с<с, (1) удовлетворяет этим условиям. По теореме 3.2.1.2А можно брать с = 1.
Рекуррент- ное соотношение теперь имеет вид Х„вг = ((хе+ 1)Х„+ 1) шейх', (2) и это уравнение означает, что можно избежать умножения; просто достаточно перемещения и суммирования. Например, пусть и = Вт+1, где  — — размер байта компьютера И11. Программа (3) ЬОА Х; ЯЬА 2; А00 Х; 1ИСА 1 Ь) Пусть /(х) -- такай же полинам., как в (а). Покажите, что г'(х) имеет не более п различных "корней" по модулю р, т. е. существует не более н целых чисел а, 0 < а < р, таких, что 1(а) гя О (по модулю р). с) Так же, как и в упр. 15, (Ь), полинам у(х) = хыв1 — 1 имеет р — 1 различных корней; следовательно, существует целое число а с порядком р — 1, 1т. [Мйб] Не все значения, перечисленные в теореме 11, можно получить, используя построения, приведенные в разделе, например 11 — не первообразный элемент по модулю 5', Как это возможно, если 11 является первообразным элементам по модулю 10' согласно теореме Р? Какие из чисел, перечисленных в теореме 11, являются одновременно первообразными элементами по модулям 2' и 5'1 13.
[М25] Докажите теорему 11 (см. предыдущее упражнение). 19. [40] Составьте таблицу нескольких подходящих множителей а для каждого нз значений т, внесенных в табл. 3.2.1.1-1, предполагая, что с = О. ь 20. [М24] (Дж. Марсалья (С. Магваб11а).) Назначение упражнения состоит в изучении длины периода произвольной линейной конгруэнтной последовательности. Пусть 1;, = 1 + а + + а" ', так что Х„= (А1' + Хо) шоб т для некоторой константы А из условия 3.2.1-(8).
а) Докажите, что длина периода (Х ) равна длине периода (У„шов(т ), когда т~ = т/бсв)(А, т). Ь) Докажите, что длина периода (У„шеар') удовлетворяет следующим требованиям, когда р — простое число. (1) Если а шос1р = О, длина периода равна 1. (0) Если а шоб р = 1, она равна р', за исключением случаев, когда р = 2, е > 2 и а глоб 4 = 3. (ш) Если р = 2, е > 2 и а шоб 4 = 3, она равна удвоенному порядку а по модулю р' (см. упр. 11), за исключением случая, когда а ге — 1 (по модулю 2"), при котором она ранна 2. (1в) Если а шог( р > 1, длина периода равна порядку а по мозулю р' 21.
[М25] Пусть в линейной конгруэнтной последовательности с максимальным периодом Хе = О в — наименьшее положительное целое число, такое, что а* гн 1 (по модулю т). Докажите, что йсб(Х„т) = в (йсв1 — — наибольший общий делитель. — Прим. перев.). ь 22. [М25] Обсудите проблему нахождения модулей т = 6~ х 6' х 1 таким образом, чтобы генераторы, использующие вычитание с заимствованием и суммирование с переносом (см. упр 3.2.1.1-14), имели очень длинные периоды, (4) 6' = О (по модулю т). (Целое число э всегда существует, когда множитель удовлетворяет условиям теоремы 3.2.1.2А, так квк Ь кратно каждому простому делителю т,) Можно анализировать случайность последовательности, положив Ле — — О, так как О встречается в периоде.
При этом предположении соотношение 3.2,1 — (6) сводится к Х„= ((а" — 1)с/6) пюб тп; и, если разложить выражение а" — 1 = (6 + 1)" — 1 по бнномиальной формуле,. получится Х„= с(п+ ( ) 6+ + ( ) Ь' ') шобт. (5) Все члены разложения Ь', 6'+' и т.
д. можно исключить, так как они кратны т. Уравнение (5) столь поучительно, что необходимо рассмотреть некоторые специальные случаи. Если а = 1, потенциал равен 1 н Л„:— сп (по модулю т), как мы уже видели, так что последовательность наверняка не случайна. Если потенциал равен 2, то Л'„= си+ сЬ(",), и снова последовательность не совсем случайна. Действительно, в этом случае Х„+1 — Х„: — с + сьп. Таким образом, разность между последовательно генерируемыми числами выраже- на простой зависимостью от и. Точка (Л'„, Хь~ы Х„+э) всегда лежит на одной из четырех плоскостей в трехмерном пространстве: х — 2у+л = Н вЂ” т, х — 2у+2=а — 2т, х — 2у+г = Н+т, х — 2у+х = Н, где И = сЬ шод т. Если потенциал равен 3, то последовательность становится более или менее похожей па случайную, но все еще существует высокая степень зависимости между Х„, Л в ы и Л„+э.
Тесты показывает, что последовательности с потенциалом 3 по- прежнему недостаточно хороши. Сообщалось, что приемлемые результаты были получены в некоторых случаях при потенциале, равном 4, но это оспаривалось может использоваться вместо программы, приведенной в разделе 3.2.1.1, и время выполнения программы уменьшается от 1бп до 7и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
