AOP_Tom2 (1021737), страница 30

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 30)

Так как Л„= Х„+х для всех достаточно больших и, 1'„= У„+х (следовательно, Л кратно Л~) и У„= Я„э.х (следовательно, Л кратно Лэ). Таким образом, получим, что Л > Л'. Более того, известно, что У„= У„+х и о„= Е„+х для всех достаточно больших и; поэтому из (4) следует, что Х„= Х„.~х . Это доказывает, что Л < Л'. 1 Сейчас мы готовы доказать теорему А. Из леммы Я следует, что теорему достаточно доказать для случая, когда т является степенью простого числа, поскольку р",...

р," = Л = 1сш(Лы..., Л!) < Лд... Лс < р",... р Л'„= ( ) с шос1т. (5) Если с и т не взаимно простые числа, то значение Л'„никогда не может быть равно 1. Следовательно, условие (1) теоремы необходимо. Период имеет длину т тогда и только тогда, когда наименьшее положительное значение и, для которого Х„= Хо = О, равняется и = гп. Из (5) и условия (1)'следует, что доказательство нашей теоремы сводится к доказательству следующего утверждения. Лемма К. Предположим, что 1 < а < р', где р — простое число. Еглн Л вЂ” наимень- шее целое положительное число, для которого (а — 1)/(а — 1) = О (по модулю р'), то ( а эз 1 (по модулю р), Л = р' тогда и только тогда, когда ( а ь— з 1 (по модулю 4), где р>2, где р= 2.

Доказательство. Предположим, что Л = р'. Если а р( 1 (по модулю р), то (а" — 1)/(а — 1) = О (по модулю р') тогда и только тогда, когда а" — 1 = О (по модулю р'). Значит, условие аг — 1 ин О (по модулю р') влечет равенство аг' = 1 (по модулю р), но из теоремы 1.2.4г следует, что ая': — а (по модулю р). Таким образом, предположение, что а ф 1 (по модулю р), приводит к противоречию.

Если р = 2 и а = 3 (по модулю 4), то из упр. 8 следует (аэ — 1)/(а — 1) = О (по модулю 2'). Эти рассуждения показывают, что в большинстве случаев необходимо, чтобы а = 1+ дру, где ру > 2 и д не кратны р, всякий раз, когда Л = р'. (1сш — наименьшее общее кратное. — Прим. перев.) выполняется тогда и только тогда, когда Л = р у для 1 < у < 1. Предположим поэтому, что т = р', где р — простое число, а е — целое положительное число. Поскольку утверждение теоремы очевидно при а = 1, люжно считать, что а > 1.

Период может иметь длину гп тогда и только тогда, когда каждое целое число я, такое, что О < х < т, встречается в этом периоде. Действительно, никакое значение я в периоде не может встретиться более одного раза. Таким образом, период имеет длину т тогда и только тогда, когда период последовательности с начальным значением Ло = О имеет период длиной т, Поэтому достаточно доказать теорему, когда Хо = О.

Из формулы 3.2.1-(6) следует, что Остается показать, что это условие достлаточно для того, чтобы Л = р'. Применив лемму Р, находим, что для всех д > О а» = 1 (по модулю р7»), а" ф 1 (по модулю р~ »~~); следовательно, (а" — 1)/(а — 1) = О (по модулю р»), (а" — 1)/(а — 1) ~ О (по модулю р»+'). (6) В частности, (໠— 1)/(а — 1) аз О (по модулю р').

Сейчас для конгруэнтной последовательности, определяемой параметрами (О,а,1,р') Л'„, справедливо Л„= (а" — 1)/(а — 1) шо»1р'. Значит, ее период равен Л, т. е. Х„= О тогда и только тогда, когда и кратно Л. Следовательно, р' кратно Л. Это может случиться, только если Л = р» для 'некоторых д и соотношения (6) означают, что Л = р'. ! Итак, теорема А доказана. $ В завершение этого раздела рассмотрим специальный случай использования исключительно мультипликативных генераторов, когда с = О. Несмотря на то что процесс генерирования случайных чисел является немного более быстрым в данном случае, теорема А показывает, что максимальный период не может быть достигнут. Действительно, это совершенно очевидно, так как последовательность удовлетворяет соотношению (7) Хв ы — — аХ„шо»( т а" = 1 (по модулю р' 7).

(8) По теореме Эйлера (упр. 1.2.4 — 28) а~(» > ш 1 (по модулю р' »); следовательно, Л является делителем р(р -') = р"-'-'( - 1) и значение Х» = О может появиться, только если последовательность вырождается в нуль. Вообще, если д — любой делитель»п и если Х„кратно д, все последующие элементы мультипликативной последовательности Х„еи Х„е»,, будут кратны д.

Так что когда с = О, необходимо, чтобы Х„и»н были взаимнб простыми числами для всех н., что и ограпичинает длину периода максимум до у~(га) — числа целых взаимно простых чисел с»п, лежащих между О и т. Приемлемой длины периода можно достичь, даже если оговорить, что с = О. Давайте сейчас попытаемся найти такие условия, которым удовлетворяет множитель, чтобы в этом специальном случае период стал настолько длинным, насколько это возможно. Согласно лемме Я период последовательности зависит исключительно от периодов последовательностей при т = р'. Рассмотрим эту ситуацию. Итак, Л„= а" Хе шодр' и ясно, что период будет иметь длину 1 (здесь можно только сказать, что длина периода не болыпе, чем е.

— Прим. ред.), если а кратно р. Поэтому будем считать, что а н р взаимно простые. Тогда период будет наименыпим целым числом Л, таким, что Хо — — а"Хв шос) р'. Если наибольшим общим делителем Хо и р' является р/, то это условие эквивалентно условию Когда а и т — взаимно простые числа, наименьшее число Л, для которого а: — 1 ь (по модулю гп), принято называть порядком а по модулю т. Любое такое значение а, которое имеет максимальный возможный порядок по модулю т, называют переообраэнмм элементом по модулю т. Обозначим через Л(т) порядок первообразного элемента, а именна — максимальный возможный порядок по модулю тп. Из замечаний следует, что Л(р') является делителель р* '(р-1); достаточно легко (см. упр. 11-16, приведенные ниже) можно определить значения Л(гп) во всех следующих случаях: Л(2) = 1, Л(4) = 2, Л(2') = 2' т, если е > 3; Л(р') =р' '(р-1), если р > 2; Л(р"...р,") = 1сьп(Л(рь').... Л(р",)).

(9) Все сказанное можно подытожить в следующей теореме. Теорема В. (С. Г. Сапээ, Р!эдпьэ!с!оььеэ Аг!сЛшес!сю (1801), 190-92.) Максььмальььыьи периодом, возможным, когда с = О, является Л(т), где Л(тп) определено в (9). Этот период достигается, если: ь) Ло и т — взаимно простые числа; й) а является первообразным элементом по модулю т.

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

Теорема С. Числа а является первообрвзным элементом по модулю р' тогда я' только тогда, когда выполняется одно из следующих условий: ь) р = 2, е = 1. и а — нечетное число; й) р=2,с=2 иашоь)4=3; ш) р = 2, е = 3 и а шоб 8 = 3, 5 ььли 7; Условия (т) и (т1) теоремы легко проверяются на компьютере длн больших р. Эффективные методы оценки степени, когда известны множители числа р — 1, обсуждаются в разделе 4.6.3. Теорема С применима только к степеням простых чисел.

Но если заданы значения аьь являющиеся первообразными элементами по модулю р,', то можно найти 1т) р = 2, е > 4 н а шоь! 8 = 3 иля 5, т) р — нечетное число, е = 1, а ф для любого простого делителя д т!) р — нечетное число, е > 1, (по модулю р ). 0 (по модулю р) и а'" ь!1' ф 1 (по модулю р) числа р — 1; а удовлетворяют условию (т) н аг ' 81 1 1 единственное значение а, такое, что а = ау (по модулю р,") при 1 <? ( Ф, используя китайский алгоритм (алгоритм, построенный на основании китайской теоремы об остатках. — Прим.

перев.), рассматриваемый в разделе 4.3.2. Число а будет перво- образным элементом по модулю р",... р,". Таким образом, существует приемлемый эффективный путь построения множителей, удовлетворяющих условию теоремы В, для любых модулей пт умеренной размерности, хотя вычисления в общем случае могут быть весьма длинными. В распространенном случае, когда гп = 2', где е > 4, изложенные выше условия приводят к единственному требованию: а = 3 или 5 (по модулю 8). В этой ситуации четвертая часть всех возможных множителей даст длину периода, равную ги[4, а т/4 будет максимальной длиной периода, когда с = О.

Существует второй, еще более распространенный случай, когда пт = 10'. Используя леммы Р и 14, нетрудно получить необходимые и достаточные условия достижения максимального периода для десятичного компьютера (см. упр. 18). Теорема Р. Еглп т = 10', е > 5, с = 0 и Ло не кратно 2 или 5, то период линейной конгруэптной последовательности равен 5 х 10' э тогда и только тогда, когда а шос( 200 равно одному пз следующих 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. [16) Чему равна длина периода линейной конгруэнтной последовательности с параметрами Хо = 57?2156648, а = 3141592621, с = 2?18281829 и эп = 10000000000? 2. [?6] Будут ли следующие два условия гарантировать максимальную длину периода, когда яэ является степенью 2? В) с — нечетное число;(0) а щон 4 = 1. 3. [?У) Предположим,что гп = 10', где е > 2,н пусть с — нечетное число, не кратное 5.

Характеристики

Список файлов книги