\input style
\chapter{замечания об упражнениях}
уПРАЖНЕНИЯ, ПОМЕЩЕННЫЕ В КНИГАХ НАСТОЯЩЕЙ СЕРИИ, ПРЕДНАЗНАЧЕНЫ КАК ДЛЯ
САМОСТОЯТЕЛЬНОЙ ПРОРАБОТКИ, ТАК И ДЛЯ СЕМИНАРСКИХ ЗАНЯТИЙ. тРУДНО, ЕСЛИ
НЕ НЕВОЗМОЖНО ИЗУЧИТЬ ПРЕДМЕТ, ТОЛЬКО ЧИТАЯ ТЕОРИЮ И НЕ ПРИМЕНЯЯ
ПОЛУЧЕННУЮ ИНФОРМАЦИЮ ДЛЯ РЕШЕНИЯ СПЕЦИАЛЬНЫХ ЗАДАЧ И ТЕМ САМЫМ НЕ
ЗАСТАВЛЯЯ СЕБЯ ОБДУМЫВАТЬ ТО, ЧТО БЫЛО ПРОЧИТАНО. кРОМЕ ТОГО, МЫ ЛУЧШЕ
ВСЕГО ЗАУЧИВАЕМ ТО, ЧТО САМИ ОТКРЫВАЕМ ДЛЯ СЕБЯ. пОЭТОМУ
УПРАЖНЕНИЯ ОБРАЗУЮТ ВАЖНУЮ ЧАСТЬ ДАННОЙ РАБОТЫ; БЫЛИ ПРЕДПРИНЯТЫ
ОПРЕДЕЛЕННЫЕ ПОПЫТКИ, ЧТОБЫ ОТОБРАТЬ УПРАЖНЕНИЯ, В КОТОРЫХ
БЫ СОДЕРЖАЛОСЬ КАК МОЖНО БОЛЬШЕ ИНФОРМАЦИИ И КОТОРЫЕ БЫЛО БЫ ИНТЕРЕСНО РЕШАТЬ.

вО МНОГИХ КНИГАХ ЛЕГКИЕ УПРАЖНЕНИЯ ДАЮТСЯ ВПЕРЕМЕШКУ С ИСКЛЮЧИТЕЛЬНО
ТРУДНЫМИ. зАЧАСТУЮ ЭТО ОЧЕНЬ НЕУДОБНО, ТАК КАК ПЕРЕД ТЕМ, КАК ПРИСТУПАТЬ К
РЕШЕНИЮ ЗАДАЧИ, ЧИТАТЕЛЬ ОБЯЗАТЕЛЬНО ДОЛЖЕН ПРЕДСТАВЛЯТЬ СЕБЕ, СКОЛЬКО
ВРЕМЕНИ УЙДЕТ У НЕГО НА ЭТО РЕШЕНИЕ (ИНАЧЕ ОН МОЖЕТ РАЗВЕ ТОЛЬКО
ПРОСМОТРЕТЬ ВСЕ ЗАДАЧИ). кЛАССИЧЕСКИМ ПРИМЕРОМ ЗДЕСЬ ЯВЛЯЕТСЯ КНИГА
рИЧАРДА бЕЛЛМАНА "дИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ"; ЭТО ВАЖНАЯ ПИОНЕРСКАЯ
РАБОТА, В КОТОРОЙ В КОНЦЕ КАЖДОЙ ГЛАВЫ ПОД РУБРИКОЙ "уПРАЖНЕНИЯ И
ИССЛЕДОВАТЕЛЬСКИЕ ПРОБЛЕМЫ" ДАЕТСЯ ЦЕЛЫЙ РЯД ЗАДАЧ, ГДЕ НАРЯДУ С ГЛУБОКИМИ
ЕЩЕ НЕРЕШЕННЫМИ ПРОБЛЕМАМИ ВСТРЕЧАЮТСЯ ИСКЛЮЧИТЕЛЬНО ТРИВИАЛЬНЫЕ ВОПРОСЫ.
гОВОРЯТ, ЧТО ОДНАЖДЫ КТО-ТО СПРОСИЛ Д-РА бЕЛЛМАНА, КАК ОТЛИЧИТЬ
УПРАЖНЕНИЯ ОТ ИССЛЕДОВАТЕЛЬСКИХ ПРОБЛЕМ, И ТОТ ОТВЕТИЛ: "еСЛИ ВЫ
МОЖЕТЕ РЕШИТЬ ЗАДАЧУ, ЭТО---УПРАЖНЕНИЕ; В ПРОТИВНОМ СЛУЧАЕ ЭТО---ПРОБЛЕМА".

мОЖНО ПРИВЕСТИ МНОГО ДОВОДОВ В ПОЛЬЗУ ТОГО, ЧТО В КНИГЕ ТИПА ЭТОЙ ДОЛЖНЫ
БЫТЬ КАК ИССЛЕДОВАТЕЛЬСКИЕ ПРОБЛЕМЫ, ТАК И ОЧЕНЬ ПРОСТЫЕ УПРАЖНЕНИЯ, И ДЛЯ
ТОГО ЧТОБЫ ЧИТАТЕЛЮ НЕ ПРИХОДИЛОСЬ ЛОМАТЬ ГОЛОВУ НАД ТЕМ, КАКАЯ ЗАДАЧА
ЛЕГКАЯ, А КАКАЯ ТРУДНАЯ, МЫ ВВЕЛИ "ОЦЕНКИ", КОТОРЫЕ УКАЗЫВАЮТ СТЕПЕНЬ
ТРУДНОСТИ КАЖДОГО УПРАЖНЕНИЯ. эТИ ОЦЕНКИ ИМЕЮТ СЛЕДУЮЩЕЕ ЗНАЧЕНИЕ:
\descrtable{
\bf оЦЕНКА  & \bf оБЎЯСНЕНИЕ \cr
00 & чРЕЗВЫЧАЙНО ЛЕГКОЕ УПРАЖНЕНИЕ, НА КОТОРОЕ МОЖНО ОТВЕТИТЬ СРАЗУ ЖЕ,
     ЕСЛИ ПОНЯТ МАТЕРИАЛ ТЕКСТА, И КОТОРОЕ ПОЧТИ ВСЕГДА МОЖНО РЕШИТЬ "В УМЕ".\cr
%% 11
10 & пРОСТАЯ ЗАДАЧА, КОТОРАЯ ЗАСТАВЛЯЕТ ЗАДУМАТЬСЯ НАД ПРОЧИТАННЫМ
     МАТЕРИАЛОМ, НО НЕ ПРЕДСТАВЛЯЕТ НИКАКИХ ОСОБЫХ ТРУДНОСТЕЙ. нА РЕШЕНИЕ ТАКОЙ
     ЗАДАЧИ ТРЕБУЕТСЯ НЕ БОЛЬШЕ ОДНОЙ МИНУТЫ; В ПРОЦЕССЕ РЕШЕНИЯ МОГУТ
     ПОНАДОБИТЬСЯ КАРАНДАШ И БУМАГА. \cr
20 & зАДАЧА СРЕДНЕЙ ТРУДНОСТИ, ПОЗВОЛЯЮЩАЯ ПРОВЕРИТЬ, НАСКОЛЬКО ХОРОШО
     ПОНЯТ ТЕКСТ. нА ТО ЧТОБЫ ДАТЬ ИСЧЕРПЫВАЮЩИЙ ОТВЕТ, ТРЕБУЕТСЯ ПРИМЕРНО
     15--20~МИНУТ. \cr
30 & зАДАЧА УМЕРЕННОЙ ТРУДНОСТИ И/ИЛИ СЛОЖНОСТИ, ДЛЯ УДОВЛЕТВОРИТЕЛЬНОГО
     РЕШЕНИЯ КОТОРОЙ ТРЕБУЕТСЯ БОЛЬШЕ ДВУХ ЧАСОВ. \cr
40 & оЧЕНЬ ТРУДНАЯ ИЛИ ТРУДОЕМКАЯ ЗАДАЧА, КОТОРУЮ, ВЕРОЯТНО, СЛЕДУЕТ
     ВКЛЮЧИТЬ В ПЛАН ПРАКТИЧЕСКИХ ЗАНЯТИЙ. пРЕДПОЛАГАЕТСЯ, ЧТО СТУДЕНТ МОЖЕТ
     РЕШИТЬ ТАКУЮ ЗАДАЧУ, НО ДЛЯ ЭТОГО ЕМУ ПОТРЕБУЕТСЯ ЗНАЧИТЕЛЬНЫЙ ОТРЕЗОК
     ВРЕМЕНИ; ЗАДАЧА РЕШАЕТСЯ НЕТРИВИАЛЬНЫМ ОБРАЗОМ. \cr
50 & иССЛЕДОВАТЕЛЬСКАЯ ПРОБЛЕМА, КОТОРАЯ (НАСКОЛЬКО ЭТО БЫЛО ИЗВЕСТНО АВТОРУ
     В МОМЕНТ НАПИСАНИЯ) ЕЩЕ НЕ ПОЛУЧИЛА УДОВЛЕТВОРИТЕЛЬНОГО РЕШЕНИЯ. еСЛИ
     ЧИТАТЕЛЬ НАЙДЕТ РЕШЕНИЕ ЭТОЙ ЗАДАЧИ, ЕГО НАСТОЯТЕЛЬНО ПРОСЯТ ОПУБЛИКОВАТЬ
     ЕГО; КРОМЕ ТОГО, АВТОР ДАННОЙ КНИГИ БУДЕТ ОЧЕНЬ ПРИЗНАТЕЛЕН, ЕСЛИ ЕМУ
     СООБЩАТ РЕШЕНИЕ, КАК МОЖНО БЫСТРЕЕ (ПРИ УСЛОВИИ, ЧТО ОНО ПРАВИЛЬНО). \cr
}

иНТЕРПОЛИРУЯ ПО ЭТОЙ "ЛОГАРИФМИЧЕСКОЙ" ШКАЛЕ, МОЖНО ПРИКИНУТЬ, ЧТО
ОЗНАЧАЕТ ЛЮБАЯ ПРОМЕЖУТОЧНАЯ ОЦЕНКА. нАПРИМЕР, ОЦЕНКА~17 ГОВОРИТ О ТОМ,
ЧТО ДАННОЕ УПРАЖНЕНИЕ ЧУТЬ ЛЕГЧЕ, ЧЕМ УПРАЖНЕНИЕ СРЕДНЕЙ ТРУДНОСТИ. зАДАЧА
С ОЦЕНКОЙ~50, ЕСЛИ ОНА БУДЕТ РЕШЕНА КАКИМ-ЛИБО ЧИТАТЕЛЕМ, В СЛЕДУЮЩИХ
ИЗДАНИЯХ ДАННОЙ КНИГИ МОЖЕТ ИМЕТЬ УЖЕ ОЦЕНКУ~45.

аВТОР ЧЕСТНО СТАРАЛСЯ ДАВАТЬ ОБЎЕКТИВНЫЕ ОЦЕНКИ, НО ТОМУ, КТО СОСТАВЛЯЕТ
ЗАДАЧИ, ТРУДНО ПРЕДВИДЕТЬ, НАСКОЛЬКО ТРУДНЫМИ ЭТИ ЗАДАЧИ ОКАЖУТСЯ ДЛЯ
КОГО-ТО ДРУГОГО; К ТОМУ ЖЕ У КАЖДОГО ЧЕЛОВЕКА СУЩЕСТВУЕТ ОПРЕДЕЛЕННЫЙ ТИП
ЗАДАЧ, КОТОРЫЕ ОН РЕШАЕТ БЫСТРЕЕ. нАДЕЮСЬ, ЧТО ВЫСТАВЛЕННЫЕ МНОЙ ОЦЕНКИ
ДАЮТ ПРАВИЛЬНОЕ ПРЕДСТАВЛЕНИЕ О СТЕПЕНИ ТРУДНОСТИ ЗАДАЧ, НО В ОБЩЕМ
ИХ НУЖНО ВОСПРИНИМАТЬ КАК ОРИЕНТИРОВОЧНЫЕ, А НЕ АБСОЛЮТНЫЕ.

эТА КНИГА НАПИСАНА ДЛЯ ЧИТАТЕЛЕЙ САМЫХ РАЗНЫХ СТЕПЕНЕЙ МАТЕМАТИЧЕСКОЙ
ПОДГОТОВКИ И ИСКУШЕННОСТИ, ПОЭТОМУ НЕКОТОРЫЕ УПРАЖНЕНИЯ ПРЕДНАЗНАЧЕНЫ
ТОЛЬКО ДЛЯ ЧИТАТЕЛЕЙ С МАТЕМАТИЧЕСКИМ УКЛОНОМ. еСЛИ В КАКОМ-ЛИБО
УПРАЖНЕНИИ МАТЕМАТИЧЕСКИЕ ПОНЯТИЯ ИЛИ РЕЗУЛЬТАТЫ ИСПОЛЬЗУЮТСЯ БОЛЕЕ ШИРОКО,
ЧЕМ ЭТО НЕОБХОДИМО ДЛЯ ТЕХ, КОГО В ПЕРВУЮ ОЧЕРЕДЬ ИНТЕРЕСУЕТ
ПРОГРАММИРОВАНИЕ АЛГОРИТМОВ, ТО ПЕРЕД ОЦЕНКОЙ ТАКОГО УПРАЖНЕНИЯ
СТАВИТСЯ БУКВА "\emph{м}". еСЛИ ДЛЯ РЕШЕНИЯ УПРАЖНЕНИЯ ТРЕБУЕТСЯ
ЗНАНИЕ ВЫСШЕЙ МАТЕМАТИКИ В БОЛЬШЕМ ОБЎЕМЕ, ЧЕМ ЭТО ДАНО В НАСТОЯЩЕЙ
%% 12
КНИГЕ, ТО СТАВЯТСЯ БУКВЫ~"\emph{вм}". пОМЕТКА~"\emph{вм}" ОТНЮДЬ НЕ
ЯВЛЯЕТСЯ СВИДЕТЕЛЬСТВОМ ТОГО, ЧТО ДАННОЕ УПРАЖНЕНИЕ ТРУДНОЕ.

пЕРЕД НЕКОТОРЫМИ УПРАЖНЕНИЯМИ СТОИТ СТРЕЛКА~"$\btr$"; ЭТО ОЗНАЧАЕТ, ЧТО
ДАННОЕ УПРАЖНЕНИЕ ОСОБЕННО ПОУЧИТЕЛЬНО И ЕГО РЕКОМЕНДУЕТСЯ ОБЯЗАТЕЛЬНО
ВЫПОЛНИТЬ. сАМО СОБОЙ РАЗУМЕЕТСЯ, НИКТО НЕ ОЖИДАЕТ, ЧТО ЧИТАТЕЛЬ (ИЛИ
СТУДЕНТ) БУДЕТ РЕШАТЬ ВСЕ ЗАДАЧИ, ПОТОМУ-ТО НАИБОЛЕЕ ПОЛЕЗНЫЕ ИЗ НИХ И
ВЫДЕЛЕНЫ. эТО СОВСЕМ НЕ ЗНАЧИТ, ЧТО ДРУГИЕ ЗАДАЧИ НЕ СТОИТ РЕШАТЬ! кАЖДЫЙ
ЧИТАТЕЛЬ ДОЛЖЕН ПО КРАЙНЕЙ МЕРЕ ПОПЫТАТЬСЯ РЕШИТЬ ВСЕ ЗАДАЧИ С
ОЦЕНКОЙ~10 И НИЖЕ; СТРЕЛКИ ЖЕ ПОМОГУТ ВЫБРАТЬ, КАКИЕ ЗАДАЧИ С БОЛЕЕ
ВЫСОКИМИ ОЦЕНКАМИ СЛЕДУЕТ РЕШИТЬ В ПЕРВУЮ ОЧЕРЕДЬ.

к БОЛЬШИНСТВУ УПРАЖНЕНИЙ ПРИВЕДЕНЫ ОТВЕТЫ; ОНИ ПОМЕЩЕНЫ В СПЕЦИАЛЬНОМ
РАЗДЕЛЕ В КОНЦЕ КНИГИ. пОЛЬЗУЙТЕСЬ ИМИ МУДРО;
В ОТВЕТ СМОТРИТЕ ТОЛЬКО ПОСЛЕ ТОГО, КАК ВЫ ПРИЛОЖИЛИ ДОСТАТОЧНО УСИЛИЙ,
ЧТОБЫ РЕШИТЬ ЗАДАЧУ САМОСТОЯТЕЛЬНО, ИЛИ ЖЕ ЕСЛИ ДЛЯ РЕШЕНИЯ ДАННОЙ
ЗАДАЧИ У ВАС НЕТ ВРЕМЕНИ. еСЛИ ПОЛУЧЕН СОБСТВЕННЫЙ ОТВЕТ, ЛИБО ЕСЛИ ВЫ
ДЕЙСТВИТЕЛЬНО ПЫТАЛИСЬ РЕШИТЬ ЗАДАЧУ, ТОЛЬКО В ЭТОМ СЛУЧАЕ ОТВЕТ,
ПОМЕЩЕННЫЙ В КНИГЕ, БУДЕТ ПОУЧИТЕЛЬНЫМ И ПОЛЕЗНЫМ. кАК ПРАВИЛО, ОТВЕТЫ К
ЗАДАЧАМ ИЗЛАГАЮТСЯ ОЧЕНЬ КРАТКО, СХЕМАТИЧНО, ТАК КАК ПРЕДПОЛАГАЕТСЯ, ЧТО
ЧИТАТЕЛЬ УЖЕ ЧЕСТНО ПЫТАЛСЯ РЕШИТЬ ЗАДАЧУ СОБСТВЕННЫМИ СИЛАМИ. иНОГДА В
ПРИВЕДЕННОМ РЕШЕНИИ ДАЕТСЯ МЕНЬШЕ ИНФОРМАЦИИ, ЧЕМ СПРАШИВАЛОСЬ,
ЧАЩЕ---НАОБОРОТ. вПОЛНЕ ВОЗМОЖНО, ЧТО ПОЛУЧЕННЫЙ ВАМИ ОТВЕТ ОКАЖЕТСЯ ЛУЧШЕ
ОТВЕТА, ПОМЕЩЕННОГО В КНИГЕ, ИЛИ ВЫ НАЙДЕТЕ ОШИБКУ В ЭТОМ ОТВЕТЕ; В ТАКОМ
СЛУЧАЕ АВТОР БЫЛ БЫ ОЧЕНЬ ОБЯЗАН, ЕСЛИ БЫ ВЫ КАК МОЖНО СКОРЕЕ ПОДРОБНО
СООБЩИЛИ ЕМУ ОБ ЭТОМ. в ПОСЛЕДУЮЩИХ ИЗДАНИЯХ НАСТОЯЩЕЙ КНИГИ
БУДЕТ ПОМЕЩЕНО УЖЕ ИСПРАВЛЕННОЕ РЕШЕНИЕ ВМЕСТЕ С ИМЕНЕМ ЕГО АВТОРА.

\bigskip
\centerline{\bf сВОДКА УСЛОВНЫХ ОБОЗНАЧЕНИЙ}
\ctable{
\emph{#}\bskip\hfil&\bskip#\hfil\cr
$\btr$ &  рЕКОМЕНДУЕТСЯ \cr
м & с МАТЕМАТИЧЕСКИМ УКЛОНОМ \cr
вм & тРЕБУЕТ ЗНАНИЯ "ВЫСШЕЙ МАТЕМАТИКИ" \cr
00 & тРЕБУЕТ НЕМЕДЛЕННОГО ОТВЕТА \cr
10 & пРОСТОЕ (НА ОДНУ МИНУТУ) \cr
20 & сРЕДНЕЙ ТРУДНОСТИ (НА ЧЕТВЕРТЬ ЧАСА) \cr
30 & пОВЫШЕННОЙ ТРУДНОСТИ \cr
40 & дЛЯ "МАТПРАКТИКУМА" \cr
50 & иССЛЕДОВАТЕЛЬСКАЯ ПРОБЛЕМА \cr
}

\excercises
\ex[00] чТО ОЗНАЧАЕТ ПОМЕТКА~"\emph{м20}"?

\ex[10] кАКОЕ ЗНАЧЕНИЕ ДЛЯ ЧИТАТЕЛЯ ИМЕЮТ УПРАЖНЕНИЯ, ПОМЕЩАЕМЫЕ В УЧЕБНИКАХ?

\ex[м50] дОКАЖИТЕ, ЧТО ЕСЛИ~$n$---ЦЕЛОЕ ЧИСЛО, $n>2$, ТО
УРАВНЕНИЕ~$x^n+y^n=z^n$ НЕРАЗРЕШИМО В ЦЕЛЫХ ПОЛОЖИТЕЛЬНЫХ ЧИСЛАХ~$x$, $y$, $z$.

%% 13
\chapno=2\chapnotrue\chapter{сЛУЧАЙНЫЕ ЧИСЛА} % 3
\epigraph
вСЯКИЙ, КТО ПИТАЕТ СЛАБОСТЬ К АРИФМЕТИЧЕСКИМ МЕТОДАМ ПОЛУЧЕНИЯ СЛУЧАЙНЫХ
ЧИСЕЛ, ГРЕШЕН ВНЕ ВСЯКИХ СОМНЕНИЙ.
\signed дЖОН ФОН нЕЙМАН (1951)

\epigraph
кРУГЛЫЕ ЧИСЛА ВСЕГДА ФАЛЬШИВЫ.
\signed сЭМЮЭЛЬ дЖОНСОН (ОКОЛО 1750)

\epigraph Lest men suspect your tale untrue, \goodbreak
Keep probability in view%
\note{1}%
{чТОБЫ ЛЮДИ ПОВЕРИЛИ ВАШИМ РОССКАЗНЯМ, ПОМНИТЕ О
 ВЕРОЯТНОСТИ.---{\sl пРИМ. ПЕРЕВ.\/}
}.
\signed дЖОН гЭЙ (1727)

\subchap{введение} % 3.1
"сЛУЧАЙНО ВЫБРАННЫЕ" ЧИСЛА ОКАЗЫВАЮТСЯ ПОЛЕЗНЫМИ ДЛЯ САМЫХ РАЗЛИЧНЫХ ЦЕЛЕЙ.
 вОТ НЕКОТОРЫЕ ПРИМЕРЫ:
\medskip
a)~\emph{мОДЕЛИРОВАНИЕ.} кОГДА С ПОМОЩЬЮ ВЫЧИСЛИТЕЛЬНОЙ
МАШИНЫ МОДЕЛИРУЮТСЯ ПРИРОДНЫЕ ЯВЛЕНИЯ, СЛУЧАЙНЫЕ ЧИСЛА
ПОЗВОЛЯЮТ ПРИБЛИЗИТЬ МОДЕЛЬ К РЕАЛЬНОСТИ. мОДЕЛИРОВАНИЕ ПРИМЕНЯЕТСЯ ВО
МНОГИХ ОБЛАСТЯХ: ОТ ЯДЕРНОЙ ФИЗИКИ (ЧАСТИЦЫ ИСПЫТЫВАЮТ СЛУЧАЙНЫЕ
СОУДАРЕНИЯ) ДО СИСТЕМНОГО АНАЛИЗА (СКАЖЕМ, ЛЮДИ ВХОДЯТ В БАНК ЧЕРЕЗ
СЛУЧАЙНЫЕ ИНТЕРВАЛЫ ВРЕМЕНИ).

b)~\emph{вЫБОРКА.} чАСТО БЫВАЕТ, ЧТО ПРОВЕРКА ВСЕХ ВОЗМОЖНЫХ ВАРИАНТОВ
ПРАКТИЧЕСКИ НЕОСУЩЕСТВИМА. тОГДА НА НЕКОТОРЫЕ ВОПРОСЫ ПОЗВОЛЯЕТ ПОЛУЧИТЬ
ОТВЕТЫ СЛУЧАЙНАЯ ВЫБОРКА.

c)~\emph{чИСЛЕННЫЙ АНАЛИЗ.} дЛЯ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ
МАТЕМАТИКИ БЫЛА РАЗРАБОТАНА ОСТРОУМНАЯ ТЕХНИКА, ИСПОЛЬЗУЮЩАЯ СЛУЧАЙНЫЕ
ЧИСЛА. оБ ЭТОМ НАПИСАН РЯД КНИГ.

d)~\emph{пРОГРАММИРОВАНИЕ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ МАШИН.} сЛУЧАЙНЫЕ ЗНАЧЕНИЯ
СЛУЖАТ ХОРОШИМ ИСТОЧНИКОМ ДАННЫХ ПРИ ИСПЫТАНИИ ЭФФЕКТИВНОСТИ РАЗЛИЧНЫХ
АЛГОРИТМОВ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ МАШИН. в ЭТОЙ КНИГЕ НАС БУДЕТ В ОСНОВНОМ
ИНТЕРЕСОВАТЬ ИМЕННО ТАКОЕ ИСПОЛЬЗОВАНИЕ СЛУЧАЙНЫХ ЧИСЕЛ. пОЭТОМУ ПРЕЖДЕ
ЧЕМ ПОЙДЕТ РЕЧЬ О ДРУГИХ АЛГОРИТМАХ, ЗДЕСЬ, В ТРЕТЬЕЙ ГЛАВЕ, БУДУТ
РАССМОТРЕНЫ СЛУЧАЙНЫЕ ЧИСЛА.

e)~\emph{пРИНЯТИЕ РЕШЕНИЙ.} гОВОРЯТ, ЧТО МНОГИЕ РУКОВОДИТЕЛИ ПРИНИМАЮТ
РЕШЕНИЯ, БРОСАЯ МОНЕТКУ ИЛИ КОСТИ. хОДЯТ ДАЖЕ
%% 14
СЛУХИ, ЧТО НЕКОТОРЫЕ ПРОФЕССОРА В КОЛЛЕДЖАХ ДОБИВАЮТСЯ УСПЕХА ИМЕННО
ТАКИМ ОБРАЗОМ. иНОГДА БЫВАЕТ ВАЖНО ПРИНИМАТЬ СОВЕРШЕННО НЕПРЕДВЗЯТЫЕ
РЕШЕНИЯ. пОЛЕЗНО ПРЕДУСМОТРЕТЬ ТАКУЮ ВОЗМОЖНОСТЬ ДЛЯ АЛГОРИТМОВ,
ПРИМЕНЯЕМЫХ В ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ, НАПРИМЕР В СЛУЧАЯХ, КОГДА ПРИНЯТИЕ
ДЕТЕРМИНИРОВАННОГО РЕШЕНИЯ МОЖЕТ ПРИВЕСТИ К ЗАМЕДЛЕНИЮ СЧЕТА.
сЛУЧАЙНОСТЬ, КРОМЕ ТОГО,---СУЩЕСТВЕННАЯ ЧАСТЬ ОПТИМАЛЬНЫХ СТРАТЕГИЙ В
ТЕОРИИ ИГР.

f)~\emph{рАЗВЛЕЧЕНИЯ.} мНОГИЕ ПРОВОДЯТ ВРЕМЯ, ТАСУЯ КАРТЫ, БРОСАЯ КОСТИ
ИЛИ НАБЛЮДАЯ ЗА КОЛЕСОМ РУЛЕТКИ, И НАХОДЯТ В ЭТОМ НЕИЗЎЯСНИМОЕ
УДОВОЛЬСТВИЕ. тАКИМ ТРАДИЦИОННЫМ ИСПОЛЬЗОВАНИЕМ СЛУЧАЙНЫХ ЧИСЕЛ
ОБЎЯСНЯЕТСЯ, ПОЧЕМУ ТЕРМИН "мОНТЕ-кАРЛО" СЛУЖИТ ОБЩИМ НАИМЕНОВАНИЕМ ДЛЯ
ВСЕХ АЛГОРИТМОВ, В КОТОРЫХ ПРИМЕНЯЮТ СЛУЧАЙНЫЕ ЧИСЛА.
\medskip
сТАЛО ОБЫЧНЫМ В ЭТОМ МЕСТЕ ПОСВЯЩАТЬ НЕСКОЛЬКО АБЗАЦЕВ ФИЛОСОФСКОМУ
ОБСУЖДЕНИЮ ТОГО, ЧТО ЖЕ ТАКОЕ "СЛУЧАЙНОСТЬ". в НЕКОТОРОМ СМЫСЛЕ ТАКОГО
ОБЎЕКТА, КАК СЛУЧАЙНОЕ ЧИСЛО, ПРОСТО НЕТ. сКАЖЕМ, ДВОЙКА---ЭТО СЛУЧАЙНОЕ
ЧИСЛО? сКОРЕЕ МЫ ГОВОРИМ О \emph{ПОСЛЕДОВАТЕЛЬНОСТИ НЕЗАВИСИМЫХ} СЛУЧАЙНЫХ
ЧИСЕЛ С ОПРЕДЕЛЕННЫМ \emph{ЗАКОНОМ РАСПРЕДЕЛЕНИЯ,} И ЭТО ОЗНАЧАЕТ, ГРУБО
ГОВОРЯ, ЧТО КАЖДОЕ ЧИСЛО БЫЛО ПОЛУЧЕНО САМЫМ ПРОИЗВОЛЬНЫМ ОБРАЗОМ,
БЕЗ ВСЯКОЙ СВЯЗИ С ДРУГИМИ ЧЛЕНАМИ ПОСЛЕДОВАТЕЛЬНОСТИ, И ЧТО У НЕГО ЕСТЬ
ОПРЕДЕЛЕННАЯ ВЕРОЯТНОСТЬ ОКАЗАТЬСЯ В ЛЮБОМ ЗАДАННОМ ИНТЕРВАЛЕ.

\dfn{рАВНОМЕРНЫМ} НАЗЫВАЕТСЯ ТАКОЕ РАСПРЕДЕЛЕНИЕ, ПРИ КОТОРОМ КАЖДОЕ
ВОЗМОЖНОЕ ЧИСЛО РАВНОВЕРОЯТНО. оБЫЧНО, ЕСЛИ СПЕЦИАЛЬНО НЕ ОГОВОРЕНО
ЧТО-ЛИБО ИНОЕ, ИМЕЮТ В ВИДУ РАВНОМЕРНЫЕ РАСПРЕДЕЛЕНИЯ.

кАЖДАЯ ИЗ ДЕСЯТИ ЦИФР ОТ~$0$ ДО~$9$ СОСТАВЛЯЕТ ПРИМЕРНО ОДНУ ДЕСЯТУЮ ЧАСТЬ
ВСЕХ ЦИФР ВО ВСЯКОЙ СЛУЧАЙНОЙ (РАВНОМЕРНОЙ) ПОСЛЕДОВАТЕЛЬНОСТИ ЦИФР. лЮБАЯ
ЗАДАННАЯ ПАРА ДВУХ СОСЕДНИХ ЦИФР ДОЛЖНА СОСТАВЛЯТЬ ПРИМЕРНО
$\frac1/{100}$~ЧАСТЬ ВСЕХ ПАР, ВСТРЕЧАЮЩИХСЯ В ПОСЛЕДОВАТЕЛЬНОСТИ,
И~Т.~Д. тЕМ НЕ МЕНЕЕ, ЕСЛИ МЫ РАССМОТРИМ КАКУЮ-НИБУДЬ КОНКРЕТНУЮ СЛУЧАЙНУЮ
ПОСЛЕДОВАТЕЛЬНОСТЬ ИЗ МИЛЛИОНА ЦИФР, В НЕЙ СОВСЕМ НЕ ОБЯЗАТЕЛЬНО
ОКАЖЕТСЯ РОВНО $100\,000$~НУЛЕЙ, $100\,000$~ЕДИНИЦ И~Т.~Д. в
ДЕЙСТВИТЕЛЬНОСТИ ВЕРОЯТНОСТЬ ТАКОГО СОБЫТИЯ ОЧЕНЬ МАЛА. зАКОНОМЕРНОСТЬ ЖЕ
ВЫПОЛНЯЕТСЯ В СРЕДНЕМ ДЛЯ \emph{ПОСЛЕДОВАТЕЛЬНОСТИ} ТАКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

лЮБАЯ ЗАДАННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ СТОЛЬ ЖЕ ВЕРОЯТНА, КАК И
ПОСЛЕДОВАТЕЛЬНОСТЬ, СОСТОЯЩАЯ ИЗ ОДНИХ \emph{НУЛЕЙ.} бОЛЕЕ ТОГО, ДОПУСТИМ,
ЧТО МЫ ВЫБИРАЕМ СЛУЧАЙНЫМ ОБРАЗОМ ПОСЛЕДОВАТЕЛЬНОСТЬ ИЗ МИЛЛИОНА ЦИФР.
пУСТЬ ОКАЗАЛОСЬ, ЧТО ПЕРВЫЕ $999\,999$
%% 15
ИЗ НИХ РАВНЫ НУЛЮ. и В ЭТОМ СЛУЧАЕ ВЕРОЯТНОСТЬ ТОГО, ЧТО ПОСЛЕДНЯЯ ЦИФРА
БУДЕТ НУЛЕМ, ВСЕ ЕЩЕ В ТОЧНОСТИ РАВНА~$\frac 1/{10}$, ЕСЛИ ВЫБОРКА
ДЕЙСТВИТЕЛЬНО СЛУЧАЙНАЯ. дЛЯ МНОГИХ ЭТИ УТВЕРЖДЕНИЯ ЗВУЧАТ КАК ПАРАДОКС,
НО НА САМОМ ДЕЛЕ В НИХ НЕТ ПРОТИВОРЕЧИЯ.

сУЩЕСТВУЕТ НЕСКОЛЬКО СПОСОБОВ СФОРМУЛИРОВАТЬ ХОРОШЕЕ АБСТРАКТНОЕ
ОПРЕДЕЛЕНИЕ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. мЫ ЕЩЕ ВЕРНЕМСЯ К ЭТОМУ
ИНТЕРЕСНОМУ ВОПРОСУ В~\S~3.5. пОКА ЖЕ ДОСТАТОЧНО ИНТУИТИВНО ПОНЯТЬ ИДЕЮ.

рАНЬШЕ УЧЕНЫЕ, НУЖДАВШИЕСЯ ДЛЯ СВОЕЙ РАБОТЫ В СЛУЧАЙНЫХ ЧИСЛАХ,
РАСКЛАДЫВАЛИ КАРТЫ, БРОСАЛИ КОСТИ ИЛИ ВЫТАСКИВАЛИ ШАРЫ ИЗ УРНЫ, КОТОРУЮ
ПРЕДВАРИТЕЛЬНО "КАК СЛЕДУЕТ ТРЯСЛИ". в 1927~Г.\ л.~тИППЕТТ ОПУБЛИКОВАЛ
ТАБЛИЦЫ, СОДЕРЖАЩИЕ СВЫШЕ $40\,000$~СЛУЧАЙНЫХ ЦИФР, "ПРОИЗВОЛЬНО ВЗЯТЫХ ИЗ
ОТЧЕТОВ О ПЕРЕПИСИ". пОЗЖЕ БЫЛИ СКОНСТРУИРОВАНЫ СПЕЦИАЛЬНЫЕ МАШИНЫ,
МЕХАНИЧЕСКИ ВЫРАБАТЫВАЮЩИЕ СЛУЧАЙНЫЕ ЧИСЛА. пЕРВУЮ ТАКУЮ МАШИНУ В
1939~Г.\ ИСПОЛЬЗОВАЛИ м.~дЖ.~кЕНДАЛЛ И~б.~бЭБИНГТОН-сМИТ ПРИ СОЗДАНИИ
ТАБЛИЦ, ВКЛЮЧАЮЩИХ 100~ТЫСЯЧ СЛУЧАЙНЫХ ЦИФР. в 1955~Г.\ КОМПАНИЯ RAND
Corporation ОПУБЛИКОВАЛА ХОРОШО ИЗВЕСТНЫЕ ТАБЛИЦЫ С МИЛЛИОНОМ СЛУЧАЙНЫХ
ЦИФР, ПОЛУЧЕННЫХ ДРУГОЙ ТАКОЙ МАШИНОЙ. иЗВЕСТНАЯ МАШИНА ERNIE,
ВЫРАБАТЫВАЮЩАЯ СЛУЧАЙНЫЕ ЧИСЛА, ОПРЕДЕЛЯЕТ ВЫИГРАВШИЕ НОМЕРА В
бРИТАНСКОЙ ЛОТЕРЕЕ. [сМ.\ СТАТЬИ кЕНДАЛЛА И бЭБИНГТОН-сМИТА В
{\sl Journal of the Royal Statistical Society,\/}
Series~A, {\bf 101} (1938), 147--166, И Series~в, {\bf 6} (1939), 51--61,
А ТАКЖЕ ОБЗОР В~{\sl Math.\ Comp.,\/} {\bf 10} (1956), 39--43.]

вСКОРЕ ПОСЛЕ СОЗДАНИЯ ВЫЧИСЛИТЕЛЬНЫХ МАШИН НАЧАЛИСЬ ПОИСКИ ЭФФЕКТИВНЫХ
МЕТОДОВ ПОЛУЧЕНИЯ СЛУЧАЙНЫХ ЧИСЕЛ, ПРИГОДНЫХ ДЛЯ ИСПОЛЬЗОВАНИЯ В
ПРОГРАММАХ. в ПРИНЦИПЕ МОЖНО РАБОТАТЬ И С ТАБЛИЦАМИ, ОДНАКО, ЭТОТ МЕТОД
ИМЕЕТ ОГРАНИЧЕНИЯ, СВЯЗАННЫЕ С КОНЕЧНЫМ ОБЎЕМОМ ПАМЯТИ МАШИН И ЗАТРАТАМИ
ВРЕМЕНИ ДЛЯ ВВОДА ЧИСЕЛ В МАШИНУ В ТОМ СЛУЧАЕ, КОГДА ТАБЛИЦА ОКАЗЫВАЕТСЯ
СЛИШКОМ КОРОТКОЙ. кРОМЕ ТОГО, ДОВОЛЬНО НЕПРИЯТНО ГОТОВИТЬ ТАБЛИЦЫ
ЗАРАНЕЕ, ДА И ВООБЩЕ ИМЕТЬ С НИМИ ДЕЛО. мОЖНО ПРИСОЕДИНИТЬ К эвм МАШИНУ
ТИПА ERNIE, НО И ЭТОТ ПУТЬ ОКАЗЫВАЕТСЯ НЕУДОВЛЕТВОРИТЕЛЬНЫМ, ПОТОМУ ЧТО
ПРИ ОТЛАДКЕ ПРОГРАММЫ НЕВОЗМОЖНО ВОСПРОИЗВЕСТИ ВТОРИЧНО ВЫЧИСЛЕНИЯ,
СДЕЛАННЫЕ РАНЕЕ.

нЕСОВЕРШЕНСТВО ВСЕХ ЭТИХ МЕТОДОВ ПРОБУДИЛО ИНТЕРЕС К ПОЛУЧЕНИЮ СЛУЧАЙНЫХ
ЧИСЕЛ С ПОМОЩЬЮ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ. пЕРВЫМ
ТАКОЙ ПОДХОД В 1946~Г.\ ПРЕДЛОЖИЛ дЖОН ФОН нЕЙМАН, ИСПОЛЬЗОВАВШИЙ МЕТОД
"СЕРЕДИНЫ КВАДРАТА". иДЕЯ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ПРЕДЫДУЩЕЕ СЛУЧАЙНОЕ
ЧИСЛО ВОЗВОДИТСЯ В КВАДРАТ, А ЗАТЕМ ИЗ РЕЗУЛЬТАТА ИЗВЛЕКАЮТСЯ СРЕДНИЕ
ЦИФРЫ. пУСТЬ, НАПРИМЕР, МЫ ВЫРАБАТЫВАЕМ ДЕСЯТИЗНАЧНЫЕ ЧИСЛА И ДОПУСТИМ,
ЧТО ПРЕДЫДУЩЕЕ ЧИСЛО БЫЛО РАВНО~$5772156649$;
%% 16
ВОЗВЕДЯ ЕГО В КВАДРАТ, ПОЛУЧИМ
$$
33317792380594909201,
$$
И ПОЭТОМУ СЛЕДУЮЩЕЕ ЧИСЛО РАВНО~$7923805949$.

мЕТОД ВЫЗЫВАЕТ ДОВОЛЬНО ОЧЕВИДНОЕ ВОЗРАЖЕНИЕ. кАК МОЖЕТ БЫТЬ СЛУЧАЙНОЙ
ВЫРАБОТАННАЯ ТАКИМ СПОСОБОМ ПОСЛЕДОВАТЕЛЬНОСТЬ, ЕСЛИ КАЖДЫЙ ЕЕ ЧЛЕН
ПОЛНОСТЬЮ ОПРЕДЕЛЕН СВОИМ ПРЕДШЕСТВЕННИКОМ?

оТВЕТ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ \emph{НЕ} СЛУЧАЙНА
НО \emph{ВЫГЛЯДИТ} КАК СЛУЧАЙНАЯ. в ТИПИЧНЫХ ПРИЛОЖЕНИЯХ ОБЫЧНО НЕ ИМЕЕТ
ЗНАЧЕНИЯ, КАК СВЯЗАНЫ ДРУГ С ДРУГОМ ДВА ПОСЛЕДУЮЩИХ ЧИСЛА
ПОСЛЕДОВАТЕЛЬНОСТИ; ТАКИМ ОБРАЗОМ, НЕСЛУЧАЙНЫЙ ХАРАКТЕР
ПОСЛЕДОВАТЕЛЬНОСТИ НЕ ЯВЛЯЕТСЯ НЕЖЕЛАТЕЛЬНЫМ. иНТУИТИВНО МЕТОД СЕРЕДИНЫ
КВАДРАТА ДОЛЖЕН ДОВОЛЬНО ХОРОШО "ПЕРЕМЕШИВАТЬ" ПРЕДЫДУЩЕЕ ЧИСЛО.

в НАУЧНО-ТЕХНИЧЕСКОЙ ЛИТЕРАТУРЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ВЫРАБАТЫВАЕМЫЕ
ДЕТЕРМИНИСТСКИМИ СПОСОБАМИ, НАЗЫВАЮТСЯ \emph{ПСЕВДОСЛУЧАЙНЫМИ} ИЛИ
\emph{КВАЗИСЛУЧАЙНЫМИ.} зДЕСЬ ЖЕ МЫ БУДЕМ НАЗЫВАТЬ ИХ ПРОСТО СЛУЧАЙНЫМИ
ПОСЛЕДОВАТЕЛЬНОСТЯМИ, ПОНИМАЯ, ЧТО ОНИ ТОЛЬКО \emph{ПРОИЗВОДЯТ
ВПЕЧАТЛЕНИЕ} СЛУЧАЙНЫХ. нАВЕРНОЕ, ВСЕ, ЧТО МОЖНО СКАЗАТЬ О СЛУЧАЙНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ, ЭТО ТО, ЧТО ОНА "ПО ВНЕШНЕМУ ВИДУ СЛУЧАЙНАЯ". тОЧНЫЕ
МАТЕМАТИЧЕСКИЕ ОПРЕДЕЛЕНИЯ СЛУЧАЙНОСТИ ДАЮТСЯ В~\S~3.5. вЫРАБОТАННЫЕ
ДЕТЕРМИНИСТСКИМИ МЕТОДАМИ СЛУЧАЙНЫЕ ЧИСЛА ОКАЗАЛИСЬ ПРИГОДНЫМИ ПОЧТИ ДЛЯ
ВСЕХ ПРИЛОЖЕНИЙ (ХОТЯ, КОНЕЧНО, ОНИ НЕ МОГУТ ЗАМЕНИТЬ ERNIE В ЛОТЕРЕЯХ).

оДНАКО ПЕРВОНАЧАЛЬНЫЙ "МЕТОД СЕРЕДИНЫ КВАДРАТА" ФОН нЕЙМАНА ОКАЗАЛСЯ
СРАВНИТЕЛЬНО СКУДНЫМ ИСТОЧНИКОМ СЛУЧАЙНЫХ ЧИСЕЛ. нЕДОСТАТОК ЕГО
ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ ИМЕЮТ ТЕНДЕНЦИЮ ПРЕВРАЩАТЬСЯ В
КОРОТКИЕ ЦИКЛЫ ПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ. нАПРИМЕР, ЕСЛИ КАКОЙ-НИБУДЬ ЧЛЕН
ПОСЛЕДОВАТЕЛЬНОСТИ ОКАЖЕТСЯ РАВНЫМ НУЛЮ, ВСЕ ПОСЛЕДУЮЩИЕ ЧЛЕНЫ ТАКЖЕ
БУДУТ НУЛЯМИ. в НАЧАЛЕ ПЯТИДЕСЯТЫХ ГОДОВ НЕКОТОРЫЕ УЧЕНЫЕ
ПРОВОДИЛИ ЭКСПЕРИМЕНТЫ С МЕТОДОМ СЕРЕДИНЫ КВАДРАТА. дЖ.~э.~фОРСАЙТ,
РАБОТАВШИЙ С ЧЕТЫРЕХЗНАЧНЫМИ (А НЕ С ДЕСЯТИЗНАЧНЫМИ) ЧИСЛАМИ, ПРОВЕРИЛ
16~ЧИСЕЛ В КАЧЕСТВЕ НАЧАЛЬНЫХ ЗНАЧЕНИЙ ПОСЛЕДОВАТЕЛЬНОСТЕЙ оКАЗАЛОСЬ,
ЧТО~12 ИЗ НИХ ПОРОЖДАЛИ ПОСЛЕДОВАТЕЛЬНОСТИ, ОКАНЧИВАЮЩИЕСЯ ЦИКЛОМ~$6100$,
$2100$, $4100$, $8100$, $6100$,~\dots, А ДВЕ ПОСЛЕДОВАТЕЛЬНОСТИ ВЫРОДИЛИСЬ
В НУЛЬ. оБШИРНЫЕ ЭКСПЕРИМЕНТЫ ПО ИССЛЕДОВАНИЮ МЕТОДА СЕРЕДИНЫ КВАДРАТА
ПРОВЕЛ н.~мЕТРОПОЛИС, ОПЕРИРОВАВШИЙ ГЛАВНЫМ ОБРАЗОМ ДВОИЧНЫМИ ЧИСЛАМИ.
рАБОТАЯ С 20-РАЗРЯДНЫМИ ЧИСЛАМИ, ОН ПОКАЗАЛ, ЧТО СУЩЕСТВУЕТ
ТРИНАДЦАТЬ РАЗЛИЧНЫХ ЦИКЛОВ, В КОТОРЫЕ МОГУТ ВЫРОДИТЬСЯ
ПОСЛЕДОВАТЕЛЬНОСТИ; ДЛИНА ПЕРИОДА САМОГО БОЛЬШОГО ИЗ НИХ РАВНА~$142$.
кАК ТОЛЬКО ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫРОЖДАЕТСЯ В НУЛЬ, ДОВОЛЬНО ЛЕГКО НАЧАТЬ
ВЫРАБОТКУ СЛУЧАЙНЫХ ЧИСЕЛ ЗАНОВО. гОРАЗДО ТРУДНЕЙ БОРОТЬСЯ
%% 17
С ДЛИННЫМИ ЦИКЛАМИ. вСЕ ЖЕ р.~фЛОЙД (СМ.~УПР.~7) ПРЕДЛОЖИЛ
ОСТРОУМНЫЙ МЕТОД, ПОЗВОЛЯЮЩИЙ ЗАРЕГИСТРИРОВАТЬ ВОЗНИКНОВЕНИЕ ЦИКЛА В
ПОСЛЕДОВАТЕЛЬНОСТИ. мЕТОД фЛОЙДА ТРЕБУЕТ НЕБОЛЬШОЙ ПАМЯТИ МАШИНЫ,
УВЕЛИЧИВАЕТ ВРЕМЯ ВЫРАБОТКИ СЛУЧАЙНОГО ЧИСЛА ВСЕГО В ТРИ РАЗА И СРАЗУ ЖЕ
СИГНАЛИЗИРУЕТ, КАК ТОЛЬКО В ПОСЛЕДОВАТЕЛЬНОСТИ ПОЯВЛЯЕТСЯ ВСТРЕЧАВШЕЕСЯ
РАНЕЕ ЧИСЛО.

тЕОРЕТИЧЕСКИЕ НЕДОСТАТКИ МЕТОДА СЕРЕДИНЫ КВАДРАТА ОБСУЖДАЮТСЯ В УПР.~9
И~10. с ДРУГОЙ СТОРОНЫ, ОТМЕТИМ, ЧТО, РАБОТАЯ С 38-РАЗРЯДНЫМИ ДВОИЧНЫМИ
ЧИСЛАМИ, н.~мЕТРОПОЛИС ОБНАРУЖИЛ ПОСЛЕДОВАТЕЛЬНОСТЬ, СОСТОЯЩУЮ
ИЗ $750\,000$~ЧЛЕНОВ, ОТЛИЧАЮЩИХСЯ ДРУГ ОТ ДРУГА. сТАТИСТИЧЕСКИЕ ТЕСТЫ
ПОДТВЕРДИЛИ СЛУЧАЙНЫЙ ХАРАКТЕР ПОЛУЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ
$750000 \times 38$~БИТОВ. эТО ПОДТВЕРЖДАЕТ, ЧТО, ПРИМЕНЯЯ МЕТОД СЕРЕДИНЫ
КВАДРАТА, \emph{МОЖНО} ПОЛУЧИТЬ ПОЛЕЗНЫЕ РЕЗУЛЬТАТЫ. тЕМ НЕ МЕНЕЕ БЕЗ
ПРЕДВАРИТЕЛЬНЫХ ТРУДОЕМКИХ ВЫЧИСЛЕНИЙ ЕМУ НЕ СТОИТ ИЗЛИШНЕ ДОВЕРЯТЬ.

мНОГИЕ ДАТЧИКИ СЛУЧАЙНЫХ ЧИСЕЛ, ПОПУЛЯРНЫЕ СЕЙЧАС, НЕДОСТАТОЧНО ХОРОШИ.
сРЕДИ ПОЛЬЗОВАТЕЛЕЙ НАМЕТИЛАСЬ ТЕНДЕНЦИЯ ИЗБЕГАТЬ ИХ ИЗУЧЕНИЯ. дОВОЛЬНО
ЧАСТО КАКОЙ-НИБУДЬ СТАРЫЙ СРАВНИТЕЛЬНО НЕУДОВЛЕТВОРИТЕЛЬНЫЙ МЕТОД
ПЕРЕДАЕТСЯ ОТ ОДНОГО ПРОГРАММИСТА К ДРУГОМУ ВСЛЕПУЮ, И СЕГОДНЯШНИЙ
ПОЛЬЗОВАТЕЛЬ УЖЕ НИЧЕГО НЕ ЗНАЕТ ОБ ЕГО НЕДОСТАТКАХ. в ЭТОЙ ГЛАВЕ МЫ
УБЕДИМСЯ, ЧТО НЕТРУДНО ИЗУЧИТЬ САМЫЕ ВАЖНЫЕ СВОЙСТВА ДАТЧИКОВ
СЛУЧАЙНЫХ ЧИСЕЛ И НАУЧИТЬСЯ ПРИМЕНЯТЬ ЭТИ ЗНАНИЯ.

иЗОБРЕСТИ ПРОСТОЙ ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ НЕ ТАК ЛЕГКО. нЕСКОЛЬКО ЛЕТ НАЗАД
ЭТОТ ФАКТ ПРОИЗВЕЛ НА АВТОРА БОЛЬШОЕ ВПЕЧАТЛЕНИЕ. оН ТОГДА ПЫТАЛСЯ
СОЗДАТЬ ФАНТАСТИЧЕСКИ ХОРОШИЙ ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ НА ОСНОВЕ
СЛЕДУЮЩЕГО СВОЕОБРАЗНОГО МЕТОДА.

\alg K.(дАТЧИК "СВЕРХСЛУЧАЙНЫХ" ЧИСЕЛ.) с ПОМОЩЬЮ ЭТОГО АЛГОРИТМА ДАННОЕ
ДЕСЯТИЗНАЧНОЕ ДЕСЯТИЧНОЕ ЧИСЛО~$X$ МОЖНО ПРЕОБРАЗОВАТЬ В ДРУГОЕ ЧИСЛО,
КОТОРОЕ, КАК ПРЕДПОЛАГАЕТСЯ, ЯВЛЯЕТСЯ СЛЕДУЮЩИМ ЧЛЕНОМ СЛУЧАЙНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ. кАЗАЛОСЬ БЫ, АЛГОРИТМ ПОЗВОЛЯЕТ ВЫРАБОТАТЬ ДОСТАТОЧНО
СЛУЧАЙНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ, НО ВЫЯСНИЛОСЬ, ЧТО ЭТО СОВСЕМ НЕ ТАК.
пРИЧИНЫ НЕУДАЧИ РАЗБИРАЮТСЯ НИЖЕ. (чИТАТЕЛЮ НЕТ НУЖДЫ СЛИШКОМ ВНИКАТЬ В
ДЕТАЛИ. дОСТАТОЧНО УБЕДИТЬСЯ В БОЛЬШОЙ СЛОЖНОСТИ АЛГОРИТМА.)

\st[вЫБРАТЬ ЧИСЛО ИТЕРАЦИЙ.] уСТАНОВИТЬ~$Y\asg\floor{X/10^9}$, ЗАДАВ ЕГО
РАВНЫМ СТАРШЕЙ ЦИФРЕ ЧИСЛА~$X$. (мЫ ПОВТОРИМ $Y+1$~РАЗ ШАГИ С~\stp{2}
ПО~\stp{13} ВКЛЮЧИТЕЛЬНО. дРУГИМИ СЛОВАМИ, СЛУЧАЙНОЕ ЧИСЛО БУДЕТ
ВЫЧИСЛЯТЬСЯ \emph{СЛУЧАЙНОЕ} ЧИСЛО РАЗ.)

\st[вЫБРАТЬ СЛУЧАЙНЫЙ ШАГ.] уСТАНОВИТЬ~$Z\asg\floor{X/10^8}\bmod 10$,
Т.~Е.~ПРИСВОИТЬ~$Z$ ЗНАЧЕНИЕ, РАВНОЕ ВТОРОЙ ПО СТАРШИНСТВУ ЦИФРЕ ЧИСЛА~$X$.
пЕРЕЙТИ К ВЫПОЛНЕНИЮ ШАГА~\stp{$(3+Z)$}.
%% 18
(дРУГИМИ СЛОВАМИ, ДАЛЕЕ МЫ ВЫПОЛНЯЕМ \emph{СЛУЧАЙНО} ВЫБРАННЫЙ ШАГ ПРОГРАММЫ!)

\st[оБЕСПЕЧИТЬ~$X\ge 5\cdot 10^9$.] еСЛИ~$X<5\cdot 10^9$, ТО
УСТАНОВИТЬ~$X\asg X+5\cdot 10^9$.

\st[сЕРЕДИНА КВАДРАТА.] зАМЕНИТЬ~$X$ ЧИСЛОМ~$\floor{X^2/10^5}\bmod 10^{10}$,
Т.~Е.\ СЕРЕДИНОЙ КВАДРАТА ЧИСЛА~$X$.

\st[уМНОЖИТЬ.] зАМЕНИТЬ~$X$ НА~$(1001001001 X) \bmod 10^{10}$.

\st[пСЕВДОДОПОЛНЕНИЕ.] еСЛИ~$X<10^8$, ТО УСТАНОВИТЬ~$X\asg X+9814055677$,
В ПРОТИВНОМ СЛУЧАЕ~$X\asg 10^{10}-X$.

\st[пЕРЕСТАВИТЬ ПОЛОВИНКИ.] пОМЕНЯТЬ МЕСТАМИ $5$~СТАРШИХ И $5$~МЛАДШИХ
ЦИФР, Т.~Е.\
УСТАНОВИТЬ~$X\asg 10^5 \floor{X \bmod 10^5}+\floor{X/10^5}$, ИЛИ,
ПО-ДРУГОМУ, ВЗЯТЬ СРЕДНИЕ $10$~ЦИФР ЧИСЛА~$(10^{10}+1)X$.

\st[уМНОЖИТЬ.] (сМ.~ШАГ~\stp{5}.)

\st[уМЕНЬШИТЬ ЦИФРЫ.] уМЕНЬШИТЬ НА ЕДИНИЦУ КАЖДУЮ ОТЛИЧНУЮ ОТ НУЛЯ ЦИФРУ
ЧИСЛА~$X$ (В ДЕСЯТИЧНОМ ПРЕДСТАВЛЕНИИ).

\st[мОДИФИЦИРОВАТЬ НА~$99999$.] еСЛИ~$X<10^5$, ТО
УСТАНОВИТЬ~$X\asg X^2+99999$, В ПРОТИВНОМ СЛУЧАЕ~$X\asg X-99999$.

\st[нОРМАЛИЗОВАТЬ.] (зДЕСЬ~$X$ НЕ МОЖЕТ БЫТЬ РАВНЫМ НУЛЮ.) еСЛИ~$X<10^9$,
ТО УСТАНОВИТЬ~$X\asg 10X$ И ПОВТОРИТЬ ЭТОТ ШАГ.

\st[мОДИФИЦИРОВАННАЯ СЕРЕДИНА КВАДРАТА.] зАМЕНИТЬ~$X$
НА~$\floor{X(X-1)/10^5}\bmod 10^{10}$, Т.~Е.\ ВЗЯТЬ СРЕДНИЕ 10~ЦИФР ЧИСЛА~$X(X-1)$.

\st[пОВТОРИТЬ?] еСЛИ~$Y>0$, ТО УМЕНЬШИТЬ~$Y$ НА~$1$ И ВЕРНУТЬСЯ НА
ШАГ~\stp{2}. еСЛИ~$Y=0$, АЛГОРИТМ ЗАВЕРШЕН, ПРИЧЕМ ТЕКУЩЕЕ ЗНАЧЕНИЕ~$X$
СЧИТАЕТСЯ ИСКОМЫМ СЛУЧАЙНЫМ ЧИСЛОМ.
\algend
(хОТЕЛОСЬ НАПИСАТЬ НАСТОЛЬКО СЛОЖНУЮ ПРОГРАММУ, РЕАЛИЗУЮЩУЮ ОПИСАННЫЙ ВЫШЕ
АЛГОРИТМ, ЧТОБЫ ЧЕЛОВЕК, ЧИТАЮЩИЙ ЕЕ ТЕКСТ, НЕ МОГ БЫ БЕЗ ОБЎЯСНЕНИЙ
ДОГАДАТЬСЯ, ЧТО ЖЕ В НЕЙ ДЕЛАЕТСЯ.)

уЧИТЫВАЯ ВСЕ МЕРЫ ПРЕДОСТОРОЖНОСТИ, ПРИНЯТЫЕ В АЛГОРИТМЕ~K, НЕ КАЖЕТСЯ
ЛИ ВПОЛНЕ ПРАВДОПОДОБНЫМ, ЧТО С ЕГО ПОМОЩЬЮ МОЖНО ПОЛУЧИТЬ БЕСКОНЕЧНОЕ
МНОЖЕСТВО АБСОЛЮТНО СЛУЧАЙНЫХ ЧИСЕЛ? нЕТ! в ДЕЙСТВИТЕЛЬНОСТИ, КАК ТОЛЬКО
ЭТОТ АЛГОРИТМ БЫЛ РЕАЛИЗОВАН НА эвм, ПОЧТИ СРАЗУ ЖЕ ИТЕРАЦИИ СОШЛИСЬ К
ЧИСЛУ~$6065038420$, КОТОРОЕ, В РЕЗУЛЬТАТЕ НЕВЕРОЯТНОГО СОВПАДЕНИЯ,
ПРЕОБРАЗУЕТСЯ САМО В СЕБЯ (СМ.~ТАБЛ.~1). пРИ ДРУГОМ НАЧАЛЬНОМ ЗНАЧЕНИИ
ПОСЛЕДОВАТЕЛЬНОСТЬ, НАЧИНАЯ С ЧЛЕНА С НОМЕРОМ~$7401$, ПОВТОРЯЕТСЯ С ДЛИНОЙ
ПЕРИОДА~$3178$.

мОРАЛЬ ЭТОЙ ИСТОРИИ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО \emph{СЛУЧАЙНЫЕ ЧИСЛА НЕЛЬЗЯ
ВЫРАБАТЫВАТЬ С ПОМОЩЬЮ СЛУЧАЙНО ВЫБРАННОГО АЛГОРИТМА.} нУЖНА КАКАЯ-НИБУДЬ
ТЕОРИЯ.

в ЭТОЙ ГЛАВЕ МЫ РАССМОТРИМ МЕТОДЫ ВЫРАБОТКИ СЛУЧАЙНЫХ ЧИСЕЛ, ПРЕВОСХОДЯЩИЕ
МЕТОД СЕРЕДИНЫ КВАДРАТА И АЛГОРИТМ~K В ТОМ ОТНОШЕНИИ, ЧТО ДЛЯ НИХ МОЖНО
ТЕОРЕТИЧЕСКИ ГАРАНТИРОВАТЬ
%% 19
\htable{тАБЛИЦА~1}%
{кОЛОССАЛЬНОЕ СОВПАДЕНИЕ: ЧИСЛО 6065038420 ПРЕОБРАЗУЕТСЯ В СЕБЯ С ПОМОЩЬЮ АЛГОРИТМА~K}%
{\strut #\bskip\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip&\vrule\bskip#\hfil&\bskip$#$\hfil\bskip&\bskip$#$\hfil\bskip\cr
шАГ & \hbox{$X$ (В КОНЦЕ ШАГА)} \span & шАГ & \hbox{$X$ (В КОНЦЕ ШАГА)}\span \cr
K1  & 6065038420 &     & K9  & 1107855700 \cr
K3  & 6065038420 &     & K10 & 1107755701 \cr
K4  & 6910360760 &     & K11 & 1107755701 \cr
K5  & 8031120760 &     & K12 & 1226919902 & Y=3\cr
K6  & 1968879240 &     & K5  & 0048821902 \cr
K7  & 7924019688 &     & K6  & 9862877579 \cr
K8  & 9631707688 &     & K7  & 7757998628 \cr
K9  & 8520606577 &     & K8  & 2384626628 \cr
K10 & 8520506578 &     & K9  & 1273515517 \cr
K11 & 8520506578 &     & K10 & 1273415518 \cr
K12 & 0323372207 & Y=6 & K11 & 1273415518 \cr
K6  & 9676627793 &     & K12 & 5870802097 & Y=2\cr
K7  & 2779396766 &     & K11 & 5870802097 \cr
K8  & 4942162766 &     & K12 & 3172562687 & Y=1\cr
K9  & 3831051655 &     & K4  & 1540029446 \cr
K10 & 3830951656 &     & K5  & 7015475446 \cr
K11 & 3830951656 &     & K6  & 2984524554 \cr
K12 & 1905867781 & Y=5 & K7  & 2455429845 \cr
K12 & 3319967479 & Y=4 & K8  & 2730274845 \cr
KБ  & 6680032521 &     & K9  & 1620163734 \cr
K7  & 3252166800 &     & K10 & 1620063735 \cr
K8  & 2218966800 &     & K11 & 1620063735 \cr
    &            &     & K12 & 6065038420 & Y=0 \cr
}
ВЫПОЛНЕНИЕ ОПРЕДЕЛЕННЫХ СВОЙСТВ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ И ОТСУТСТВИЕ
ВЫРОЖДЕНИЯ. бУДУТ ИЗЛОЖЕНЫ НЕКОТОРЫЕ ДЕТАЛИ, ОБЕСПЕЧИВАЮЩИЕ ТАКОЕ
СЛУЧАЙНОЕ ПОВЕДЕНИЕ, И УДЕЛЕНО ВНИМАНИЕ ТЕХНИКЕ ПРИМЕНЕНИЯ СЛУЧАЙНЫХ ЧИСЕЛ.
в ЧАСТНОСТИ, НАПРИМЕР, БУДЕТ ПОКАЗАНО, КАК ТАСОВАТЬ КАРТЫ С ПОМОЩЬЮ
ПРОГРАММЫ ДЛЯ~эвм.

\excercises
\rex[20] пРЕДПОЛОЖИМ, ВЫ ХОТИТЕ, НЕ ИСПОЛЬЗУЯ эвм, ПОЛУЧИТЬ
СЛУЧАЙНУЮ ДЕСЯТИЧНУЮ ЦИФРУ. кАКОЙ ИЗ ПЕРЕЧИСЛЕННЫХ НИЖЕ МЕТОДОВ ВЫ ПРЕДПОЧТЕТЕ?

a)~оТКРОЙТЕ ТЕЛЕФОННЫЙ СПРАВОЧНИК В ПРОИЗВОЛЬНОМ МЕСТЕ (Т.~Е.\ ТКНИТЕ ПАЛЬЦЕМ
КУДА УГОДНО) И ВОЗЬМИТЕ МЛАДШУЮ ЦИФРУ ПЕРВОГО ПОПАВШЕГОСЯ
НОМЕРА НА ВЫБРАННОЙ ВАМИ СТРАНИЦЕ.

b)~сДЕЛАЙТЕ ТО ЖЕ САМОЕ, НО ВОСПОЛЬЗУЙТЕСЬ МЛАДШЕЙ ЦИФРОЙ НОМЕРА
\emph{СТРАНИЦЫ.}

%% 20
c)~бРОСЬТЕ КОСТЬ В ФОРМЕ ПРАВИЛЬНОГО ИКОСАЭДРА, КАЖДАЯ ИЗ ДВАДЦАТИ ГРАНЕЙ
КОТОРОГО ПОМЕЧЕНА ЦИФРАМИ~$0$, $0$, $1$, $1$,~\dots, $9$, $9$. зАПИШИТЕ
ЦИФРУ, КОТОРОЙ БУДЕТ ПОМЕЧЕНА ВЕРХНЯЯ ГРАНЬ ОСТАНОВИВШЕЙСЯ КОСТИ. (дЛЯ
ЭКСПЕРИМЕНТА РЕКОМЕНДУЕТСЯ ПОЛЬЗОВАТЬСЯ СТОЛОМ С ТВЕРДОЙ ОБИТОЙ СУКНОМ ПОВЕРХНОСТЬЮ.)

d)~пОСТАВЬТЕ НА МИНУТУ РЯДОМ С ИСТОЧНИКОМ РАДИОАКТИВНОГО ИЗЛУЧЕНИЯ СЧЕТЧИК
гЕЙГЕРА (ПРИМИТЕ МЕРЫ ПРЕДОСТОРОЖНОСТИ). вОСПОЛЬЗУЙТЕСЬ МЛАДШЕЙ ЦИФРОЙ
ЧИСЛА ОТСЧЕТОВ, ПОКАЗАННОГО СЧЕТЧИКОМ. (пРЕДПОЛАГАЕТСЯ, ЧТО ГЕЙГЕРОВСКИЙ
СЧЕТЧИК ПОКАЗЫВАЕТ ЧИСЛО ОТСЧЕТОВ В ДЕСЯТИЧНОМ ВИДЕ И ПЕРЕД НАЧАЛОМ
ЭКСПЕРИМЕНТА ОН БЫЛ УСТАНОВЛЕН НА НУЛЬ.)

e)~вЗГЛЯНИТЕ НА СВОИ ЧАСЫ И, ЕСЛИ СЕКУНДНАЯ СТРЕЛКА НАХОДИТСЯ
МЕЖДУ ЧИСЛАМИ~$6n$ И~$6(n+1)$, ВЫБЕРИТЕ ЦИФРУ~$n$.

f)~пОПРОСИТЕ ПРИЯТЕЛЯ ЗАДУМАТЬ СЛУЧАЙНУЮ ЦИФРУ И ПУСТЬ ОН ВАМ ЕЕ НАЗОВЕТ.

g)~пУСТЬ ТО ЖЕ САМОЕ СДЕЛАЕТ ВАШ НЕДРУГ.

h)~пРЕДПОЛОЖИМ, ЧТО В ЗАБЕГЕ УЧАСТВУЕТ $10$~АБСОЛЮТНО НЕИЗВЕСТНЫХ
ВАМ ЛОШАДЕЙ. сОВЕРШЕННО ПРОИЗВОЛЬНО ПРОНУМЕРУЙТЕ ИХ ЦИФРАМИ ОТ~$0$
ДО~$9$. вОСПОЛЬЗУЙТЕСЬ НОМЕРОМ ПОБЕДИТЕЛЯ ЗАБЕГА.

\ex[м22] кАКОВА ВЕРОЯТНОСТЬ ОБНАРУЖИТЬ РОВНО $100\,000$~ЭКЗЕМПЛЯРОВ ЛЮБОЙ
ЗАДАННОЙ ЗАРАНЕЕ ЦИФРЫ В СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, СОСТОЯЩЕЙ ИЗ
$1\,000\,000$~ДЕСЯТИЧНЫХ ЦИФР?

\ex[10] кАКОЕ ЧИСЛО ПОЛУЧИТСЯ ПОСЛЕ ПРИМЕНЕНИЯ МЕТОДА СЕРЕДИНЫ КВАДРАТА
К ЧИСЛУ~$1010101010$?

\ex[10] пОЧЕМУ ПРИ ВЫПОЛНЕНИИ ШАГА~K11 АЛГОРИТМА~K ЗНАЧЕНИЕ~$X$ НЕ МОЖЕТ
БЫТЬ РАВНЫМ НУЛЮ? чТО ПРОИЗОШЛО БЫ С АЛГОРИТМОМ, ЕСЛИ БЫ~$х$ МОГЛО БЫТЬ НУЛЕМ?

\ex[15] оБЎЯСНИТЕ, ПОЧЕМУ В ЛЮБОМ СЛУЧАЕ НЕЛЬЗЯ ОЖИДАТЬ
ПОЛУЧЕНИЯ "БЕСКОНЕЧНОГО МНОЖЕСТВА" СЛУЧАЙНЫХ ЧИСЕЛ С ПОМОЩЬЮ АЛГОРИТМА~K
(ДАЖЕ ЕСЛИ БЫ НЕ ПРОИЗОШЛО СОВПАДЕНИЯ, ПРИВЕДЕННОГО В ТАБЛ.~1), СЧИТАЯ
ЗАРАНЕЕ ИЗВЕСТНЫМ ТОТ ФАКТ, ЧТО ЛЮБАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, ВЫРАБОТАННАЯ С
ИСПОЛЬЗОВАНИЕМ ЭТОГО АЛГОРИТМА, В КОНЦЕ КОНЦОВ СТАНЕТ ПЕРИОДИЧЕСКОЙ?

\rex[м20] пРЕДПОЛОЖИМ, ЧТО МЫ ХОТИМ ВЫРАБОТАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ
ЧИСЕЛ~$X_0$, $X_1$, $X_2$,~\dots{} В ИНТЕРВАЛЕ~$0\le X_n < m$.
пУСТЬ~$f(x)$---ЛЮБАЯ ФУНКЦИЯ, ТАКАЯ, ЧТО ЕСЛИ~$0 \le x < m$, ТО~$0\le f(x)<m$.
рАССМОТРИМ ПОСЛЕДОВАТЕЛЬНОСТЬ, ПОЛУЧЕННУЮ С ПОМОЩЬЮ
СООТНОШЕНИЯ~$X_{n+1}=f(X_n)$. (пРИМЕРАМИ ЯВЛЯЮТСЯ МЕТОД СЕРЕДИНЫ КВАДРАТА
И АЛГОРИТМ~к.)

a)~пОКАЖИТЕ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ В КОНЦЕ КОНЦОВ СТАНОВИТСЯ
ПЕРИОДИЧЕСКОЙ, Т.~Е.\ СУЩЕСТВУЮТ ТАКИЕ ЧИСЛА~$\lambda$ И~$\mu$, ЧТО
ЗНАЧЕНИЯ~$X_0$, $X_1$,~\dots, $X_\mu$,~\dots, $X_{\mu+\lambda-1}$ РАЗЛИЧНЫ,
НО~$X_{n+\lambda}=X_n$,  КОГДА~$n\ge \mu$. нАЙДИТЕ МАКСИМАЛЬНОЕ И
МИНИМАЛЬНОЕ ВОЗМОЖНЫЕ ЗНАЧЕНИЯ~$\mu$ И~$\lambda$.

b)~пОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ~$n>0$, ТАКОЕ, ЧТО~$X_n=X_{2n}$;
НАИМЕНЬШЕЕ ЗНАЧЕНИЕ ЭТОГО~$n$ ЛЕЖИТ В ИНТЕРВАЛЕ~$\mu \le n \le \mu+\lambda$.
зНАЧЕНИЕ~$X_n$ ЯВЛЯЕТСЯ ЕДИНСТВЕННЫМ В ТОМ СМЫСЛЕ, ЧТО
ЕСЛИ~$X_n=X_{2n}$ И~$X_r=X_{2r}$, ТО~$X_r=X_n$ (СЛЕДОВАТЕЛЬНО, $r-n$
КРАТНО~$\lambda$).

\rex[20] пРИМЕНИТЕ РЕЗУЛЬТАТЫ ПРЕДЫДУЩЕГО УПРАЖНЕНИЯ, ЧТОБЫ
ПОСТРОИТЬ ПРАКТИЧНЫЙ АЛГОРИТМ ВЫРАБОТКИ СЛУЧАЙНЫХ ЧИСЕЛ, ДОПОЛНЯЮЩИЙ
ДАТЧИК ТИПА~$X_{n+1}=f(X_n)$. вАШ АЛГОРИТМ ДОЛЖЕН: a)~ОБЛАДАТЬ СВОЙСТВОМ
ПРИОСТАНАВЛИВАТЬ ВЫРАБОТКУ СЛУЧАЙНЫХ ЧИСЕЛ ПОСЛЕДОВАТЕЛЬНОСТИ, КАК
ТОЛЬКО ПОВТОРЯЕТСЯ РАНЕЕ ВСТРЕЧАВШЕЕСЯ ЧИСЛО, b)~ВЫРАБОТАТЬ ПО МЕНЬШЕЙ
МЕРЕ~$\lambda$ ЭЛЕМЕНТОВ ПЕРЕД ОСТАНОВКОЙ, ХОТЯ ЗНАЧЕНИЕ~$\lambda$ ЗАРАНЕЕ
НЕИЗВЕСТНО, И~c)~ИСПОЛЬЗОВАТЬ НЕБОЛЬШУЮ ПАМЯГЬ (Т.~Е.\ НЕ РАЗРЕШАЕТСЯ.
ПРОСТО ЗАПОМИНАТЬ ВСЕ ВЫЧИСЛЕННЫЕ ПОСЛЕДОВАТЕЛЬНЫЕ ЗНАЧЕНИЯ).

\ex[28] пОЛНОСТЬЮ ПРОВЕРЬТЕ МЕТОД СЕРЕДИНЫ КВАДРАТА ДЛЯ СЛУЧАЯ
ДВУЗНАЧНЫХ ЧИСЕЛ. a)~мЫ МОЖЕМ НАЧАТЬ С ЛЮБОГО ИЗ 100~ВОЗМОЖНЫХ
ЗНАЧЕНИЙ~$00$, $01$,~\dots, $99$. в СКОЛЬКИХ СЛУЧАЯХ МЫ В КОНЦЕ КОНЦОВ
ПРИДЕМ К ПОВТОРЕНИЮ ЦИКЛА~$00$, $00$,~\dots? [\emph{пРИМЕР.} нАЧАВ С~$43$,
МЫ ПОЛУЧИМ ПОСЛЕДОВАТЕЛЬНОСТЬ~$43$, $84$, $05$, $02$, $00$, $00$,
$00$,~$\ldots\,$.] b)~сКОЛЬКО МОЖЕТ ПОЛУЧИТЬСЯ РАЗЛИЧНЫХ ЦИКЛОВ? кАКОВА ДЛИНА
ПЕРИОДА САМОГО ДЛИННОГО ЦИКЛА? c)~кАКОЕ НАЧАЛЬНОЕ ЗНАЧЕНИЕ
%% 21
ПОЗВОЛЯЕТ ПОЛУЧИТЬ САМУЮ ДЛИННУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕПОВТОРЯЮЩИХСЯ ЭЛЕМЕНТОВ?

\ex[м14] дОКАЖИТЕ, ЧТО МЕТОД СЕРЕДИНЫ КВАДРАТА, ИСПОЛЬЗУЮЩИЙ
$2n\hbox{-ЗНАЧНЫЕ}$ ЧИСЛА С ОСНОВАНИЕМ~$b$, ИМЕЕТ СЛЕДУЮЩИЙ НЕДОСТАТОК:
НАЧИНАЯ С ЧИСЛА~$X$, У КОТОРОГО СТАРШИЕ $n$~ЦИФР РАВНЫ НУЛЮ, ВСЕ
ПОСЛЕДУЮЩИЕ ЭЛЕМЕНТЫ ПОСЛЕДОВАТЕЛЬНОСТИ СТАНОВЯТСЯ ВСЕ МЕНЬШЕ И МЕНЬШЕ,
ПОКА НЕ ОБРАТЯТСЯ В НУЛЬ.

\ex[м16] сОХРАНИВ ПРЕДПОЛОЖЕНИЯ ПРЕДЫДУЩЕГО УПРАЖНЕНИЯ, ЧТО МОЖНО СКАЗАТЬ
О ПОСЛЕДОВАТЕЛЬНОСТИ ЭЛЕМЕНТОВ, СЛЕДУЮЩИХ ЗА ЧИСЛОМ~$X$, У
КОТОРОГО \emph{САМЫЕ МЛАДШИЕ} $n$~ЦИФР РАВНЫ НУЛЮ? чТО, ЕСЛИ МЛАДШИЕ
$(n+1)$~ЦИФР РАВНЫ НУЛЮ?

\rex[м26] рАССМОТРИМ СЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ,
ВЫРАБАТЫВАЕМЫЕ ДАТЧИКАМИ ТИПА ОПИСАННОГО В УПР.~6. еСЛИ МЫ ВЫБИРАЕМ~$f(x)$
И~$X_0$ СЛУЧАЙНО И ПРЕДПОЛАГАЕМ, ЧТО ЛЮБЫЕ ИЗ $m^m$~ВОЗМОЖНЫХ
ФУНКЦИЙ~$f(x)$ И $m$~НАЧАЛЬНЫХ ЗНАЧЕНИЙ~$X_0$ РАВНОВЕРОЯТНЫ, ТО КАКОВА
ВЕРОЯТНОСТЬ ТОГО, ЧТО В КОНЦЕ КОНЦОВ ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫРОДИТСЯ, ОБРАЗУЯ
ЦИКЛ С ДЛИНОЙ ПЕРИОДА~$\lambda=1$?

[\emph{зАМЕЧАНИЕ.} пРЕДПОЛОЖЕНИЯ, ПРИНЯТЫЕ В ЭТОЙ ЗАДАЧЕ, ДАЮТ
ВОЗМОЖНОСТЬ ВПОЛНЕ ЕСТЕСТВЕННЫМ ОБРАЗОМ ЗАДУМАТЬСЯ О "СЛУЧАЙНОМ" ДАТЧИКЕ
СЛУЧАЙНЫХ ЧИСЕЛ ПОДОБНОГО ТИПА. мОЖНО ОЖИДАТЬ, ЧТО МЕТОД, ПОДОБНЫЙ
АЛГОРИТМУ~K, ДОЛЖЕН БЫТЬ ПОХОЖИМ НА СРЕДНИЙ ДАТЧИК, РАССМОТРЕННЫЙ ЗДЕСЬ.
рЕШЕНИЕ ЗАДАЧИ ДАЕТ МЕРУ ТОГО, НАСКОЛЬКО "КОЛОССАЛЬНО" НА САМОМ ДЕЛЕ
СОВПАДЕНИЕ, ПРИВЕДЕННОЕ В ТАБЛ.~1.]

\rex[м31] иСПОЛЬЗУЯ ПРЕДПОЛОЖЕНИЯ ПРЕДЫДУЩЕГО УПРАЖНЕНИЯ, НАЙДИТЕ СРЕДНЮЮ
ДЛИНУ ЦИКЛА, КОТОРЫЙ ОБРАЗУЕТСЯ В ПОСЛЕДОВАТЕЛЬНОСТЯХ. кАКОЙ СРЕДНЕЙ ДЛИНЫ
ДОСТИГАЕТ ПОСЛЕДОВАТЕЛЬНОСТЬ, ПРЕЖДЕ ЧЕМ НАЧАТЬ ЦИКЛИТЬСЯ? (в ОБОЗНАЧЕНИЯХ
УПР.~6 МЫ ХОТИМ ОПРЕДЕЛИТЬ СРЕДНИЕ ЗНАЧЕНИЯ~$\lambda$ И~$\mu+\lambda$.)

\ex[м42] еСЛИ~$f(x)$ ВЫБИРАЕТСЯ СЛУЧАЙНО В СМЫСЛЕ УПР.~11, КАКОВА
СРЕДНЯЯ ДЛИНА \emph{САМОГО ДЛИННОГО} ЦИКЛА, ПОЛУЧЕННОГО В РЕЗУЛЬТАТЕ
ИЗМЕНЕНИЯ НАЧАЛЬНОГО ЗНАЧЕНИЯ~$X_0$? [\emph{зАМЕЧАНИЕ.} оТВЕТ ИЗВЕСТЕН
ДЛЯ СПЕЦИАЛЬНОГО СЛУЧАЯ, КОГДА В КАЧЕСТВЕ ФУНКЦИИ~$f(x)$ РАССМАТРИВАЕТСЯ
ПЕРЕСТАНОВКА; СМ. УПР.~1.3.3-23.]

\ex[м38] еСЛИ~$f(x)$ ВЫБИРАЕТСЯ СЛУЧАЙНО В СМЫСЛЕ УПР.~11, КАКОВО СРЕДНЕЕ
ЧИСЛО РАЗЛИЧНЫХ ЦИКЛОВ, ПОЛУЧАЕМЫХ В РЕЗУЛЬТАТЕ ИЗМЕНЕНИЯ НАЧАЛЬНОГО
ЗНАЧЕНИЯ? (сР.~С~УПР.~8(b).)

\ex[м15] еСЛИ~$f(x)$ ВЫБИРАЕТСЯ СЛУЧАЙНО В СМЫСЛЕ УПР.~11, КАКОВА
ВЕРОЯТНОСТЬ ТОГО, ЧТО НИ ОДИН ИЗ ЦИКЛОВ НЕ ИМЕЕТ ДЛИНЫ~$1$,
БЕЗОТНОСИТЕЛЬНО К ВЫБОРУ~$X_0$?

\ex[15] пОСЛЕДОВАТЕЛЬНОСТЬ, ВЫРАБАТЫВАЕМАЯ С ПОМОЩЬЮ МЕТОДА, ОПИСАННОГО
В УПР.~6, ДОЛЖНА НАЧАТЬ ПОВТОРЯТЬСЯ САМОЕ ПОЗДНЕЕ ПОСЛЕ ВЫРАБОТКИ
$m$~ЗНАЧЕНИЙ. пРЕДПОЛОЖИМ, ЧТО МЫ ОБОБЩИЛИ МЕТОД ТАК, ЧТО $X_{n+1}$~ТЕПЕРЬ
ЗАВИСИТ НЕ ТОЛЬКО ОТ~$X_n$, НО И ОТ~$X_{n-1}$. фОРМАЛЬНО ПУСТЬ~$f(x, y)$
БУДЕТ ТАКАЯ ФУНКЦИЯ, ЧТО ЕСЛИ~$0\le x$, $y<m$, ТО~$0\le f(x, y)< m$.
нАЧИНАЕМ СТРОИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ С ПРОИЗВОЛЬНОГО ВЫБОРА~$X_0$ И~$X_1$.
зАТЕМ ПОЛАГАЕМ
$$
X_{n+1}=f(X_n, X_{n-1}) \rem{ДЛЯ $n>0$.}
$$
кАКУЮ МАКСИМАЛЬНУЮ ДЛИНУ ПЕРИОДА МОЖНО ПОЛУЧИТЬ В ЭТОМ СЛУЧАЕ?

\ex[10] оБОБЩИТЕ ИДЕЮ ПРЕДЫДУЩЕГО УПРАЖНЕНИЯ ТАК, ЧТОБЫ $X_{n+1}$~ЗАВИСЕЛО
ОТ $k$~ПРЕДЫДУЩИХ ЗНАЧЕНИЙ ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТИ.

\ex[м22] пРИДУМАЙТЕ МЕТОД, АНАЛОГИЧНЫЙ ПРЕДЛОЖЕННОМУ В УПР.~7,
ДЛЯ ОБНАРУЖЕНИЯ ЦИКЛА ДАТЧИКА СЛУЧАЙНЫХ ЧИСЕЛ ОБЩЕГО ВИДА,
РАССМОТРЕННОГО В ПРЕДЫДУЩЕМ УПРАЖНЕНИИ.

\ex[м50] рЕШИТЕ ЗАДАЧИ, ПОСТАВЛЕННЫЕ В УПР.~11--15, ДЛЯ БОЛЕЕ
ОБЩЕГО СЛУЧАЯ, КОГДА $X_{n+1}$~ЗАВИСИТ ОТ ПРЕДЫДУЩИХ $k$~ЭЛЕМЕНТОВ
ПОСЛЕДОВАТЕЛЬНОСТИ. кАЖДАЯ ИЗ~$m^{m^k}$ ФУНКЦИЙ~$f(x_1, x_2,~\ldots, x_k)$
ДОЛЖНА РАССМАТРИВАТЬСЯ КАК РАВНОВЕРОЯТНАЯ. [\emph{зАМЕЧАНИЕ.} кОЛИЧЕСТВО
ФУНКЦИЙ, ДАЮЩИХ \emph{МАКСИМАЛЬНЫЙ} ПЕРИОД, ПРИВОДИТСЯ В УПР.~2.3.4.2-23.]

%% 22
\subchap{выработка равномерно распределенных случайных чисел} % 3.2
в ЭТОМ ПАРАГРАФЕ МЫ РАССМОТРИМ МЕТОДЫ ПОЛУЧЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ
СЛУЧАЙНЫХ ДРОБЕЙ, Т.~Е.\ СЛУЧАЙНЫХ \emph{ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$U_n$,
РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ.} тАК КАК В
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО ВСЕГДА ПРЕДСТАВЛЯЕТСЯ С
ОГРАНИЧЕННОЙ ТОЧНОСТЬЮ, ФАКТИЧЕСКИ МЫ БУДЕМ ГЕНЕРИРОВАТЬ ЦЕЛЫЕ ЧИСЛА~$X_n$
В ИНТЕРВАЛЕ ОТ~$0$ ДО НЕКОТОРОГО~$m$. тОГДА ДРОБЬ
$$
U_n=X_n/m
\eqno(1)
$$
ПОПАДЕТ В ИНТЕРВАЛ ОТ НУЛЯ ДО ЕДИНИЦЫ. оБЫЧНО~$m$ НА ЕДИНИЦУ БОЛЬШЕ
МАКСИМАЛЬНОГО ЧИСЛА, КОТОРОЕ МОЖНО ЗАПИСАТЬ В МАШИННОМ СЛОВЕ [($m$ РАВНО
\emph{РАЗМЕРУ СЛОВА} (word size)]. пОЭТОМУ~$X_n$ МОЖНО ИНТЕРПРЕТИРОВАТЬ
(КОНСЕРВАТИВНО) КАК ЦЕЛОЕ СОДЕРЖИМОЕ МАШИННОГО СЛОВА С ДЕСЯТИЧНОЙ
ЗАПЯТОЙ, РАСПОЛОЖЕННОЙ СПРАВА, А~$U_n$ МОЖНО СЧИТАТЬ (ЛИБЕРАЛЬНО) ДРОБЬЮ,
СОДЕРЖАЩЕЙСЯ В ТОМ ЖЕ СЛОВЕ, С ЗАПЯТОЙ В КРАЙНЕЙ ЛЕВОЙ ПОЗИЦИИ.

\subsubchap{лИНЕЙНЫЙ КОНГРУЭНТНЫЙ МЕТОД} % 3.2.1
нАИЛУЧШИЕ ИЗ ИЗВЕСТНЫХ СЕГОДНЯ ДАТЧИКОВ СЛУЧАЙНЫХ ЧИСЕЛ ПРЕДСТАВЛЯЮТ СОБОЙ
ЧАСТНЫЕ СЛУЧАИ СЛЕДУЮЩЕЙ СХЕМЫ, ПРЕДЛОЖЕННОЙ д.~X.~лЕМЕРОМ В~1948~Г.\
[сМ. Proc. 2nd Symposium on Large-Scale Digital Computing Machinery
(Cambridge: Harvard University Press, 1951), 141--146.] вЫБИРАЕМ ЧЕТЫРЕ
"МАГИЧЕСКИХ ЧИСЛА":
$$
\vcenter{\halign{
$#$\hfil\bskip&#\bskip\hfil&\bskip\hfil$#$&${}#$\hfil\cr
X_0, & НАЧАЛЬНОЕ ЗНАЧЕНИЕ; & X_0&\ge 0; \cr
  a, & МНОЖИТЕЛЬ;          &   a&\ge 0; \cr
  c, & ПРИРАЩЕНИЕ;         &   c&\ge 0; \cr
  m, & МОДУЛЬ;             &   m&> X_0, m>a, m>c.\cr
}}
\eqno(1)
$$
тОГДА ИСКОМАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ СЛУЧАЙНЫХ ЧИСЕЛ~$\<X_n>$ ПОЛУЧАЕТСЯ ИЗ СООТНОШЕНИЯ
$$
X_{n+1}=(aX_n+c) \bmod m, \rem{$n\ge 0$.}
\eqno (2)
$$

оНА НАЗЫВАЕТСЯ \dfn{ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ.}
%% 23

нАПРИМЕР, ПРИ~$X_0=a=c=7$, $m=10$ ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫГЛЯДИТ ТАК:
$$
7,\; 6,\; 9,\; 0,\; 7,\; 6,\; 9,\; 0,\;~\ldots
\eqno (3)
$$
кАК ВИДНО ИЗ ПРИВЕДЕННОГО ПРИМЕРА, ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ ВСЕГДА
ОКАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ ВЫБИРАТЬ~$X_0$, $a$, $c$, $m$ ПРОИЗВОЛЬНО. в
ПОСЛЕДУЮЩИХ РАЗДЕЛАХ ЭТОЙ ГЛАВЫ БУДУТ ПОДРОБНО ИССЛЕДОВАНЫ ПРИНЦИПЫ
ВЫБОРА ЭТИХ ЗНАЧЕНИЙ.

пРИМЕР~(3) ИЛЛЮСТРИРУЕТ ТОТ ФАКТ, ЧТО КОНГРУЭНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
ВСЕГДА "ЗАЦИКЛИВАЮТСЯ", Т.~Е.\ В КОНЦЕ КОНЦОВ ЧИСЛА ОБРАЗУЮТ ЦИКЛ, КОТОРЫЙ
ПОВТОРЯЕТСЯ БЕСКОНЕЧНОЕ ЧИСЛО РАЗ. эТО СВОЙСТВО ПРИСУЩЕ ВСЕМ
ПОСЛЕДОВАТЕЛЬНОСТЯМ, ИМЕЮЩИМ ОБЩИЙ ВИД~$X_{n+1}=f(X_n)$; СМ.~УПР.~3.1-6.
пОВТОРЯЮЩИЙСЯ ЦИКЛ НАЗЫВАЕТСЯ \dfn{ПЕРИОДОМ.} дЛИНА ПЕРИОДА У
ПОСЛЕДОВАТЕЛЬНОСТИ~(3) РАВНА~$4$. рЕАЛЬНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ, КОТОРЫМИ
ПОЛЬЗУЮТСЯ, ИМЕЮТ, КОНЕЧНО, СРАВНИТЕЛЬНО БОЛЬШОЙ ПЕРИОД.

сПЕЦИАЛЬНОГО УПОМИНАНИЯ ЗАСЛУЖИВАЕТ ЧАСТНЫЙ СЛУЧАЙ~$c=0$, КОГДА ПРОЦЕСС
ВЫРАБОТКИ СЛУЧАЙНЫХ ЧИСЕЛ ПРОИСХОДИТ НЕСКОЛЬКО БЫСТРЕЕ. пОЗЖЕ МЫ УВИДИМ,
ЧТО ОГРАНИЧЕНИЕ~$c=0$ УМЕНЬШАЕТ ДЛИНУ ПЕРИОДА ПОСЛЕДОВАТЕЛЬНОСТИ, НО ПРИ
ЭТОМ ВСЕ ЕЩЕ МОЖНО ПОЛУЧИТЬ ОТНОСИТЕЛЬНО БОЛЬШОЙ ПЕРИОД. в ПЕРВОНАЧАЛЬНОМ
МЕТОДЕ лЕМЕРА БЫЛО ПРИНЯТО~$c=0$, ХОТЯ АВТОР И УПОМЯНУЛ ВОЗМОЖНОСТЬ
ИСПОЛЬЗОВАНИЯ~$c\ne 0$. иДЕЯ ПОЛУЧЕНИЯ БОЛЕЕ ДЛИННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
ЗА СЧЕТ ОБОБЩЕНИЯ~$c\ne 0$ ПРИНАДЛЕЖИТ тОМСОНУ
[{\sl Comp. J.,\/} {\bf 1} (1958), 83, 86] И НЕЗАВИСИМО рОТЕНБЕРГУ
[{\sl JACM,\/} {\bf 7} (1960), 75--77].

мНОГИМИ АВТОРАМИ ТЕРМИНЫ \dfn{МУЛЬТИПЛИКАТИВНЫЙ КОНГРУЭНТНЫЙ МЕТОД} И
\dfn{СМЕШАННЫЙ КОНГРУЭНТНЫЙ МЕТОД} ПРИМЕНЯЮТСЯ ДЛЯ ОБОЗНАЧЕНИЯ ЛИНЕЙНЫХ
КОНГРУЭНТНЫХ МЕТОДОВ С~$c=0$ И~$c\ne0$ СООТВЕТСТВЕННО.

вО ВСЕЙ ЭТОЙ ГЛАВЕ БУКВЫ~$a$, $c$, $m$, $X_0$ БУДУТ ИСПОЛЬЗОВАТЬСЯ В ТОМ
СМЫСЛЕ, КАК ЭТО ПРИНЯТО ВЫШЕ. бОЛЕЕ ТОГО, ЧТОБЫ УПРОСТИТЬ МНОГИЕ НАШИ
ФОРМУЛЫ, ОКАЗЫВАЕТСЯ ПОЛЕЗНЫМ ОПРЕДЕЛИТЬ
$$
b=a-1.
\eqno(4)
$$
мОЖНО СРАЗУ ЖЕ ОТБРОСИТЬ СЛУЧАЙ~$a=1$, ТАК КАК ПРИ ЭТОМ $X_n=(X_0+nc) \bmod m$,
И ОЧЕВИДНО, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ СЛУЧАЙНАЯ. вАРИАНТ~$a=0$
ЕЩЕ ХУЖЕ. сЛЕДОВАТЕЛЬНО, ДЛЯ ПРАКТИЧЕСКИХ ЦЕЛЕЙ МЫ МОЖЕМ ПРЕДПОЛОЖИТЬ, ЧТО
$$
a\ge 2, \qquad b \ge 1.
\eqno (5)
$$

тЕПЕРЬ МОЖНО ОБОБЩИТЬ СООТНОШЕНИЕ~(2),
$$
X_{n+k}=(a^k X_n+(a^k-1)c/b) \bmod m,
\rem{$k\ge 0$, $n\ge 0$},
\eqno (6)
$$
ВЫРАЗИВ $(n+k)\hbox{-Й}$~ЧЛЕН ПРЯМО ЧЕРЕЗ~$n\hbox{-Й}$. (сЛЕДУЕТ ОБРАТИТЬ
ВНИМАНИЕ НА ЧАСТНЫЙ СЛУЧАЙ~$n=0$.) пОСЛЕДОВАТЕЛЬНОСТЬ, СОСТАВЛЕННАЯ
%% 24
ИЗ КАЖДОГО $k\hbox{-ГО}$~ЧЛЕНА НАШЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ
ОБРАЗУЕТ ДРУГУЮ ЛИНЕЙНУЮ КОНГРУЭНТНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ С
МНОЖИТЕЛЕМ~$a^k$ И ПРИРАЩЕНИЕМ~$((a^k-1)c/b)$.

\excercises
\ex[10] в ПРИМЕРЕ~(3) ИЛЛЮСТРИРУЕТСЯ СИТУАЦИЯ, КОГДА~$X_4=X_0$, ТАК
ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ ОПЯТЬ НАЧИНАЕТСЯ СНАЧАЛА. нАЙДИТЕ ПРИМЕР ТАКОЙ
ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С~$m=10$, В КОТОРОЙ
$X_0$~ВСТРЕЧАЕТСЯ ТОЛЬКО ОДИН РАЗ.

\rex[м20] пОКАЖИТЕ, ЧТО, ЕСЛИ~$a$ И~$m$ ВЗАИМНО ПРОСТЫЕ, ЧИСЛО~$X_0$
БУДЕТ ПЕРИОДИЧЕСКИ ПОВТОРЯТЬСЯ.

\ex[м10] оБЎЯСНИТЕ, ПОЧЕМУ, ЕСЛИ~$a$ И~$m$ НЕ ЯВЛЯЮТСЯ ВЗАИМНО ПРОСТЫМИ,
ПОСЛЕДОВАТЕЛЬНОСТЬ В КАКОМ-ТО СМЫСЛЕ НЕУДАЧНАЯ И, ВЕРОЯТНО, НЕ
СЛИШКОМ СЛУЧАЙНАЯ. пОЭТОМУ, ВООБЩЕ ГОВОРЯ, МЫ БУДЕМ СТАРАТЬСЯ ВЫБИРАТЬ~$a$
И~$m$  ВЗАИМНО ПРОСТЫМИ.

\ex[11] дОКАЖИТЕ СООТНОШЕНИЕ~(6).

\ex[м20] сООТНОШЕНИЕ~(6) ВЫПОЛНЯЕТСЯ ДЛЯ~$k\ge 0$. еСЛИ ЭТО ВОЗМОЖНО,
ПОЛУЧИТЕ ФОРМУЛУ, ВЫРАЖАЮЩУЮ~$X_{n+k}$ ЧЕРЕЗ~$X_n$ И ДЛЯ
\emph{ОТРИЦАТЕЛЬНЫХ} ЗНАЧЕНИЙ~$k$.

\subsubsubchap{вЫБОР МОДУЛЯ}%3.2.1.1
сНАЧАЛА ОБСУДИМ, КАК ПРАВИЛЬНО ВЫБИРАТЬ ЧИСЛО~$m$. мЫ ХОТИМ, ЧТОБЫ
ЗНАЧЕНИЕ~$m$ БЫЛО ДОСТАТОЧНО БОЛЬШИМ, ТАК КАК ДЛИНА ПЕРИОДА НЕ МОЖЕТ БЫТЬ
БОЛЬШЕ~$m$. (дАЖЕ ЕСЛИ ТРЕБУЮТСЯ ТОЛЬКО СЛУЧАЙНЫЕ НУЛИ И ЕДИНИЦЫ,
НЕ СЛЕДУЕТ БРАТЬ~$m=2$, ТАК КАК ПРИ ЭТОМ В ЛУЧШЕМ СЛУЧАЕ ПОЛУЧИТСЯ НАБОР
$$
\ldots, 0, 1, 0, 1, 0, 1,\ldots\,!
$$

мЕТОДЫ ИСПОЛЬЗОВАНИЯ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ ДЛЯ
ПОЛУЧЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ НУЛЕЙ И ЕДИНИЦ ОБСУЖДАЮТСЯ В~\S~3.4.)

дРУГОЙ ФАКТОР, ВЛИЯЮЩИЙ НА ВЫБОР~$m$---ЭТО СКОРОСТЬ ВЫРАБОТКИ ЧИСЕЛ: МЫ
ХОТИМ ПОДОБРАТЬ ТАКОЕ ЗНАЧЕНИЕ, ЧТОБЫ БЫСТРЕЕ ВЫЧИСЛЯТЬ~$(aX_n+c)\bmod m$.

рАССМОТРИМ В КАЧЕСТВЕ ПРИМЕРА МАШИНУ~\MIX. мЫ МОЖЕМ ВЫЧИСЛЯТЬ~$y \bmod
m$, ПОМЕЩАЯ~$y$ В РЕГИСТРЫ~|A| И~|X|, ПОСЛЕДУЮЩИМ ДЕЛЕНИЕМ НА~$m$.
пРЕДПОЛОЖИВ, ЧТО~$y$ И~$m$---ПОЛОЖИТЕЛЬНЫЕ ЧИСЛА, МОЖНО УБЕДИТЬСЯ, ЧТО В
РЕЗУЛЬТАТЕ В РЕГИСТРЕ~|X| ОКАЖЕТСЯ~$y\bmod m$. нО ТАК КАК
ДЕЛЕНИЕ---СРАВНИТЕЛЬНО МЕДЛЕННАЯ ОПЕРАЦИЯ, ЕЕ МОЖНО ИЗБЕЖАТЬ ЗА СЧЕТ ОСОБО
УДОБНОГО ВЫБОРА~$m$, ПРИНЯВ ЕГО РАВНЫМ \emph{РАЗМЕРУ СЛОВА} (Т.~Е.~НА
ЕДИНИЦУ БОЛЬШЕ МАКСИМАЛЬНОГО ЦЕЛОГО ЧИСЛА, РАЗМЕЩАЮЩЕГОСЯ В СЛОВЕ
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ).

пУСТЬ~$w$---ТАКОЕ МАКСИМАЛЬНОЕ ЦЕЛОЕ ЧИСЛО. тОГДА ОПЕРАЦИЯ СЛОЖЕНИЯ
ПРОИЗВОДИТСЯ ПО МОДУЛЮ~$w$, А УМНОЖЕНИЕ ПО МОДУЛЮ~$w$ ТАКЖЕ СРАВНИТЕЛЬНО
ПРОСТО, ТАК КАК НУЖНЫЙ РЕЗУЛЬТАТ ПОЛУЧАЕТСЯ В МЛАДШИХ РАЗРЯДАХ
ПРОИЗВЕДЕНИЯ. тАКИМ ОБРАЗОМ, СЛЕДУЮЩАЯ
%% 25
ПРОГРАММА ЭФФЕКТИВНО ВЫЧИСЛЯЕТ~$(aX+c)\bmod w$:
$$
\vcenter{
\mixcode
LDA  & A
MUL  & X
SLAX & 5
ADD  & C
\endmixcode
}
\eqno(1)
$$

рЕЗУЛЬТАТ ПОЛУЧАЕТСЯ В РЕГИСТРЕ~|A|. в КОНЦЕ ВЫПОЛНЕНИЯ ЭТОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ КОМАНД МОЖЕТ ПРОИЗОЙТИ ПЕРЕПОЛНЕНИЕ, СИГНАЛ КОТОРОГО
МОЖНО ВЫКЛЮЧИТЬ, НАПИСАВ ВСЛЕД ЗА ПОСЛЕДНЕЙ КОМАНДОЙ~"|JOV *+1|".

мЕНЕЕ ШИРОКО ИЗВЕСТНУЮ ТОНКУЮ ТЕХНИКУ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ВЫЧИСЛЕНИЙ ПО
МОДУЛЮ~$(w+1)$. пО ПРИЧИНАМ, О КОТОРЫХ БУДЕТ СКАЗАНО НИЖЕ, ПРИ~$m=w+1$ МЫ
ОБЫЧНО ПОЛАГАЕМ~$c=0$. пОЭТОМУ НАМ НУЖНО ВЫЧИСЛЯТЬ ПРОСТО~$(aX)\bmod(w+1)$.
эТО ДЕЛАЕТ СЛЕДУЮЩАЯ ПРОГРАММА:
$$
\vcenter{
\mixcode
LDAN & X
MUL  & A
STX  & TEMP
SUB  & TEMP
JANN & *+3
INCA & 2
ADD  & =W-1=
\endmixcode
}
\eqno(2)
$$

в РЕГИСТРЕ~|A| ТЕПЕРЬ СОДЕРЖИТСЯ ЗНАЧЕНИЕ~$(aX)\bmod (w+1)$. кОНЕЧНО, ОНО
МОЖЕТ БЫТЬ ЛЮБЫМ В ИНТЕРВАЛЕ МЕЖДУ~$0$ И~$w$. пОЭТОМУ ЧИТАТЕЛЬ ВПОЛНЕ
ЗАКОННО МОЖЕТ СПРОСИТЬ, КАК МОЖНО ЗАПИСАТЬ ТАК МНОГО ЗНАЧЕНИЙ С ПОМОЩЬЮ
|A|-РЕГИСТРА! (оЧЕВИДНО, ЧТО В РЕГИСТРЕ НЕ МОГУТ ПОМЕЩАТЬСЯ ЧИСЛА,
БОЛЬШИЕ, ЧЕМ~$w-1$.) оТВЕТ СОСТОИТ В ТОМ, ЧТО ПЕРЕПОЛНЕНИЕ ПРОИЗОЙДЕТ
ТОГДА И ТОЛЬКО ТОГДА, КОГДА РЕЗУЛЬТАТ РАВЕН~$w$ (В ПРЕДПОЛОЖЕНИИ, ЧТО
СИГНАЛ ПЕРЕПОЛНЕНИЯ БЫЛ РАНЕЕ ВЫКЛЮЧЕН).

дЛЯ ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО ПРОГРАММА~(2), В САМОМ ДЕЛЕ,
ВЫЧИСЛЯЕТ~$(aX)\bmod (w+1)$, ЗАМЕТИМ, ЧТО В СТРОКЕ~04 МЫ ВЫЧИТАЕМ
МЛАДШУЮ ПОЛОВИНУ ПРОИЗВЕДЕНИЯ ИЗ СТАРШЕЙ. пЕРЕПОЛНЕНИЯ ПРИ ЭТОМ
ПРОИЗОЙТИ НЕ МОЖЕТ, И, ЕСЛИ~$aX=qw+r$, ГДЕ~$0\le r < w$, В РЕГИСТРЕ~|A|
ПОСЛЕ ВЫПОЛНЕНИЯ СТРОКИ~04 ОКАЖЕТСЯ ЗНАЧЕНИЕ~$r-q$. зАМЕТИМ, ЧТО
$$
aX=q(w+1)+(r-q),
$$
А ТАК КАК~$q<w$,  ИМЕЕМ~$-w < r-q < w$. сЛЕДОВАТЕЛЬНО,
$(aX)\bmod(w+1)$~РАВНЯЕТСЯ ЛИБО~$r-q$, ЛИБО~$r-q+(w+1)$ В ЗАВИСИМОСТИ ОТ
ТОГО, КАКОЕ ИЗ НЕРАВЕНСТВ~$r-q\ge 0$ ИЛИ~$r-q<0$ ВЫПОЛНЯЕТСЯ.
еСЛИ МЫ ПОЛЬЗУЕМСЯ КОНГРУЭНТНЫМ МЕТОДОМ С~$m=w+1$, ОТБРАСЫВАТЬ
ЗНАЧЕНИЯ~$w$, ЕСЛИ ОНИ ПОЛУЧАЮТСЯ, БЫВАЕТ ОБЫЧНО
%% 26
ЛЕГКО, ДОБАВЛЯЯ К ПРОГРАММЕ~(2) КОМАНДЫ
$$
\vbox{
\mixcode
JOV & * +1 \global\pcntr=-1
\dots \global\pcntr=8
JNOV & *+3
LDAN & A
JMP  & *-4
\endmixcode
}
\eqno(3)
$$

с ПОМОЩЬЮ ПОХОЖЕЙ ТЕХНИКИ МОЖНО ВЫЧИСЛЯТЬ ПРОИЗВЕДЕНИЕ ДВУХ ЧИСЕЛ ПО
МОДУЛЮ~$(w-1)$; СМ.~УПР.~8.

в ПОСЛЕДУЮЩИХ РАЗДЕЛАХ НАМ ПОТРЕБУЕТСЯ УМЕТЬ ПРЕДСТАВЛЯТЬ~$m$ В ВИДЕ
ПРОИЗВЕДЕНИЯ ПРОСТЫХ ЧИСЕЛ. эТО ПОМОЖЕТ ПРАВИЛЬНО ВЫБРАТЬ МНОЖИТЕЛЬ~$a$.
в ТАБЛ.~1 ПРИВОДИТСЯ ФАКТОРИЗАЦИЯ ЧИСЕЛ ВИДА~$w\pm 1$ ПОЧТИ ДЛЯ ВСЕХ
ИЗВЕСТНЫХ РАЗМЕРОВ СЛОВ. бОЛЕЕ ПОЛНЫЕ ДАННЫЕ МОЖНО НАЙТИ В КНИГЕ
э.~кАННИНГХЭМА И~X.~вУДАЛЛА (Factorization of~$y^n\pm 1$, Francis Hodgson,
London, 1925) ИЛИ ПОЛУЧИТЬ С ПОМОЩЬЮ МЕТОДОВ П.~4.5.4.

чИТАТЕЛЬ МОЖЕТ ЗАДАТЬ СПРАВЕДЛИВЫЙ ВОПРОС, ПОЧЕМУ НАС ТАК БЕСПОКОЯТ
ЗНАЧЕНИЯ~$m=w\pm1$, ЕСЛИ УДОБСТВА ВЫБОРА~$m=w$ НАСТОЛЬКО ОЧЕВИДНЫ?
пРИЧИНА ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ПРИ~$m=w$ \emph{МЛАДШИЕ ЦИФРЫ ЧИСЛА~$X_n$
НАМНОГО МЕНЕЕ СЛУЧАЙНЫ, ЧЕМ СТАРШИЕ.} еСЛИ~$d$ ЯВЛЯЕТСЯ ДЕЛИТЕЛЕМ~$m$ И ЕСЛИ
% !!! СТИЛЬ СНОСОК ДОЛЖЕН БЫТЬ ТАКИМ, ЧТОБЫ НЕ ПУТАТЬ ЭТУ СНОСКУ
% С ВЕРХНИМ ИНДЕКСОМ.
$$
Y_n=X_n \bmod d %
\hbox{\note{1}%
{фОРМУЛА~(4) ОПРЕДЕЛЯЕТ НОВУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ ОСТАТКОВ~$\gamma_0$,
 $\gamma_1$,~\dots, $\gamma_n$, \dots, ДЛЯ КОТОРОЙ
 ВЫПОЛНЕНО~(5).---{\sl пРИМ. РЕД.\/}},
}
\eqno(4)
$$
ТО, КАК МОЖНО ЛЕГКО ПОКАЗАТЬ,
$$
Y_{n+1}=(aY_n+c)\bmod d
\eqno(5)
$$
(ИБО НАЙДЕТСЯ НЕКОТОРОЕ ЦЕЛОЕ~$q$, ДЛЯ КОТОРОГО~$X_{n+1}=aX_n+c-qm$, И
ПОЭТОМУ ЕСЛИ~$d$ ЯВЛЯЕТСЯ ДЕЛИТЕЛЕМ~$m$, ТО, ПЕРЕХОДЯ К СРАВНЕНИЮ ПО
МОДУЛЮ~$d$, ПОЛУЧИМ~(5)).

чТОБЫ ПРОИЛЛЮСТРИРОВАТЬ ВАЖНОСТЬ СООТНОШЕНИЯ~(5), ПРЕДПОЛОЖИМ, НАПРИМЕР,
ЧТО ИМЕЕТСЯ ДВОИЧНАЯ ВЫЧИСЛИТЕЛЬНАЯ МАШИНА. еСЛИ~$m=w=2^e$, ТО МЛАДШИЕ
ЧЕТЫРЕ БИТА~$X_n$ ПРЕДСТАВЛЯЮТ ЧИСЛО~$Y_n=X_n\bmod 2^4$. сУЩНОСТЬ
ФОРМУЛЫ~(5) ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО МЛАДШИЕ ЧЕТЫРЕ БИТА~$X_n$ ОБРАЗУЮТ
КОНГРУЭНТНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ С ПЕРИОДОМ, НЕ ПРЕВЫШАЮЩИМ~16. тОЧНО ТАК
ЖЕ МЛАДШИЕ ПЯТЬ БИТОВ ПЕРИОДИЧНЫ С ПЕРИОДОМ, РАВНЫМ САМОЕ
БОЛЬШЕЕ~32. сАМЫЙ ЖЕ МЛАДШИЙ БИТ~$X_n$ ЛИБО СОХРАНЯЕТ ПОСТОЯННОЕ ЗНАЧЕНИЕ,
ЛИБО СТРОГО ПЕРИОДИЧЕСКИ ИЗМЕНЯЕТСЯ ОТ НУЛЯ ДО ЕДИНИЦЫ.

пОДОБНОЙ СИТУАЦИИ НЕ ВОЗНИКАЕТ, КОГДА~$m=w\pm 1$. в ЭТОМ СЛУЧАЕ МЛАДШИЕ
БИТЫ~$X_n$ ВЕДУТ СЕБЯ ТАК ЖЕ СЛУЧАЙНО, КАК И СТАРШИЕ. нАПРИМЕР, ЧЛЕНЫ
ПОСЛЕДОВАТЕЛЬНОСТИ ПРИ~$w=2^{35}$ И~$m=2^{35}-1$
%% 27
{\catcode`.=\active\def.{\cdot}\offinterlineskip
\htable{тАБЛИЦА 1}%
{рАЗЛОЖЕНИЕ~$w\pm 1$ НА ПРОСТЫЕ МНОЖИТЕЛИ}%
{\strut\hfil$#$\bskip&\vrule\hfil\bskip$#$\bskip\hfil\vrule&\bskip$#$\hfil\cr
2^e-1 & e & 2^e+1 \cr
\noalign{\hrule}
                             7.31.151 & 15 & 3^2.11.331 \cr
                           3.5.17.257 & 16 & 65537 \cr
                               131071 & 17 & 3.43601 \cr
                          3^2.7.19.73 & 18 & 5.13.37.109 \cr
                               524287 & 19 & 3.174763 \cr
                       3.5^2.11.31.41 & 20 & 17.61681 \cr
                          7^2.127.337 & 21 & 3^2.43.5419 \cr
                          3.23.89.683 & 22 & 5.397.2113 \cr
                            47.178481 & 23 & 3.2796203 \cr
                    3^2.5.7.13.17.241 & 24 & 97.257.673 \cr
                          31.601.180l & 25 & 3.11.251.4051 \cr
                          3.2731.8191 & 26 & 5.53.157.1613 \cr
                          7.73.262657 & 27 & 3^4.19.87211 \cr
                    3.5.29.43.113.127 & 28 & 17.15790321 \cr
                        233.1103.2089 & 29 & 3.59.3033169 \cr
              3^2.7 .11 .31 .151 .331 & 30 & 5^2.13.41.61.1321 \cr
                           2147483647 & 31 & 3.715827883 \cr
                     3.5.17.257.65537 & 32 & 641.6700417 \cr
                       7.23.89.599479 & 33 & 3^2 .67.683.20857 \cr
                       3.43691.131071 & 34 & 5.137.953.26317 \cr
                     31.71.127.122921 & 35 & 3.11.43.281.86171 \cr
              3^2.5.7.13.19.37.73.109 & 36 & 17.241.433.38737 \cr
                        223.616318177 & 37 & 3.1777.25781083 \cr
                      3.174763.524287 & 38 & 5.229.457.525313 \cr
                     7.79.8191.121369 & 39 & 3^2 .2731.22366891 \cr
              3.5^2.11.17.31.41.61681 & 40 & 257.4278255361 \cr
                      13367.164511353 & 41 & 3.83.8831418697 \cr
              3^2.7^2.43.127.337.5419 & 42 & 5.13.29.113.1429.14449 \cr
                     431.9719.2099863 & 43 & 3.2932031007403 \cr
               3.5.23.89.397.683.2113 & 44 & 17.353.2931542417 \cr
                7.31.73.151.631.23311 & 45 & 3^3.11.19.331.18837001 \cr
                  3.47.178481.2796203 & 46 & 5.277.1013.1657.30269 \cr
                   2351.4513.13264529 & 47 & 3.283.165768537521 \cr
         3^2.5.7.13.17.97.241.257.673 & 48 & 193.65537.22253377 \cr
                 179951.3203431780337 & 59 & 3.2833.37171.1824726041 \cr
3^2.5^2.7.11.13.31.41.61.151.331.1321 & 60 & 17.241.61681.4562284561 \cr
          7^2.73.127.337.92737.649657 & 63 & 3^3.19.43.5419.77158673929 \cr
         3.5.17.257.641.65537.6700417 & 64 &274177.67280421310721 \cr
\noalign{\hrule\smallskip\hrule}
                               10^e-1 &  e & 10^e+1\cr
\noalign{\hrule}
                       3^3.7.11.13.37 &  6 & 101.9901\cr
                         3^2.239.4649 &  7 & 11.909091\cr
                    3^2.11.73.101.137 &  8 & 17.5882353\cr
                        3^4.37.333667 &  9 & 7.11.13.19.52579\cr
                   3^2.11.41.271.9091 & 10 & 101.3541.27961\cr
                     3^2.21649.513239 & 11 & 11^2.23.4093.8779\cr
              3^3.7.11.13.37.101.9901 & 12 & 73.137.99990001\cr
         3^2.11.17.73.101.137.5882353 & 16 & 353.449.641.1409.69857\cr
\noalign{\hrule\smallskip\hrule}
}
}
%% 28
БУДУТ НЕ СЛИШКОМ СЛУЧАЙНЫ, ЕСЛИ ВЫЧИСЛЯТЬ ВЫЧЕТЫ ПО МОДУЛЮ~$31$, $71$,
$127$ ИЛИ~$122921$ (СР.~С~ТАБЛ.~1). в ТО ЖЕ ВРЕМЯ МЛАДШИЕ БИТЫ БУДУТ
ВПОЛНЕ СЛУЧАЙНЫ (ИХ МОЖНО РАССМАТРИВАТЬ КАК ВЫЧЕТЫ ЧЛЕНОВ
ПОСЛЕДОВАТЕЛЬНОСТИ, ПОЛУЧЕННЫЕ ПРИ СРАВНЕНИИ ПО МОДУЛЮ~$2$).

дРУГАЯ ВОЗМОЖНОСТЬ---ЭТО ВЫБОР В КАЧЕСТВЕ~$m$ НАИБОЛЬШЕГО ПРОСТОГО ЧИСЛА,
МЕНЬШЕГО, ЧЕМ~$w$. еГО МОЖНО НАЙТИ, ПРИМЕНЯЯ ТЕХНИКУ П.~4.5.4, В КОТОРОМ
ЕСТЬ И ТАБЛИЦА СООТВЕТСТВУЮЩИХ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ.

дЛЯ БОЛЬШИНСТВА ПРИЛОЖЕНИЙ МЛАДШИЕ БИТЫ НЕ СУЩЕСТВЕННЫ, И ВЫБОР~$m=w$
ЯВЛЯЕТСЯ ВПОЛНЕ УДОВЛЕТВОРИТЕЛЬНЫМ ПРИ УСЛОВИИ, ЧТО ПРОГРАММИСТ,
ПОЛЬЗУЮЩИЙСЯ СЛУЧАЙНЫМИ ЧИСЛАМИ, ДЕЛАЕТ ЭТО РАЗУМНО.

\excercises

\ex[12] иЗ УПР.~3.2.1-3 МЫ ЗАКЛЮЧИЛИ, ЧТО У САМЫХ ЛУЧШИХ
КОНГРУЭНТНЫХ ДАТЧИКОВ ЧИСЛА~$a$ И~$m$ ВЗАИМНО ПРОСТЫЕ. пОКАЖИТЕ, ЧТО В
ЭТОМ СЛУЧАЕ МОЖНО ПОЛУЧИТЬ~$(aX+c)\bmod w$ В РЕГИСТРЕ~$X$ С ПОМОЩЬЮ ВСЕГО
\emph{ТРЕХ} КОМАНД~\MIX, А НЕ ЧЕТЫРЕХ, КАК В ПРИМЕРЕ~(1).

\ex[16] нАПИШИТЕ ПОДПРОГРАММУ~\MIX, УДОВЛЕТВОРЯЮЩУЮ ТРЕМ УСЛОВИЯМ:
\descrtable{
     оБРАЩЕНИЕ: & |JMP RANDM| \cr
 уСЛОВИЯ ВХОДА: & в ЯЧЕЙКЕ~|XRAND| СОДЕРЖИТСЯ ЦЕЛОЕ ЧИСЛО~$X$. \cr
уСЛОВИЯ ВЫХОДА: & $X\asg |rA|\asg(aX+c)\bmod w$, $|rX|\asg 0$,
                  ПЕРЕПОЛНЕНИЕ "ВЫКЛЮЧЕНО".\cr
}
(тАКИМ ОБРАЗОМ, В РЕЗУЛЬТАТЕ ОБРАЩЕНИЯ К ЭТОЙ ПОДПРОГРАММЕ БУДЕТ
ПОЛУЧЕНО СЛЕДУЮЩЕЕ СЛУЧАЙНОЕ ЧИСЛО ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.)

\ex[20] кАК ОПИСАТЬ НА ЯЗЫКЕ АВТОКОДА~\MIX{} КОНСТАНТУ~$w-1$ НЕЗАВИСИМО ОТ
РАЗМЕРА БАЙТА?

\ex[10] оБЎЯСНИТЕ СМЫСЛ ПОСЛЕДОВАТЕЛЬНОСТИ КОМАНД~(3).

\ex[20] дАНО, ЧТО $m$~МЕНЬШЕ МАКСИМАЛЬНОГО ЦЕЛОГО, ПОМЕЩАЮЩЕГОСЯ В СЛОВЕ,
А~$x$ И~$y$---НЕОТРИЦАТЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛА, МЕНЬШИЕ, ЧЕМ~$m$. пОКАЖИТЕ, ЧТО
ДЛЯ ВЫЧИСЛЕНИЯ РАЗНОСТИ~$(x-y)\bmod m$ ДОСТАТОЧНО ЧЕТЫРЕХ КОМАНД~\MIX{} И НЕ
НУЖНА ОПЕРАЦИЯ ДЕЛЕНИЯ. кАКОВА НАИЛУЧШАЯ ПРОГРАММА ДЛЯ
ВЫЧИСЛЕНИЯ СУММЫ~$(x+y)\bmod m$?

\rex[20] в ПРЕДЫДУЩЕМ УПРАЖНЕНИИ ПРЕДПОЛАГАЕТСЯ, ЧТО ВЫЧИТАНИЕ ПО~$\bmod m$
ПРОЩЕ, ЧЕМ СЛОЖЕНИЕ ПО~$\bmod m$. рАССМОТРИТЕ ПОСЛЕДОВАТЕЛЬНОСТИ,
ОБРАЗУЮЩИЕСЯ ПО ПРАВИЛУ
$$
X_{n+1}=(aX_n-c) \bmod m.
$$

сУЩЕСТВЕННО ЛИ ОНИ ОТЛИЧАЮТСЯ ОТ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ОПРЕДЕЛЕННЫХ В ТЕКСТЕ? уДОБНЕЕ ЛИ ОНИ ДЛЯ
ЭФФЕКТИВНОГО ВЫЧИСЛЕНИЯ НА МАШИНАХ?

\ex[м24] кАКИЕ ХАРАКТЕРНЫЕ ОСОБЕННОСТИ ТАБЛ.~1 ВЫ МОЖЕТЕ ОТМЕТИТЬ?

\rex[20] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ ВЫЧИСЛЕНИЯ~$(aX)\bmod (w-1)$,
АНАЛОГИЧНУЮ~(2). зНАЧЕНИЯ~$0$ И~$w-1$ НА ВХОДЕ И ВЫХОДЕ ВАШЕЙ ПРОГРАММЫ
СЛЕДУЕТ СЧИТАТЬ ЭКВИВАЛЕНТНЫМИ.

\ex[23] нАПИШИТЕ \MIX-ПРОГРАММУ ДЛЯ ВЫЧИСЛЕНИЯ~$(aX)\bmod (w-2)$,
АНАЛОГИЧНУЮ ТРЕБУЮЩЕЙСЯ В УПР.~8.

\subsubsubchap{вЫБОР МНОЖИТЕЛЯ}%3.2.1.2
 в ЭТОМ ПОДПУНКТЕ МЫ ПОКАЖЕМ, КАК ВЫБИРАТЬ МНОЖИТЕЛЬ~$a$, ЧТОБЫ ПОЛУЧАТЬ
\emph{ПЕРИОД МАКСИМАЛЬНОЙ
%% 29
ДЛИНЫ.} дЛЯ ЛЮБОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, ПРЕДНАЗНАЧЕННОЙ ДЛЯ ИСПОЛЬЗОВАНИЯ В
КАЧЕСТВЕ ИСТОЧНИКА СЛУЧАЙНЫХ ЧИСЕЛ, ВАЖЕН БОЛЬШОЙ ПЕРИОД. дЕЙСТВИТЕЛЬНО,
НАМ БЫ ХОТЕЛОСЬ, ЧТОБЫ ПЕРИОД СОДЕРЖАЛ ЗНАЧИТЕЛЬНО БОЛЬШЕ ЧИСЕЛ, ЧЕМ ЭТО
НЕОБХОДИМО ДЛЯ РЕШЕНИЯ КАКОЙ-ЛИБО ОДНОЙ ЗАДАЧИ. пОЭТОМУ ЗАЙМЕМСЯ ЗДЕСЬ
ДЛИНОЙ ПЕРИОДА. чИТАТЕЛЮ СЛЕДУЕТ, ОДНАКО, ПОМНИТЬ, ЧТО
БОЛЬШОЙ ПЕРИОД---ЭТО ТОЛЬКО ОДИН ИЗ НЕОБХОДИМЫХ ПРИЗНАКОВ СЛУЧАЙНОСТИ НАШЕЙ
ПОСЛЕДОВАТЕЛЬНОСТИ. вПОЛНЕ ВОЗМОЖНЫ АБСОЛЮТНО НЕСЛУЧАЙНЫЕ
ПОСЛЕДОВАТЕЛЬНОСТИ С ОЧЕНЬ БОЛЬШИМ ПЕРИОДОМ. нАПРИМЕР, ПРИ~$a=c=1$
ПОСЛЕДОВАТЕЛЬНОСТЬ СВОДИТСЯ ПРОСТО К~$X_{n+1}=(X_n+1)\bmod m$. оЧЕВИДНО,
ЕЕ ПЕРИОД РАВЕН~$m$, ТЕМ НЕ МЕНЕЕ ЕЕ НИКАК НЕЛЬЗЯ НАЗВАТЬ СЛУЧАЙНОЙ.
дРУГИЕ СООБРАЖЕНИЯ, ВЛИЯЮЩИЕ НА ВЫБОР МНОЖИТЕЛЯ, БУДУТ ПРИВЕДЕНЫ В ЭТОЙ
ГЛАВЕ ПОЗЖЕ.

тАК КАК ВОЗМОЖНЫ ТОЛЬКО $m$~РАЗЛИЧНЫХ ЗНАЧЕНИЙ, ДЛИНА ПЕРИОДА НЕ МОЖЕТ
ПРЕВЫШАТЬ~$m$. дОСТИЖИМА ЛИ МАКСИМАЛЬНАЯ ДЛИНА~$m$? пРИВЕДЕННЫЙ ВЫШЕ
ПРИМЕР ПОКАЗЫВАЕТ, ЧТО ДА, ХОТЯ ВЫБОР~$a=c=1$ И НЕ ПРИВОДИТ К ЖЕЛАЕМОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ. иССЛЕДУЕМ \emph{ВСЕ} ВОЗМОЖНЫЕ СПОСОБЫ ВЫБОРА~$a$
И~$c$, КОТОРЫЕ ДАЮТ ПЕРИОД ДЛИНЫ~$m$. [\emph{зАМЕЧАНИЕ.} кОГДА ПЕРИОД
ИМЕЕТ ДЛИНУ~$m$, КАЖДОЕ ЧИСЛО ОТ~$0$ ДО~$(m-1)$ ВСТРЕЧАЕТСЯ ЗА ПЕРИОД
РОВНО ОДИН РАЗ. пОЭТОМУ В ЭТОМ СЛУЧАЕ ВЫБОР~$X_0$ НЕ ВЛИЯЕТ НА ДЛИНУ ПЕРИОДА.]

\proclaim тЕОРЕМА A. дЛИНА ПЕРИОДА ЛИНЕЙНОЙ КОНГРУЭНТНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ РАВНА~$m$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА
\item{i)}~$c$ И~$m$---ВЗАИМНО ПРОСТЫЕ ЧИСЛА;
\item{ii)}~$b=a-1$ КРАТНО~$p$ ДЛЯ ЛЮБОГО ПРОСТОГО~$p$, ЯВЛЯЮЩЕГОСЯ ДЕЛИТЕЛЕМ~$m$;
\item{iii)}~$b$ КРАТНО~$4$, ЕСЛИ~$m$ КРАТНО~$4$.

иДЕИ ДОКАЗАТЕЛЬСТВА ИЗВЕСТНЫ НЕ МЕНЕЕ СТА ЛЕТ. пЕРВОЕ ДОКАЗАТЕЛЬСТВО
ТЕОРЕМЫ В ДАННОЙ ФОРМУЛИРОВКЕ БЫЛО ДАНО м.~гРИНБЕРГЕРОМ ДЛЯ ЧАСТНОГО
СЛУЧАЯ~$m=2^e$ ({\sl JACM,\/} {\bf 8} (1961), 383--389). дОСТАТОЧНОСТЬ
УСЛОВИЙ~(i), (ii), (iii) В ОБЩЕМ СЛУЧАЕ БЫЛА ПОКАЗАНА хАЛЛОМ И дОБЕЛЛОМ
({\sl SIAM Review,\/} {\bf 4} (1962), 230--254). дЛЯ ДОКАЗАТЕЛЬСТВА
ТЕОРЕМЫ РАССМОТРИМ СНАЧАЛА НЕКОТОРЫЕ ВСПОМОГАТЕЛЬНЫЕ РЕЗУЛЬТАТЫ ТЕОРИИ
ЧИСЕЛ, КОТОРЫЕ ИНТЕРЕСНЫ И САМИ ПО СЕБЕ.

\proclaim лЕММА~P. пУСТЬ~$p$---ПРОСТОЕ ЧИСЛО, А~$e$---ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ,
ТАКОЕ, ЧТО~$p^e>2$. еСЛИ
$$
x\equiv 1 \pmod{p^e}, \quad x \not\equiv 1 \pmod{p^{e+1}},
\eqno(1)
$$
ТО
$$
x^p \equiv 1 \pmod{p^{e+1}}, \quad x^p \not\equiv 1 \pmod{p^{e+2}}.
\eqno(2)
$$

\proof мЫ ИМЕЕМ~$x=1+qp^e$,  ГДЕ~$q$---НЕКОТОРОЕ ЦЕЛОЕ, НЕ КРАТНОЕ~$p$.
%% 30
пО ФОРМУЛЕ БИНОМА ЗАПИШЕМ
$$
\eqalign{
x^p&=1+\perm{p}{1}qp^e+\cdots+\perm{p}{p-1}q^{p-1}p^{(p-1)e}+q^pp^{pe}=\cr
&=1+qp^{e+1}\left(1+{1\over p}\perm{p}{2}qp^e+{1\over p}\perm{p}{3}q^2p^{2e}+
 \cdots+{1\over p}\perm{p}{p}q^{p-1}p^{(p-1)e}\right).\cr
}
$$

вЫРАЖЕНИЕ В СКОБКАХ---ЦЕЛОЕ ЧИСЛО, ПРИЧЕМ КАЖДОЕ СЛАГАЕМОЕ КРАТНО~$p$, ЗА
ИСКЛЮЧЕНИЕМ ПЕРВОГО ЧЛЕНА. в САМОМ ДЕЛЕ,
ЕСЛИ~$1<k<p$, ТО~$\perm{p}{k}$ ДЕЛИТСЯ НА~$p$ (СР.~С~УПР.~1.2.6-10).
сЛЕДОВАТЕЛЬНО,
$$
{1\over p}\perm{p}{k}q^{k-1}p^{(k-1)e}
$$
ДЕЛИТСЯ НА~$p^{(k-1)e}$. пОСЛЕДНИЙ ЧЛЕН~$q^{p-1}p^{(p-1)e-1}$ ДЕЛИТСЯ
НА~$p$, ТАК КАК~$(p-1)e>1$ ПРИ~$p^e>2$. тАКИМ ОБРАЗОМ, $x^p=1+q'p^{e+1}$,
ГДЕ~$q'$---ЦЕЛОЕ ЧИСЛО, КОТОРОЕ НЕ ДЕЛИТСЯ НА~$p$. тЕМ САМЫМ
ДОКАЗАТЕЛЬСТВО ЗАВЕРШЕНО. (\emph{зАМЕЧАНИЕ:} ОБОБЩЕНИЕ ЭТОГО
РЕЗУЛЬТАТА СОДЕРЖИТСЯ В УПР.~3.2.2-11~(a).)
\proofend

\proclaim лЕММА~Q. {пУСТЬ РАЗЛОЖЕНИЕ~$m$ НА ПРОСТЫЕ МНОЖИТЕЛИ ИМЕЕТ ВИД
$$
m=p_1^{e_1}\ldots p_t^{e_t}.
\eqno(3)
$$
\hiddenpar
дЛИНА~$\lambda$ ПЕРИОДА ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ,
ОПРЕДЕЛЯЕМОЙ~$(X_0, a, c, m)$, РАВНА НАИМЕНЬШЕМУ ОБЩЕМУ КРАТНОМУ
ДЛИН~$\lambda_j$ ПЕРИОДОВ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
$$
(X_0 \bmod p_j^{e_j}, a p_j^{e_j}, c p_j^{e_j}, p_j^{e_j}),
\rem{$1\le j \le t$.}
$$
}

\proof иНДУКЦИЕЙ ПО~$t$ ДОСТАТОЧНО ДОКАЗАТЬ, ЧТО, ЕСЛИ~$r$ И~$s$---ВЗАИМНО
ПРОСТЫЕ ЧИСЛА, ДЛИНА~$\lambda$ ПЕРИОДА ЛИНЕЙНОЙ КОНГРУЭНТНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ, ОПРЕДЕЛЯЕМОЙ~$(X_0, a, c, rs)$, РАВНА НАИМЕНЬШЕМУ
ОБЩЕМУ КРАТНОМУ ДЛИН~$\lambda_1$ И~$\lambda_2$ ПЕРИОДОВ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$(X_0 \bmod r, a \bmod r, c \bmod r, r)$
И~$(X_0 \bmod s, a \bmod s, c \bmod s, s)$.

в ПРЕДЫДУЩЕМ РАЗДЕЛЕ (СМ.~ФОРМУЛУ~(5)) МЫ ВИДЕЛИ, ЧТО ЕСЛИ ОБОЗНАЧИТЬ
ЭЛЕМЕНТЫ ЭТИХ ТРЕХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СООТВЕТСТВЕННО~$X_n$, $Y_n$, $Z_n$,
ТО ВЫПОЛНЯЮТСЯ СЛЕДУЮЩИЕ СООТНОШЕНИЯ:
$$
Y_n=X_n \bmod r \hbox{ И } Z_n=X_n \bmod s
\rem{ДЛЯ ВСЕХ~$n\ge 0$.}
$$
%% 31
пОЭТОМУ ИЗ СВОЙСТВА~D П.~1.2.4 НАХОДИМ, ЧТО
$$
X_n=X_k  \rem{ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$Y_n=Y_k$ И~$Z_n=Z_k$.}
\eqno (4)
$$
пУСТЬ~$\lambda'$---НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ ДЛИН~$\lambda_1$ И~$\lambda_2$;
ДОКАЖЕМ, ЧТО~$\lambda'=\lambda$. тАК КАК~$X_n=X_{n+\lambda}$ ДЛЯ ВСЕХ
ДОСТАТОЧНО БОЛЬШИХ~$n$, ИМЕЕМ~$Y_n=Y_{n+\lambda}$ (СЛЕДОВАТЕЛЬНО,
$\lambda$ КРАТНО~$\lambda_1$) И~$Z_n=Z_{n+\lambda}$ (СЛЕДОВАТЕЛЬНО,
$\lambda$ КРАТНО~$\lambda_2$), И ПОЭТОМУ~$\lambda\ge\lambda'$. с ДРУГОЙ
СТОРОНЫ, МЫ ЗНАЕМ, ЧТО~$Y_n=Y_{n+\lambda'}$ И~$Z_n=Z_{n+\lambda'}$ ДЛЯ
ВСЕХ ДОСТАТОЧНО БОЛЬШИХ~$n$. пОЭТОМУ НА ОСНОВАНИИ~(4)
ИМЕЕМ~$X_n=X_{n+\lambda'}$, ИЗ ЧЕГО ПОЛУЧАЕМ~$\lambda\le\lambda'$, ТАК
ЧТО~$\lambda=\lambda'$.
\proofend

тЕПЕРЬ МЫ ГОТОВЫ ДОКАЗАТЬ ТЕОРЕМУ~A. иМЕЯ В ВИДУ ЛЕММУ~Q, ДОСТАТОЧНО
ДОКАЗАТЬ ТЕОРЕМУ ДЛЯ СЛУЧАЯ, КОГДА $m$~ЕСТЬ СТЕПЕНЬ ПРОСТОГО ЧИСЛА. в
САМОМ ДЕЛЕ, НЕРАВЕНСТВО
$$
p_1^{e_1} \ldots p_t^{e_t}=\lambda=\НОК(\lambda_1,~\ldots, \lambda_t)
\le \lambda_1 \ldots \lambda_t \le p_1^{e_1}\ldots p_t^{e_t}
$$
МОЖЕТ БЫТЬ СПРАВЕДЛИВО В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ,
ЕСЛИ~$\lambda_j=p_j^{e_j}$ ДЛЯ~$1\le j \le t$.

пОЭТОМУ ПРЕДПОЛОЖИМ, ЧТО~$m=p^e$, ГДЕ~$p$---ПРОСТОЕ, А~$e$---ПОЛОЖИТЕЛЬНОЕ
ЦЕЛОЕ ЧИСЛО. оЧЕВИДНО, ЧТО ПРИ~$a=1$ ТЕОРЕМА СПРАВЕДЛИВА, ПОЭТОМУ МОЖНО
СЧИТАТЬ~$a>1$. дЛИНА ПЕРИОДА РАВНА~$m$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА КАЖДОЕ
ЦЕЛОЕ ЧИСЛО~$x$, ТАКОЕ, ЧТО~$0 \le x < m$, ВСТРЕЧАЕТСЯ В
ПОСЛЕДОВАТЕЛЬНОСТИ НА ПРОТЯЖЕНИИ ПЕРИОДА (ПОСКОЛЬКУ НИ ОДНО ИЗ ЗНАЧЕНИЙ
НЕ МОЖЕТ ВСТРЕТИТЬСЯ ЗА ПЕРИОД БОЛЕЕ ОДНОГО РАЗА). тАКИМ ОБРАЗОМ, ПЕРИОД
ИМЕЕТ ДЛИНУ~$m$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, ЕСЛИ ДЛИНА ПЕРИОДА
ПОСЛЕДОВАТЕЛЬНОСТИ С~$X_0=0$ РАВНА~$m$, ЧТО
ОПРАВДЫВАЕТ ПРЕДПОЛОЖЕНИЕ~$X_0=0$. иЗ. ФОРМУЛЫ~3.2.1-(6) ИМЕЕМ
$$
X_n=\left({a^n-1 \over a-1}\right) c \bmod m.
\eqno (5)
$$
еСЛИ ЧИСЛА~$c$ И~$m$ НЕ ЯВЛЯЮТСЯ ВЗАИМНО ПРОСТЫМИ, $X_n$ НИКОГДА НЕ МОЖЕТ
БЫТЬ РАВНО~$1$. пОЭТОМУ УСЛОВИЕ~(i) ОКАЗЫВАЕТСЯ НЕОБХОДИМЫМ. пЕРИОД
ИМЕЕТ ДЛИНУ~$m$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА НАИМЕНЬШЕЕ ПОЛОЖИТЕЛЬНОЕ
ЗНАЧЕНИЕ~$n$, ДЛЯ КОТОРОГО~$X_n=X_0=0$, ТАКОВО, ЧТО~$n=m$. тЕПЕРЬ В
СИЛУ~(5) И УСЛОВИЯ~(i) НАША ТЕОРЕМА СВОДИТСЯ К ДОКАЗАТЕЛЬСТВУ СЛЕДУЮЩЕГО
УТВЕРЖДЕНИЯ.

\proclaim лЕММА~R. пРЕДПОЛОЖИМ, ЧТО~$1<a<p^e$, ГДЕ~$p$---ПРОСТОЕ ЧИСЛО.
еСЛИ~$\lambda$---НАИМЕНЬШЕЕ  ПОЛОЖИТЕЛЬНОЕ  ЦЕЛОЕ, ДЛЯ
КОТОРОГО~$(a^\lambda-1)/(a-1)\equiv 0 \pmod{p^e}$, ТО
$$
\lambda=p^e\hbox{ТОГДА И ТОЛЬКО ТОГДА, КОГДА }
\cases{
a\equiv 1 \pmod{p} & ПРИ $p>2$,\cr
a\equiv 1 \pmod{4} & ПРИ $p=2$.
}
$$
%% 32
\proof пРЕДПОЛОЖИМ, ЧТО~$\lambda=p^e$. еСЛИ~$a\not\equiv 1 \pmod{p}$,
ТО~$(a^n-1)/(a-1)\equiv 0 \pmod{p^e}$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ,
КОГДА~$a^n-1\equiv 0 \pmod{p^e}$. уСЛОВИЕ~$a^{p^e}-1\equiv 0 \pmod{p^e}$
ТОГДА ТРЕБУЕТ, ЧТОБЫ ВЫПОЛНЯЛОСЬ СООТНОШЕНИЕ~$a^{p^e}\equiv 1 \pmod{p}$.
нО ИЗ ТЕОРЕМЫ~1.2.4F СЛЕДУЕТ, ЧТО~$a^{p^e}\equiv a \pmod{p}$; ТАКИМ
ОБРАЗОМ ПОЛУЧАЕМ~$a\not\equiv 1 \pmod{p}$, ЧТО ПРИВОДИТ К
ПРОТИВОРЕЧИЮ. еСЛИ ЖЕ~$p=2$ И~$a\equiv 3 \pmod{4}$, ТО ИЗ УПР.~8
ИМЕЕМ~$(a^{2^{e-1}}-1)/(a-1)\equiv 0 \pmod{2^e}$. эТИ СООБРАЖЕНИЯ
ОБОСНОВЫВАЮТ НЕОБХОДИМОСТЬ РАВЕНСТВА~$a=1+qp^f$, ГДЕ~$p^f>2$, А~$q$ НЕ
КРАТНО~$p$ ДЛЯ ЛЮБЫХ~$\lambda=p^e$.

оСТАЕТСЯ ПОКАЗАТЬ, ЧТО ЭТО УСЛОВИЕ \emph{ДОСТАТОЧНО} ДЛЯ ВЫПОЛНЕНИЯ
СООТНОШЕНИЯ~$\lambda=p^e$. пОВТОРНО ИСПОЛЬЗУЯ ЛЕММУ~P, НАХОДИМ, ЧТО
$$
a^{p^g}\equiv 1 \pmod{p^{f+g}}, \quad
a^{p^g}\not\equiv 1 \pmod{p^{f+g+1}},
$$
И ПОЭТОМУ
$$
\eqalign{
(a^{p^g}-1)/(a-1) &\equiv 0 \pmod{p^g}, \cr
(a^{p^g}-1)/(a-1) &\not\equiv 0 \pmod{p^{g+1}}.\cr
}
\eqno(6)
$$

в ЧАСТНОСТИ, $(a^{p^e}-1)/(a-1)\equiv 0 \pmod{p^e}$. тАКИМ ОБРАЗОМ, В
КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$(0, a, 1, p^e)$
ИМЕЕМ~$X_n=(a^n-1)/(a-1) \bmod p^e$; ПОЭТОМУ ДЛИНА ЕЕ ПЕРИОДА РАВНА~$\lambda$,
Т.~Е.~$X_n=0$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$n$ КРАТНО~$\lambda$. сЛЕДОВАТЕЛЬНО,
$p^e$ КРАТНО~$\lambda$. эТО ВОЗМОЖНО ТОЛЬКО, ЕСЛИ~$\lambda=p^g$ ДЛЯ
НЕКОТОРОГО~$g$. иЗ СООТНОШЕНИЯ~(6) ПОЛУЧАЕМ~$\lambda=p^e$, ЧТО ЗАВЕРШАЕТ
ДОКАЗАТЕЛЬСТВО.
\proofend

тЕПЕРЬ ЗАКОНЧЕНО И ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~A.
\proofend

в ЗАКЛЮЧЕНИЕ ЭТОГО РАЗДЕЛА РАССМОТРИМ СПЕЦИАЛЬНЫЙ СЛУЧАЙ ЧИСТО
МУЛЬТИПЛИКАТИВНЫХ ДАТЧИКОВ, ДЛЯ КОТОРЫХ~$c=0$. хОТЯ ПРИ ЭТОМ ВЫРАБОТКА
СЛУЧАЙНЫХ ЧИСЕЛ ПРОИСХОДИТ НЕСКОЛЬКО БЫСТРЕЕ, ТЕОРЕМА~A ПОКАЗЫВАЕТ, ЧТО
ДОБИТЬСЯ МАКСИМАЛЬНОЙ ДЛИНЫ ПЕРИОДА НЕЛЬЗЯ. дЕЙСТВИТЕЛЬНО, ЭТО ВПОЛНЕ
ОЧЕВИДНО, ТАК КАК ЧЛЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ УДОВЛЕТВОРЯЮТ СООТНОШЕНИЮ
$$
X_{n+1}=aX_n\bmod m,
\eqno(7)
$$
И ЗНАЧЕНИЕ~$X_n=0$ МОЖЕТ В НЕЙ ВСТРЕТИТЬСЯ, ТОЛЬКО ЕСЛИ
ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫРОЖДАЕТСЯ В НУЛЬ. вООБЩЕ, ЕСЛИ~$d$---ЛЮБОЙ
ДЕЛИТЕЛЬ~$m$ И ЕСЛИ~$X_n$ КРАТНО~$d$, ВСЕ ПОСЛЕДУЮЩИЕ ЗНАЧЕНИЯ~$X_{n+1}$,
$X_{n+2}$,~\dots{} ТОЖЕ КРАТНЫ~$d$. пОЭТОМУ ПРИ~$c=0$ ЖЕЛАТЕЛЬНО, ЧТОБЫ
$X_n$~БЫЛИ ВЗАИМНО ПРОСТЫ С~$m$ ДЛЯ ВСЕХ~$n$, А ЭТО ОГРАНИЧИВАЕТ ДЛИНУ ПЕРИОДА.

мОЖНО ДОБИТЬСЯ ПРИЕМЛЕМО БОЛЬШОГО ПЕРИОДА, ДАЖЕ ЕСЛИ МЫ НАСТАИВАЕМ,
ЧТОБЫ~$c=0$. пОПЫТАЕМСЯ ТЕПЕРЬ НАЙТИ ТАКИЕ УСЛОВИЯ,
%% 33
ОПРЕДЕЛЯЮЩИЕ МНОЖИТЕЛЬ, ЧТОБЫ И В ЭТОМ ЧАСТНОМ СЛУЧАЕ
ДЛИНА ПЕРИОДА БЫЛА МАКСИМАЛЬНА.

вСЛЕДСТВИЕ ЛЕММЫ~Q ПЕРИОД ПОСЛЕДОВАТЕЛЬНОСТИ ПОЛНОСТЬЮ ОПРЕДЕЛЯЕТСЯ
ПЕРИОДАМИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ С~$m=p^e$, ТАК ЧТО РАССМОТРИМ ИМЕННО ТАКУЮ
СИТУАЦИЮ. мЫ ИМЕЕМ~$X_n=a^n X_0 \bmod p^e$, И ЯСНО, ЧТО ДЛИНА ПЕРИОДА
РАВНА~$1$, ЕСЛИ~$a$ КРАТНО~$p$\note{1}%
{еСЛИ~$a$ КРАТНО~$p$, ТО, ВООБЩЕ ГОВОРЯ, ПЕРИОД НЕ
 ПРЕВОСХОДИТ~$e$.---{\sl пРИМ. РЕД.\/}
}. пОЭТОМУ ВЫБЕРЕМ~$a$ ВЗАИМНО ПРОСТЫМ
С~$p^e$. тОГДА ПЕРИОД
РАВЕН НАИМЕНЬШЕМУ ЦЕЛОМУ~$\lambda$, ТАКОМУ, ЧТО~$X_0=a^\lambda X_0 \bmod p^e$.
еСЛИ НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ~$X_0$ И~$p^e$ ЕСТЬ~$p^f$, ЭТО УСЛОВИЕ
ЭКВИВАЛЕНТНО СЛЕДУЮЩЕМУ:
$$
a^\lambda \equiv 1 \pmod{p^{e-f}}.
\eqno(8)
$$
пО ТЕОРЕМЕ эЙЛЕРА (УПР.~1.2.4-28)
$$
a^{\varphi(p^{e-f})} \equiv 1 \pmod{p^{e-f}};
$$
СЛЕДОВАТЕЛЬНО, $\lambda$~ЕСТЬ ДЕЛИТЕЛЬ:
$$
\varphi(p^{e-f})=p^{e-f-1}(p-1).
$$

дЛЯ ВЗАИМНО ПРОСТЫХ~$a$ И~$m$ НАИМЕНЬШЕЕ ЦЕЛОЕ~$\lambda$, ДЛЯ
КОТОРОГО~$a^\lambda \equiv 1 \pmod{m}$, ОБЫЧНО НАЗЫВАЮТ \dfn{ПОРЯДКОМ ПО
МОДУЛЮ~$m$}. вЕЛИЧИНА~$a$, КОТОРОЙ СООТВЕТСТВУЕТ \emph{МАКСИМАЛЬНО}
ВОЗМОЖНЫЙ ПОРЯДОК ПО МОДУЛЮ~$m$, НАЗЫВАЕТСЯ \dfn{ПЕРВООБРАЗНЫМ ЭЛЕМЕНТОМ}
ПО МОДУЛЮ~$m$\note{2}%
{нЕ СЛЕДУЕТ ПУТАТЬ ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ С ПЕРВООБРАЗНЫМ КОРНЕМ.
 пЕРВООБРАЗНЫЕ КОРНИ СУЩЕСТВУЮТ НЕ ДЛЯ ВСЕХ~$m$.---{\sl пРИМ. РЕД.\/}
}.

оБОЗНАЧИМ ЧЕРЕЗ~$\lambda(m)$ ПОРЯДОК ПЕРВООБРАЗНОГО ЭЛЕМЕНТА, Т.~Е.\
МАКСИМАЛЬНО ВОЗМОЖНЫЙ ПОРЯДОК ПО МОДУЛЮ~$m$. пРЕДЫДУЩИЕ ЗАМЕЧАНИЯ
ПОКАЗЫВАЮТ, ЧТО~$\lambda(p^e)$ ЕСТЬ ДЕЛИТЕЛЬ~$p^{e-1}(p-1)$;
НЕ СОСТАВЛЯЕТ ТРУДА (СМ.~НИЖЕ УПР.~11--16) ПРИВЕСТИ
ТОЧНЫЕ ЗНАЧЕНИЯ~$\lambda(m)$ В СЛЕДУЮЩИХ СЛУЧАЯХ:
$$
\eqalignrem{
& \lambda(2)=1, \quad \lambda(4)=2, \quad \lambda(2^e)=2^{e-2}, & ЕСЛИ $e\ge3$,\cr
& \lambda(p^e)=p^{e-1}(p-1), & ЕСЛИ $p>2$, \cr
& \lambda(p_1^{e_1}\ldots p_t^{e_t})=\НОК(\lambda(p_1^{e_1},\ldots, \lambda(p_t^{e_t}))).\cr
}
\eqno(9)
$$

нАШИ ЗАМЕЧАНИЯ МОЖНО СУММИРОВАТЬ В СЛЕДУЮЩЕЙ ТЕОРЕМЕ:

\proclaim тЕОРЕМА~B. (р. кАРМАЙКЛ)
[R. D. Carmichael, {\sl Bull.\ Amer.\ Math.\ Soc.,\/} {\bf 16} (1910), 232--238].
мАКСИМАЛЬНО ВОЗМОЖНЫЙ ПРИ~$c=0$ ПЕРИОД РАВЕН~$\lambda(m)$,
ГДЕ~$\lambda(m)$ ОПРЕДЕЛЯЕТСЯ ВЫРАЖЕНИЯМИ~(9). тАКОЙ ПЕРИОД РЕАЛИЗУЕТСЯ, ЕСЛИ
\medskip
\item{i)}~$X_0$ И~$m$---ВЗАИМНО ПРОСТЫЕ ЧИСЛА;
\item{ii)}~$a$---ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ ПО МОДУЛЮ~$m$. \endmark

%% 34

зАМЕТЬТЕ, ЧТО ЕСЛИ~$m$---ПРОСТОЕ ЧИСЛО, МОЖНО ПОЛУЧИТЬ ДЛИНУ ПЕРИОДА~$m-1$,
ЧТО ВСЕГО ЛИШЬ НА ЕДИНИЦУ МЕНЬШЕ МАКСИМАЛЬНОГО ЗНАЧЕНИЯ.

вОПРОС ТЕПЕРЬ ЗАКЛЮЧАЕТСЯ В ТОМ, КАК НАХОДИТЬ ПЕРВООБРАЗНЫЕ ЭЛЕМЕНТЫ ПО
МОДУЛЮ~$m$. иЗ УПРАЖНЕНИЙ В КОНЦЕ ПАРАГРАФА ВЫТЕКАЕТ

\proclaim тЕОРЕМА~C. чИСЛО~$a$ ЕСТЬ ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ ПО МОДУЛЮ~$p^e$
ТОГДА И ТОЛЬКО ТОГДА, КОГДА
\medskip
\item{i)}~$p^e=2$, $a$---НЕЧЕТНОЕ; ИЛИ~$p^e=4$, $a \bmod 4=3$; ИЛИ~$p^e=8$,
 $a \bmod 8=3, 5, 7$; ИЛИ~$p=2$, $e \ge 4$, $a \bmod 8=3$ ИЛИ~$5$;
 %
\hiddenpar\noindent ИЛИ
\item{ii)}~$p$---НЕЧЕТНОЕ, $e=1$, $a \not\equiv 0 \pmod{p}$
И~$a^{(p-1)q} \not\equiv 1 \pmod{p}$ ДЛЯ ЛЮБОГО ПРОСТОГО ДЕЛИТЕЛЯ~$q$ ЧИСЛА~$p-1$;
 %
\hiddenpar\noindent ИЛИ
\item{iii)}~$p$---НЕЧЕТНОЕ, $e>1$, $a$~УДОВЛЕТВОРЯЕТ~(ii)
И~$a^{p-1} \not\equiv 1 \pmod{p^2}$\note{1}%
{пОДРАЗУМЕВАЕТСЯ, ЧТО~$p$--- ПРОСТОЕ; ЕСЛИ МОДУЛЬ ИМЕЕТ ВИД~$2$, $2^2$,
$p^e$, ГДЕ~$p$---НЕЧЕТНОЕ, ПЕРВООБРАЗНЫЕ ЭЛЕМЕНТЫ БУДУТ И ПЕРВООБРАЗНЫМИ
КОРНЯМИ.---{\sl  пРИМ. РЕД.\/}
}. \endmark

уСЛОВИЯ~(ii) И~(iii) ЭТОЙ ТЕОРЕМЫ ЛЕГКО ПРОВЕРЯЮТСЯ НА ВЫЧИСЛИТЕЛЬНОЙ
МАШИНЕ ДЛЯ БОЛЬШИХ ЗНАЧЕНИЙ~$p$, ЕСЛИ ДЛЯ ВЫЧИСЛЕНИЯ СТЕПЕНЕЙ ИСПОЛЬЗОВАТЬ
ЭФФЕКТИВНЫЕ МЕТОДЫ, ОБСУЖДАЕМЫЕ В П.~4.6.3. нАКОНЕЦ, ЕСЛИ НАМ ДАНЫ
ВЕЛИЧИНЫ~$a_j$, ЯВЛЯЮЩИЕСЯ ПЕРВООБРАЗНЫМИ ЭЛЕМЕНТАМИ ПО МОДУЛЮ~$p_j^{e_j}$,
МОЖНО НАЙТИ ЕДИНСТВЕННОЕ ЗНАЧЕНИЕ~$a$, ТАКОЕ,
ЧТО~$a \equiv a_j \pmod{p_j^{e_j}}$, $1\le j \le t$, ПРИМЕНЯЯ "КИТАЙСКУЮ ТЕОРЕМУ
ОБ ОСТАТКАХ", КОТОРАЯ ОБСУЖДАЕТСЯ В~П.4.3.2. сЛЕДОВАТЕЛЬНО, $a$~БУДЕТ
ПЕРВООБРАЗНЫМ ЭЛЕМЕНТОМ ПО МОДУЛЮ~$p_1^{e_1}\ldots p_t^{e_t}$. эТО ДАЕТ
НАМ ДОВОЛЬНО ЭФФЕКТИВНЫЙ СПОСОБ
ВЫЧИСЛЕНИЯ МНОЖИТЕЛЕЙ, УДОВЛЕТВОРЯЮЩИХ УСЛОВИЮ ТЕОРЕМЫ~в,
ДЛЯ ЛЮБОГО ЗНАЧЕНИЯ~$m$. оДНАКО В ОБЩЕМ СЛУЧАЕ ВЫЧИСЛЕНИЯ ОКАЗЫВАЮТСЯ
НЕСКОЛЬКО ДЛИННЫМИ.

дЛЯ ВАЖНОГО СЛУЧАЯ~$m=2^e$ ПРИ~$e\ge 4$ ПРИВЕДЕННЫЕ ВЫШЕ УСЛОВИЯ СВОДЯТСЯ
К ЕДИНСТВЕННОМУ ПРОСТОМУ ТРЕБОВАНИЮ,
ЧТОБЫ~$a \equiv 3\hbox{ ИЛИ } 5 \pmod{8}$.
в ЭТОМ СЛУЧАЕ ЧЕТВЕРТАЯ ЧАСТЬ ВСЕХ ВОЗМОЖНЫХ МНОЖИТЕЛЕЙ ДАЕТ
МАКСИМАЛЬНЫЙ ПЕРИОД.

вТОРОЙ НАИБОЛЕЕ РАСПРОСТРАНЕННЫЙ СЛУЧАЙ, ЭТО~$m=10^e$. пОЛЬЗУЯСЬ ЛЕММАМИ~р
И~Q, НЕТРУДНО ПОЛУЧИТЬ НЕОБХОДИМЫЕ И
ДОСТАТОЧНЫЕ УСЛОВИЯ ДОСТИЖЕНИЯ МАКСИМАЛЬНОГО ПЕРИОДА ДЛЯ ДЕСЯТИЧНОЙ
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЫ.

\proclaim тЕОРЕМА~D. еСЛИ~$m=10^e$, $e\ge 5$, $c=0$ И~$X_0$ НЕ КРАТНО~$2$
ИЛИ~$5$, ПЕРИОД ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
РАВЕН~$5\times10^{e-2}$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, КОГДА~$a \bmod 200$
ПРИНИМАЕТ ОДНО
%% 35
ИЗ СЛЕДУЮЩИХ $32$~ЗНАЧЕНИЙ:
$$
\eqalign{
& 3,11,13,19,21,27, 29, 37, 53,59, 61, 67, 69,77, 83,91,109,117,\cr
& 123,131,133,139,141,147,163,171,173,179,181,187,189.197.~\endmark\cr
}
\eqno(10)
$$

\excercises
\ex[10] кАКОВА ДЛИНА ПЕРИОДА ЛИНЕЙНОЙ КОНГРУЭНТНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ С~$X_0=5772156648$, $a=3141592621$, $c=2718281829$, $m=10000000000$?

\ex[10] гАРАНТИРУЕТ ЛИ ВЫПОЛНЕНИЕ СЛЕДУЮЩИХ ДВУХ УСЛОВИЙ:
(i)~$c$~НЕЧЕТНОЕ, (ii)~$a\bmod 4=1$, МАКСИМАЛЬНУЮ ДЛИНУ ПЕРИОДА,
КОГДА~$m=2^e$, Т.~Е.\ СТЕПЕНЬ ДВОЙКИ?

\ex[13] пРЕДПОЛОЖИМ, ЧТО~$m=10^e$, ГДЕ~$e\ge 3$, А~$c$  НЕ КРАТНО НИ~$2$,
НИ~$5$. пОКАЖИТЕ, ЧТО ЛИНЕЙНАЯ КОНГРУЭНТНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ БУДЕТ ИМЕТЬ
МАКСИМАЛЬНО БОЛЬШОЙ ПЕРИОД ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$a\bmod 20=1$.

\ex[20] чЕМУ РАВНО ЗНАЧЕНИЕ~$X_{2^{e-1}}$, ЕСЛИ~$a$ И~$c$ УДОВЛЕТВОРЯЮТ
УСЛОВИЯМ ТЕОРЕМЫ~A, $m=2^e$, $X_0=0$?

\rex[20] нАЙДИТЕ ВСЕ МНОЖИТЕЛИ~$a$, УДОВЛЕТВОРЯЮЩИЕ УСЛОВИЯМ ТЕОРЕМЫ~A,
КОГДА~$m=2^{35}+1$ (ПРОСТЫЕ МНОЖИТЕЛИ ЧИСЛА~$m$ МОЖНО НАЙТИ ИЗ ТАБЛ.~3.2.1.1-1).

\ex[20] нАЙДИТЕ ВСЕ МНОЖИТЕЛИ~$a$, УДОВЛЕТВОРЯЮЩИЕ УСЛОВИЯМ ТЕОРЕМЫ~A,
ПРИ~$m=10^6-1$ (СМ.~ТАБЛ.~3.2.1.1-1).

\rex[м24] пЕРИОД КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ НЕ ОБЯЗАТЕЛЬНО НАЧИНАТЬ
С~$X_0$. оДНАКО МЫ ВСЕГДА МОЖЕМ НАЙТИ ИНДЕКСЫ~$\mu\ge0$, $\lambda>0$,
ТАКИЕ, ЧТО~$X_{n+\lambda}=X_n$ ДЛЯ ЛЮБЫХ~$n\ge\mu$, ПРИЧЕМ~$\mu$
И~$\lambda$---НАИМЕНЬШИЕ ЗНАЧЕНИЯ, ОБЛАДАЮЩИЕ ЭТИМ СВОЙСТВОМ.
(сР.~С~УПР.~3.1-6 И~3.2.1-1.) пУСТЬ~$\mu_j$, $\lambda_j$ СООТВЕТСТВУЮТ
ПОСЛЕДОВАТЕЛЬНОСТИ~$(X_0 \bmod p_j^{e_j}, a \bmod p_j^{e_j},
c \bmod p_j^{e_j},  p_j^{e_j})$ И~$\mu$, $\lambda$
СООТВЕТСТВУЮТ ПОСЛЕДОВАТЕЛЬНОСТИ~$(X_0, a, c, p_1^{e_1}\ldots p_t^{e_t})$;
ЛЕММА~Q УСТАНАВЛИВАЕТ, ЧТО $\lambda$~ЕСТЬ НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ
ДЛЯ~$\lambda_1$,~\dots, $\lambda_t$. чЕМУ РАВНО ЗНАЧЕНИЕ~$\mu$, ВЫРАЖЕННОЕ
ЧЕРЕЗ~$\mu_1$,~\dots, $\mu_t$? кАКОЕ МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ~$\mu$ МОЖНО
ПОЛУЧИТЬ, ИЗМЕНЯЯ~$X_0$, $a$ И~$c$ ПРИ
ФИКСИРОВАННОМ~$m=p_1^{e_1}\ldots p_t^{e_t}$?

\ex[м20] пОКАЖИТЕ, ЧТО ЕСЛИ~$a \bmod 4=3$, $e>1$,
ТО~$(a^{2^{e-1}}-1)/(a-1) \equiv 0 \pmod{2^e}$. (иСПОЛЬЗУЙТЕ ЛЕММУ~P.)

\rex[м22] (у.~тОМСОН.) дЛЯ~$c=0$ И~$m=2^e\ge 8$ ТЕОРЕМЫ~B И~C УТВЕРЖДАЮТ,
ЧТО ДЛИНА ПЕРИОДА РАВНА~$2^{e-2}$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ, КОГДА
МНОЖИТЕЛЬ~$a$ УДОВЛЕТВОРЯЕТ СООТНОШЕНИЯМ~$a\bmod 8=3$ ИЛИ~$a \bmod 8=5$.
пОКАЖИТЕ, ЧТО КАЖДАЯ ТАКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ В СУЩНОСТИ ЯВЛЯЕТСЯ
ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ С~$m=2^{e-2}$, ИМЕЮЩЕЙ
\emph{ПОЛНЫЙ} ПЕРИОД В СЛЕДУЮЩЕМ СМЫСЛЕ:
\medskip
\item{a)}~ЕСЛИ~$X_{n+1}=(4c+1) X_n \bmod 2^e$ И~$X_n=4Y_n+1$, ТО
$$
Y_{n+1}=((4c+1) Y_n+c) \bmod 2^{e-2};
$$
\item{b)}~ЕСЛИ~$X_{n+1}=(4c-1)X_n \bmod 2^e$ И~$X_n=((-1)^n (4Y_n+1))
\bmod 2^e$,  ТО
$$
Y_{n+1}=((1-4c)Y_n-c)\bmod 2^{e-2}.
$$
[\emph{зАМЕЧАНИЕ.} в ЭТИХ ФОРМУЛАХ~$c$---НЕЧЕТНОЕ ЦЕЛОЕ. в ЛИТЕРАТУРЕ МОЖНО
ВСТРЕТИТЬ УТВЕРЖДЕНИЯ О ТОМ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ С~$c=0$, УДОВЛЕТВОРЯЮЩИЕ
%%  36
УСЛОВИЯМ ТЕОРЕМЫ~B, НЕСКОЛЬКО БОЛЕЕ СЛУЧАЙНЫ, ЧЕМ ТЕ, КОТОРЫЕ
УДОВЛЕТВОРЯЮТ УСЛОВИЯМ ТЕОРЕМЫ а, НЕСМОТРЯ НА ТО, ЧТО В СЛУЧАЕ ТЕОРЕМЫ~B
ПЕРИОД В ЧЕТЫРЕ РАЗА МЕНЬШЕ. эТО УПРАЖНЕНИЕ ОПРОВЕРГАЕТ ПОДОБНЫЕ УТВЕРЖДЕНИЯ.]

\ex[м21] дЛЯ КАКИХ ЗНАЧЕНИЙ~$m$ СПРАВЕДЛИВО РАВЕНСТВО~$\lambda(m)=\varphi(m)$?

\ex[м28] пУСТЬ~$x$---НЕЧЕТНОЕ ЦЕЛОЕ ЧИСЛО, БОЛЬШЕЕ~$1$.
  %
\hiddenpar
(a)~пОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ ЕДИНСТВЕННОЕ ЦЕЛОЕ~$f>1$, ТАКОЕ, ЧТО
$x\equiv 2^f \pm 1 \pmod{2^{f+1}}$.
  %
\hiddenpar
(b)~пРИ УСЛОВИИ, ЧТО~$1<x<2^e-1$, А~$f$---СООТВЕТСТВУЮЩЕЕ ЦЕЛОЕ ЧИСЛО
ИЗ~П.(a), ПОКАЖИТЕ, ЧТО ПОРЯДОК~$x \pmod{2^e}$ РАВЕН~$2^{e-f}$.
  %
\hiddenpar
(c)~в ЧАСТНОСТИ, ЭТО ДОКАЗЫВАЕТ ТЕОРЕМУ~C(i).

\ex[м26] пУСТЬ~$p$---НЕЧЕТНОЕ ПРОСТОЕ ЧИСЛО дОКАЖИТЕ ЧТО ЕСЛИ~$e>1$,
ТО~$a$---ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ ПО МОДУЛЮ~$p^e$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ,
КОГДА~$a$---ПЕРВООБРАЗНЫЙ  ЭЛЕМЕНТ ПО МОДУЛЮ~$p$ И~$a^{p-1}\equiv 1 \pmod{p^2}$.
(пРЕДПОЛОЖИТЕ, ЧТО~$\lambda(p^e)=p^{e-1}(p-1)$. эТО ДОКАЗЫВАЕТСЯ НИЖЕ В
УПР.~14 И~16.

\ex[м22] пУСТЬ~$p$---ПРОСТОЕ ЧИСЛО И~$a$ НЕ ЯВЛЯЕТСЯ ПЕРВООБРАЗНЫМ
ЭЛЕМЕНТОМ ПО МОДУЛЮ~$p$. пОКАЖИТЕ, ЧТО ЛИБО~$a$ КРАТНО~$p$
ЛИБО~$a^{(p-1)/q}\equiv 1 \pmod{p}$ ДЛЯ НЕКОТОРОГО ПРОСТОГО ЧИСЛА~$q$,
ДЕЛЯЩЕГО~$p-1$.

\ex[м18] пУСТЬ~$e>1$, $p$---НЕЧЕТНОЕ ПРОСТОЕ И~$a$---ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ ПО
МОДУЛЮ~$p$, ДОКАЖИТЕ, ЧТО ТОГДА ЛИБО~$a$, ЛИБО~$a+p$---ПЕРВООБРАЗНЫЙ
ЭЛЕМЕНТ ПО МОДУЛЮ~$p^e$. [\emph{уКАЗАНИЕ:} СМ.~УПР.~12.]

\ex[м29] (a)~пУСТЬ~$a_1$, $a_2$ ВЗАИМНО ПРОСТЫЕ С~$m$. пУСТЬ ДЛЯ ЭТИХ
ЧИСЕЛ  ПОРЯДКИ ПО МОДУЛЮ~$m$ РАВНЫ~$\lambda_1$, $\lambda_2$ СООТВЕТСТВЕННО.
дОКАЖИТЕ ЧТО ЕСЛИ~$\lambda$---НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ~$\lambda_1$
И~$\lambda_2$, ТО~$a_1^{\kappa_1}a_2^{\kappa_2}$ ИМЕЕТ ПОРЯДОК~$\lambda$
ПО МОДУЛЮ~$m$ ДЛЯ ВЫБРАННЫХ НАДЛЕЖАЩИМ ОБРАЗОМ~$\kappa_1$, $\kappa_2$.
[\emph{уКАЗАНИЕ}. рАССМОТРИТЕ СНАЧАЛА СЛУЧАЙ, КОГДА~$\lambda_1$
И~$\lambda_2$---ВЗАИМНО ПРОСТЫЕ ЧИСЛА.]
(b)~пУСТЬ~$\lambda(m)$---МАКСИМАЛЬНЫЙ ПО ВСЕМ ЭЛЕМЕНТАМ ПОРЯДОК ПО
МОДУЛЮ~$m$. дОКАЖИТЕ, ЧТО~$\lambda(m)$ КРАТНО ПОРЯДКУ ПО МОДУЛЮ~$m$ ДЛЯ
ЛЮБОГО ЭЛЕМЕНТА. дРУГИМИ СЛОВАМИ, ДОКАЖИТЕ,
ЧТО~$a^{\lambda(m)} \equiv 1 \pmod{m}$ ДЛЯ ЛЮБОГО~$a$, ВЗАИМНО ПРОСТОГО С~$m$.

\rex[м24] пУСТЬ~$p$---ПРОСТОЕ ЧИСЛО.
(a)~пУСТЬ~$f(x)=x^n+c_1 x^{n-1}+\cdots+c_n$, ГДЕ ВСЕ~$c$---ЦЕЛЫЕ ЧИСЛА,
И ЗАДАНО ТАКОЕ ЦЕЛОЕ~$a$, ЧТО~$f(a) \equiv 0 \pmod{p}$.
пОКАЖИТЕ, ЧТО СУЩЕСТВУЕТ ПОЛИНОМ~$q(x)=x^n+q_1x^{n-2}+\cdots+q_{n-1}$ С ЦЕЛЫМИ
КОЭФФИЦИЕНТАМИ, ТАКОЙ, ЧТО~$f(x)\equiv (x-a)q(x) \pmod{p}$ ДЛЯ ВСЕХ ЦЕЛЫХ~$x$.
(b)~пУСТЬ~$f(x)$---ПОЛИНОМ, ТaКОЙ Жe, КaК И В~(a). пoКАЖИТЕ, ЧТО~$f(x)$
ИМЕЕТ  САМОЕ БОЛЬШЕЕ $n$~РАЗЛИЧНЫХ "КОРНЕЙ" ПО МОДУЛЮ~$p$, Т.Е.\
СУЩЕСТВУЕТ САМОЕ БОЛЬШЕЕ $n$~ЦЕЛЫХ ЧИСЕЛ~$a$, ТАКИХ,
ЧТО~$f(a)\equiv 0 \pmod{p}$, $0\le a < p$.
(c)~в УПР.~15(b) УТВЕРЖДАЕТСЯ, ЧТО ПОЛИНОМ~$f(x)=x^{\lambda(p)}-1$ ИМЕЕТ
$p-1$~РАЗЛИЧНЫХ КОРНЕЙ; СЛЕДОВАТЕЛЬНО, СУЩЕСТВУЕТ ЦЕЛОЕ~$a$ С ПОРЯДКОМ~$p-1$.

\ex[м26] нЕ ВСЕ ЗНАЧЕНИЯ, ПЕРЕЧИСЛЕННЫЕ В ТЕОРЕМЕ~D МОЖНО ПОЛУЧИТЬ
МЕТОДОМ, ИЗЛОЖЕННЫМ В ТЕКСТЕ. нАПРИМЕР, ЧИСЛО~$11$ НЕ ЯВЛЯЕТСЯ
ПЕРВООБРАЗНЫМ ЭЛЕМЕНТОМ ПО МОДУЛЮ~$5^e$. кАК ЭТО МОЖЕТ БЫТЬ ЕСЛИ~$11$ (В
СООТВЕТСТВИИ  С ТЕОРЕМОЙ~D)---ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ ПО МОДУЛЮ~$10^e$?
кАКИЕ ИЗ ЧИСЕЛ, ПЕРЕЧИСЛЕННЫХ В ТЕОРЕМЕ~D,---ПЕРВООБРАЗНЫЕ ЭЛЕМЕНТЫ КАК ПО
МОДУЛЮ~$2^e$, ТАК И~$5^e$?

\ex[м25] дОКАЖИТЕ ТЕОРЕМУ~D. (сР.\ С ПРЕДЫДУЩИМ УПРАЖНЕНИЕМ.)

\ex[40] сОСТАВЬТЕ ТАБЛИЦУ НЕКОТОРЫХ ХОРОШИХ МНОЖИТЕЛЕЙ~$a$ ДЛЯ КАЖДОГО ИЗ
ЗНАЧЕНИЙ~$m$, ПЕРЕЧИСЛЕННЫХ В ТАБЛ.~3.2.1.1-1, В ПРЕДПОЛОЖЕНИИ~$c=0$.

\ex[м24] кАКОВА ДЛИНА ПЕРИОДА ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ,
ДЛЯ КОТОРОЙ (i)~$X_0=0$; (ii)~$a$---ПЕРВООБРАЗНЫЙ ЭЛЕМЕНТ ПО
МОДУЛЮ~$p_j^{e_j}$, $1\le i \le t$; ДЛЯ ВСЕХ СТЕПЕНЕЙ ПРОСТЫХ ЧИСЕЛ В
РАЗЛОЖЕНИИ~$m=p_1^{e_1}\ldots p_t^{e_t}$ НА ПРОСТЫЕ МНОЖИТЕЛИ; (iii)~$c$
И~$m$ ВЗАИМНО ПРОСТЫ?

\subsubsubchap{мОЩНОСТЬ\note{1}%
{в ОРИГИНАЛЕ "potency",--- {\sl пРИМ. ПЕРЕВ.\/}}}%3.2.1.3
 в ПРЕДЫДУЩЕМ РАЗДЕЛЕ МЫ ПОКАЗАЛИ, ЧТО МАКСИМАЛЬНЫЙ ПЕРИОД МОЖНО ПОЛУЧИТЬ
ПРИ~$b=a-1$, КРАТНОМ
%% 37
ВСЕМ ПРОСТЫМ ДЕЛИТЕЛЯМ ЧИСЛА~$m$ ($b$ ТАКЖЕ ДОЛЖНО БЫТЬ КРАТНО~$4$, ЕСЛИ
$m$~ДЕЛИТСЯ НА~$4$). еСЛИ~$z$---ОСНОВАНИЕ, КОТОРОЕ ИСПОЛЬЗУЕТСЯ В МАШИНЕ
(ТАК, $z=2$---ДЛЯ ДВОИЧНОЙ МАШИНЫ И~$z=10$---ДЛЯ ДЕСЯТИЧНОЙ), А~$m$---РАЗМЕР
СЛОВА~$z^e$ МАШИНЫ, ТО МНОЖИТЕЛЬ
$$
a=z^k+1, \rem{$2\le k < e$,}
\eqno(1)
$$
УДОВЛЕТВОРЯЕТ ЭТИМ УСЛОВИЯМ. иЗ ТЕОРЕМЫ~3.2.1.2.A ТАКЖЕ СЛЕДУЕТ, ЧТО
МОЖНО ПРИНЯТЬ~$c=1$. рЕКУРРЕНТНОЕ СООТНОШЕНИЕ ТЕПЕРЬ ИМЕЕТ ВИД
$$
X_{n+1}=((z^k+1)X_n+1) \bmod z^e.
\eqno(2)
$$

пРИ ВЫЧИСЛЕНИЯХ МОЖНО ИЗБЕЖАТЬ УМНОЖЕНИЯ; ДОСТАТОЧНО ПРОСТОГО СЛОЖЕНИЯ И СДВИГА.

нАПРИМЕР, ПРЕДПОЛОЖИМ, ЧТО~$a=B^2+1$, ГДЕ~$B$---РАЗМЕР БАЙТА \MIX. вМЕСТО
КОМАНД, ПРИВЕДЕННЫХ В~П.3.2.1.1, МОЖНО НАПИСАТЬ ТАКУЮ ПРОГРАММУ:
$$
\vcenter{
\mixcode
LDA  & X
SLA  & 2
ADD  & X
INCA & 1
\endmixcode
}
\eqno(3)
$$
вРЕМЯ ЕЕ ВЫПОЛНЕНИЯ УМЕНЬШАЕТСЯ С~$16u$ ДО~$7u$.

вВИДУ СКАЗАННОГО МНОЖИТЕЛИ ВИДА~(1) ШИРОКО ОБСУЖДАЛИСЬ В ЛИТЕРАТУРЕ И
РЕКОМЕНДОВАЛИСЬ МНОГИМИ АВТОРАМИ. оДНАКО ПОЧТИ ПЯТИЛЕТНИЕ ПРОВЕРОЧНЫЕ
ЭКСПЕРИМЕНТЫ ПОКАЗЫВАЮТ, ЧТО \emph{СЛЕДУЕТ ИЗБЕГАТЬ МНОЖИТЕЛЕЙ, ИМЕЮЩИХ
ТАКОЙ ПРОСТОЙ ВИД, КАК~(1)}. пРИЧИН ЗДЕСЬ НЕСКОЛЬКО. пРЕЖДЕ ВСЕГО ВРЕМЯ
СЧЕТА НЕ УМЕНЬШАЕТСЯ НА САМОМ ДЕЛЕ ВДВОЕ, КАК ЭТО ПРОИСХОДИТ В
ПРИМЕРЕ~(3). еСЛИ ДОБАВИТЬ К ПРОГРАММЕ КОМАНДЫ~|JMP|, |STJ|, |STA|, |JNOV|,
СРАВНИТЕЛЬНЫЕ ВРЕМЕНА СЧЕТА БУДУТ РАВНЫ~$22u$ ДЛЯ МУЛЬТИПЛИКАТИВНОГО
МЕТОДА И~$13u$ ДЛЯ МЕТОДА, ИСПОЛЬЗУЮЩЕГО СЛОЖЕНИЕ И СДВИГ. кРОМЕ ЭТОГО,
НЕОБХОДИМО УЧЕСТЬ ВРЕМЯ РАБОТЫ ОСНОВНОЙ ПРОГРАММЫ, ИСПОЛЬЗУЮЩЕЙ СЛУЧАЙНЫЕ
ЧИСЛА. чИСТАЯ ЭКОНОМИЯ МАШИННОГО ВРЕМЕНИ В ПРОЦЕНТАХ ПОЧТИ НИЧТОЖНА. а НА
МНОГИХ СОВРЕМЕННЫХ МАШИНАХ УМНОЖЕНИЕ ВЫПОЛНЯЕТСЯ \emph{БЫСТРЕЕ,} ЧЕМ СДВИГ
И СЛОЖЕНИЕ!

сАМЫЙ ВЕСКИЙ АРГУМЕНТ, ПРЕПЯТСТВУЮЩИЙ ИСПОЛЬЗОВАНИЮ МНОЖИТЕЛЯ
ВИДА~$z^k+1$, ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ОН ПРИВОДИТ К НЕДОСТАТОЧНО
СЛУЧАЙНЫМ ЧИСЛАМ. оДНА ИЗ ПРИЧИН ЭТОГО СВЯЗАНА С КОНЦЕПЦИЕЙ "МОЩНОСТИ",
КОТОРУЮ МЫ СЕЙЧАС ОБСУДИМ.

\dfn{мОЩНОСТЬ} ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ
ПЕРИОДОМ ОПРЕДЕЛЯЕТСЯ КАК НАИМЕНЬШЕЕ ЦЕЛОЕ ЧИСЛО~$s$, ТАКОЕ, ЧТО
$$
b^s \equiv 0 \pmod{m}.
\eqno(4)
$$
%% 38
(тАКОЕ ЦЕЛОЕ~$s$ ВСЕГДА СУЩЕСТВУЕТ, ЕСЛИ МНОЖИТЕЛЬ УДОВЛЕТВОРЯЕТ УСЛОВИЯМ
ТЕОРЕМЫ~3.2.1.2A, В ЧАСТНОСТИ, ЕСЛИ $b$~КРАТНО ЛЮБОМУ ПРОСТОМУ ДЕЛИТЕЛЮ~$m$.)

мЫ МОЖЕМ АНАЛИЗИРОВАТЬ СЛУЧАЙНОСТЬ ПОСЛЕДОВАТЕЛЬНОСТИ, ПРИНИМАЯ~$X_0=0$,
ТАК КАК НУЛЬ ОБЯЗАТЕЛЬНО ВСТРЕЧАЕТСЯ НА ПРОТЯЖЕНИИ ЕЕ ПЕРИОДА. в ТАКОМ
СЛУЧАЕ ИМЕЕМ~$X_n=((a^n-1)c/b)\bmod m$ И, РАЗЛОЖИВ~$a^n-1=(b+1)^n-1$ ПО
ФОРМУЛЕ БИНОМА, НАХОДИМ
$$
X_n=c\left(n+\perm{n}{2}b+\cdots+\perm{n}{s}b^{s-1}\right) \bmod m.
\eqno(5)
$$
вСЕ ЧЛЕНЫ С~$b^s$, $b^{s+1}$ И Т.~Д.\ МОЖНО ОПУСТИТЬ, ТАК КАК ОНИ КРАТНЫ~$m$.

иСХОДЯ ИЗ УРАВНЕНИЯ~(5), РАССМОТРИМ НЕКОТОРЫЕ ЧАСТНЫЕ СЛУЧАИ. еСЛИ~$a=1$,
МОЩНОСТЬ РАВНА~$1$ И, КАК МЫ УЖЕ ВИДЕЛИ,
$X_n \equiv cn \pmod{m}$, ТАК ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ ЯВНО НЕ СЛУЧАЙНАЯ.
еСЛИ МОЩНОСТЬ РАВНА~$2$, ИМЕЕМ~$X_n \equiv cn+cb\perm{n}{2}$, И
СНОВА ПОСЛЕДОВАТЕЛЬНОСТЬ НЕЛЬЗЯ СЧИТАТЬ СЛУЧАЙНОЙ. дЕЙСТВИТЕЛЬНО,
$$
X_{n+1}-X_n \equiv c+cbn,
$$
ТАК ЧТО РАЗНОСТЬ МЕЖДУ СОСЕДНИМИ СЛУЧАЙНЫМИ ЧИСЛАМИ ВЫРАЖАЕТСЯ ОЧЕНЬ
ПРОСТОЙ ЗАВИСИМОСТЬЮ ОТ~$n$. еСЛИ
$$
d=cb \bmod m,
$$
ТОЧКА~$(X_n, X_{n+1}, X_{n+2})$ ВСЕГДА ЛЕЖИТ НА ОДНОЙ ИЗ ЧЕТЫРЕХ
ПЛОСКОСТЕЙ В ТРЕХМЕРНОМ ПРОСТРАНСТВЕ:
$$
\eqalign{
x-2y+z &= d+m,\cr
x-2y+z &= d,\cr
x-2y+z &= d-m,\cr
x-2y+z &=d-2m.\cr
}
$$

еСЛИ МОЩНОСТЬ РАВНА~$3$, ПОСЛЕДОВАТЕЛЬНОСТЬ ВЫГЛЯДИТ НЕСКОЛЬКО БОЛЕЕ
СЛУЧАЙНОЙ. нО~$X_n$, $X_{n+1}$, И~$X_{n+2}$ ВСЕ ЕЩЕ СВЯЗАНЫ СИЛЬНОЙ
ЗАВИСИМОСТЬЮ. рАЗНОСТИ~$X_{n+1}-X_n$ ОБРАЗУЮТ ПОСЛЕДОВАТЕЛЬНОСТЬ С
МОЩНОСТЬЮ~$2$, И ТЕСТЫ ПОКАЗЫВАЮТ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ С МОЩНОСТЬЮ~$3$
ВСЕ ЕЩЕ НЕДОСТАТОЧНО ХОРОШИ. сООБЩАЛОСЬ, ЧТО ПРИЕМЛЕМЫЕ РЕЗУЛЬТАТЫ МОГУТ
БЫТЬ ПОЛУЧЕНЫ ДЛЯ ЗНАЧЕНИЯ МОЩНОСТИ, РАВНОГО~$4$ И ВЫШЕ, НО ЭТО
ОСПАРИВАЛОСЬ МНОГИМИ АВТОРАМИ. вИДИМО, ДЛЯ ДОСТАТОЧНО СЛУЧАЙНЫХ ЗНАЧЕНИЙ
ТРЕБУЕТСЯ МОЩНОСТЬ, РАВНАЯ ПО МЕНЬШЕЙ МЕРЕ~$5$.

пРЕДПОЛОЖИМ, НАПРИМЕР, ЧТО~$m=2$ И~$a=2^k+1$. тОГДА~$b=2^k$, ТАК ЧТО
ПРИ~$k \ge 18$ ЗНАЧЕНИЕ~$b^2=2^{2k}$ КРАТНО~$m$: МОЩНОСТЬ
РАВНА~$2$. еСЛИ~$k=17$, $16$,~\dots, $12$, МОЩНОСТЬ РАВНА~$3$, А
ПРИ~$k=11$, $10$, $9$ ДОСТИГАЕТСЯ ЗНАЧЕНИЕ~$4$. пОЭТОМУ С ТОЧКИ
ЗРЕНИЯ МОЩНОСТИ ЕДИНСТВЕННО ПРИЕМЛЕМЫ ТАКИЕ МНОЖИТЕЛИ, ДЛЯ КОТОРЫХ~$k\le 8$.
%% 39
эТО ЗНАЧИТ, ЧТО~$a\le 257$, А МЫ УВИДИМ ПОЗЖЕ, ЧТО
\emph{НЕБОЛЬШИХ} МНОЖИТЕЛЕЙ ТАКЖЕ СЛЕДУЕТ ИЗБЕГАТЬ. иТАК, ВСЕ
МНОЖИТЕЛИ ВИДА~$2^k+1$ ПРИ~$m=2^{35}$ ОКАЗЫВАЮТСЯ НЕПРИЕМЛЕМЫМИ.

пРИ БОЛЬШИХ РАЗМЕРАХ СЛОВА МНОЖИТЕЛИ ВИДА~$2^k+1$ ПРИНЯТЬ МОЖНО. бЫЛ
ИСПЫТАН И ОПИСАН В ЛИТЕРАТУРЕ ДАТЧИК С~$m=2^{47}$, $a=2^9+1$ И МОЩНОСТЬЮ,
РАВНОЙ~$6$ ({\sl CACM,\/} {\bf 4} (1961), 350--352).
нЕСМОТРЯ НА ЭТО, НАДО БЫТЬ ОЧЕНЬ ОСТОРОЖНЫМ С МНОЖИТЕЛЯМИ ТИПА~(1), ПОТОМУ
ЧТО ПОЧТИ ВСЕ ИЗВЕСТНЫЕ НЕНАДЕЖНЫЕ ДАТЧИКИ БЫЛИ ИМЕННО ТАКОГО ТИПА. в
ДЕЙСТВИТЕЛЬНОСТИ ДАЖЕ ПРИВЕДЕННЫЙ ПРИМЕР НЕ УДОВЛЕТВОРЯЕТ СТАТИСТИЧЕСКИМ
ТЕСТАМ П.3.3.4.

пРИ~$m$, РАВНОМ~$w\pm1$, ГДЕ~$w$---РАЗМЕР СЛОВА, $m$, ВООБЩЕ ГОВОРЯ, НЕ
РАЗЛАГАЕТСЯ НА ПРОИЗВЕДЕНИЯ ВЫСОКИХ СТЕПЕНЕЙ ПРОСТЫХ ЧИСЕЛ, ТАК ЧТО
БОЛЬШАЯ МОЩНОСТЬ НЕВОЗМОЖНА (СМ.\ ПРИМЕР~6). пОЭТОМУ В ЭТОМ СЛУЧАЕ
\emph{НЕ} СТОИТ ПОЛЬЗОВАТЬСЯ МЕТОДОМ МАКСИМАЛЬНОГО ПЕРИОДА, А СЛЕДУЕТ
ПРИМЕНЯТЬ МЕТОД ЧИСТОГО УМНОЖЕНИЯ С~$c=0$.

вСЕ ЕЩЕ ОСТАЕТСЯ МНОГО СВОБОДЫ В ВЫБОРЕ МНОЖИТЕЛЯ. вООБЩЕ ГОВОРЯ, МЫ ХОТИМ
СОХРАНИТЬ МОЩНОСТЬ ВЫСОКОЙ, МНОЖИТЕЛЬ ДОСТАТОЧНО БОЛЬШИМ И, КРОМЕ ТОГО,
ИЗБЕЖАТЬ СЛИШКОМ ПРОСТОГО ПО ВИДУ НАБОРА ЦИФР В МНОЖИТЕЛЕ. пРЕДПОЛОЖИМ,
ЧТО~$m=2^{35}$, А ОПЕРАЦИЯ УМНОЖЕНИЯ УСКОРЯЕТСЯ ПРИ УМЕНЬШЕНИИ
КОЛИЧЕСТВА "ЕДИНИЧНЫХ" БИТОВ В МНОЖИТЕЛЕ. мОЖНО РЕКОМЕНДОВАТЬ
(ЭКСПЕРИМЕНТАЛЬНО) ТАКОЙ МНОЖИТЕЛЬ, КАК~$2^{23}+2^{14}+2^2+1$.
чЛЕН~$2^{23}$ ДЕЛАЕТ МНОЖИТЕЛЬ ДОВОЛЬНО БОЛЬШИМ. чЛЕН~$2^2$ ОБЕСПЕЧИВАЕТ
ВЫСОКУЮ МОЩНОСТЬ. еДИНИЦА НЕОБХОДИМА ДЛЯ ПОЛУЧЕНИЯ МАКСИМАЛЬНОГО ПЕРИОДА,
А $2^{14}$~ДОБАВЛЯЕТСЯ, ЧТОБЫ МНОЖИТЕЛЬ НЕ ОКАЗАЛСЯ СЛИШКОМ ПРОСТЫМ ДЛЯ
ВЫРАБОТКИ ДОСТАТОЧНО СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (СР.~УПР.~8). чЛЕН,
ПОДОБНЫЙ~$2^{34}$, БЫЛ БЫ ЗДЕСЬ НЕ СТОЛЬ ХОРОШ, КАК~$2^{23}$, ТАК КАК В
ПРОИЗВЕДЕНИИ~$2^{34}X_n$ ИСПОЛЬЗУЕТСЯ ТОЛЬКО САМЫЙ МЛАДШИЙ БИТ ЧИСЛА~$X_n$
(КОТОРЫЙ НЕ СЛИШКОМ СЛУЧАЕН). еСЛИ СКОРОСТЬ УМНОЖЕНИЯ НЕ ЯВЛЯЕТСЯ
ЛИМИТИРУЮЩЕЙ, БОЛЕЕ "СЛУЧАЙНЫЙ" МНОЖИТЕЛЬ (НАПРИМЕР, $a=3141592621$),
ВЕРОЯТНО, ОКАЖЕТСЯ ЗНАЧИТЕЛЬНО БОЛЕЕ УДОВЛЕТВОРИТЕЛЬНЫМ.

в ДЕЙСТВИТЕЛЬНОСТИ КОНЦЕПЦИЯ МОЩНОСТИ ДАЕТ ТОЛЬКО ОДИН ИЗ КРИТЕРИЕВ ВЫБОРА
МНОЖИТЕЛЯ; К НЕМУ МОЖНО ДОБАВИТЬ НЕМАЛО ДРУГИХ. нИЖЕ, В П.3.3.4,
ОБСУЖДАЕТСЯ "СПЕКТРАЛЬНЫЙ ТЕСТ" ДЛЯ МНОЖИТЕЛЕЙ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ. эТО---ВАЖНЫЙ КРИТЕРИЙ, ВКЛЮЧАЮЩИЙ, КАК ЧАСТНЫЕ СЛУЧАИ,
МОЩНОСТЬ И ВЕЛИЧИНУ МНОЖИТЕЛЯ. в П.3.3.4 МЫ, НАПРИМЕР, УВИДИМ,
ЧТО ВЫБОР~$2^{23}+2^{13}+2^2+1$ НАМНОГО ХУЖЕ, ЧЕМ~$2^{23}+2^{14}+2^2+1$.
лЮБОЙ МНОЖИТЕЛЬ, КОТОРЫЙ БУДЕТ ШИРОКО ИСПОЛЬЗОВАТЬСЯ, СЛЕДУЕТ ПРОВЕРИТЬ
СПЕКТРАЛЬНЫМ ТЕСТОМ.

\excercises
\ex[M10] пОКАЖИТЕ, ЧТО НЕЗАВИСИМО ОТ ТОГО, КАКИМ ОКАЖЕТСЯ РАЗМЕР БАЙТА~$B$
МАШИНЫ \MIX, ПРОГРАММА~(3) СЛУЖИТ ДАТЧИКОМ СЛУЧАЙНЫХ ЧИСЕЛ С
МАКСИМАЛЬНЫМ ПЕРИОДОМ.

%% 40
\ex[10] кАКОВА МОЩНОСТЬ ДАТЧИКА, РЕАЛИЗОВАННОГО \MIX-ПРОГРАММОЙ~(3)?

\ex[11] кАКОВА МОЩНОСТЬ ЛИНЕЙНОЙ КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ
ПРИ~$m=2^{35}$, $a=3141592621$? чЕМУ РАВНА МОЩНОСТЬ, ЕСЛИ
МНОЖИТЕЛЬ~$a=2^{23}+2^{13}+2^2+1$?

\ex[20] пОКАЖИТЕ, ЧТО, ЕСЛИ~$m=2^e\ge 8$, МАКСИМАЛЬНАЯ МОЩНОСТЬ
ДОСТИГАЕТСЯ ПРИ~$a \bmod 8 = 5$.

\ex[M20] дАНО, ЧТО~$m=p_1^{e_1}\ldots p_t^{e_t}$
И~$a=1+kp_1^{f_1}\ldots p_t^{f_t}$, ГДЕ~$a$ УДОВЛЕТВОРЯЕТ УСЛОВИЯМ
ТЕОРЕМЫ~3.2.1.2A, А~$k$ И~$m$ ВЗАИМНО ПРОСТЫ. пОКАЖИТЕ, ЧТО МОЩНОСТЬ
РАВНА~$\max(\ceil{e_1/f_1},~\ldots, \ceil{e_t/f_t})$.

\rex[20] кАКИЕ ИЗ ЗНАЧЕНИЙ~$m=w\pm1$ В ТАБЛ.~3.2.1.1-1 МОГУТ ДАТЬ
МОЩНОСТЬ, РАВНУЮ ПО МЕНЬШЕЙ МЕРЕ~$4$? (иСПОЛЬЗУЙТЕ РЕЗУЛЬТАТ УПР.~5.)

\ex[м20] еСЛИ ЧИСЛО~$a$ УДОВЛЕТВОРЯЕТ УСЛОВИЯМ ТЕОРЕМЫ~3.2.1.2A,
ОНО ВЗАИМНО ПРОСТО С~$m$; СЛЕДОВАТЕЛЬНО, СУЩЕСТВУЕТ ЧИСЛО~$a'$, ТАКОЕ,
ЧТО~$aa'\equiv 1 \pmod{m}$. пОКАЖИТЕ, ЧТО~$a'$ МОЖНО ПРОСТО ВЫРАЗИТЬ С
ПОМОЩЬЮ~$b$.

\rex[м26] дАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ С~$X_{n+1}=(2^{17}+3)X_n \bmod 2^{35}$
И~$X_0=1$ ПОДВЕРГЛИ СЛЕДУЮЩЕМУ ТЕСТУ. пУСТЬ~$Y_n=\floor{10X_n/2^{35}}$,
ТОГДА~$Y_n$ ДОЛЖНА БЫТЬ СЛУЧАЙНОЙ ЦИФРОЙ МЕЖДУ~$6$ И~$9$, А
ТРИАДЫ~$(Y_{3n}, Y_{3n+1}, Y_{3n+2})$ ДОЛЖНЫ ПРИНИМАТЬ ЛЮБОЕ ИЗ
$1000$~ВОЗМОЖНЫХ ЗНАЧЕНИЙ ОТ~$(0, 0, 0)$ ДО~$(9, 9, 9)$ С РАВНОЙ
ВЕРОЯТНОСТЬЮ. нО В $30\,000$~ПРОВЕРЕННЫХ ЧИСЕЛ НЕКОТОРЫЕ ТРИАДЫ
ВСТРЕЧАЛИСЬ ОЧЕНЬ РЕДКО, А НЕКОТОРЫЕ ПОЯВЛЯЛИСЬ ГОРАЗДО ЧАЩЕ ДРУГИХ. мОЖЕТЕ
ЛИ ВЫ ОБЎЯСНИТЬ ТАКОЙ СТРАННЫЙ РЕЗУЛЬТАТ?

\subsubchap{дРУГИЕ МЕТОДЫ} %3.2.2
кОНЕЧНО, ЛИНЕЙНЫЕ КОНГРУЭНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ---НЕ ЕДИНСТВЕННЫЙ ИЗ
ПРЕДЛОЖЕННЫХ ДЛЯ ВЫЧИСЛИТЕЛЬНЫХ МАШИН ИСТОЧНИКОВ СЛУЧАЙНЫХ ЧИСЕЛ. в ЭТОМ
ПУНКТЕ МЫ ПРИВЕДЕМ ОБЗОР ДРУГИХ НАИБОЛЕЕ ВАЖНЫХ МЕТОДОВ. нЕКОТОРЫЕ ИЗ НИХ
ДОСТАТОЧНО ВАЖНЫ ТОГДА КАК ДРУГИЕ ПРЕДСТАВЛЯЮТ ИНТЕРЕС ЛИШЬ ПОСТОЛЬКУ,
ПОСКОЛЬКУ ОКАЗЫВАЮТСЯ СОВСЕМ НЕ ТАКИМИ ХОРОШИМИ, КАК КАЖУТСЯ НА ПЕРВЫЙ ВЗГЛЯД.

оДНО ИЗ ОБЩЕПРИНЯТЫХ ЗАБЛУЖДЕНИЙ, С КОТОРЫМИ ПРИХОДИТСЯ СТАЛКИВАТЬСЯ,
КОГДА РЕЧЬ ИДЕТ О ПОЛУЧЕНИИ СЛУЧАЙНЫХ ЧИСЕЛ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО
ДОСТАТОЧНО ВЗЯТЬ ХОРОШИЙ ДАТЧИК И СЛЕГКА ЕГО ИЗМЕНИТЬ, ЧТОБЫ ВЫРАБОТАТЬ
"ЕЩЕ БОЛЕЕ СЛУЧАЙНУЮ" ПОСЛЕДОВАТЕЛЬНОСТЬ. дОВОЛЬНО ЧАСТО ЭТО НЕВЕРНО.
нАПРИМЕР, МЫ ЗНАЕМ ЧТО ПО ФОРМУЛЕ
$$
X_{n+1}=(aX_n+c) \bmod m
\eqno(1)
$$
МОЖНО ПОЛУЧИТЬ ДОВОЛЬНО ХОРОШИЕ СЛУЧАЙНЫЕ ЧИСЛА нЕ БУДЕТ ЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
X_{n+1}=((aX_n) \bmod (m+1)+c) \bmod m
\eqno(2)
$$
ЕЩЕ БОЛЕЕ СЛУЧАЙНОЙ? оТВЕТ ТАКОВ, ЧТО НОВАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ С БОЛЬШЕЙ
ВЕРОЯТНОСТЬЮ \emph{МЕНЕЕ} СЛУЧАЙНА. зАМЕТИМ, ЧТО ЦЕЛОСТНАЯ ТЕОРИЯ ДЛЯ НЕЕ
РУШИТСЯ, А В ОТСУТСТВИЕ КАКОЙ-ЛИБО ТЕОРИИ О ПОВЕДЕНИЯ
ПОСЛЕДОВАТЕЛЬНОСТИ~(2) МЫ ПОПАДАЕМ В ОБЛАСТЬ
ДАТЧИКОВ. ТИПА~$X_{n+1}=f(X_n)$ СО СЛУЧАЙНО ВЫБРАННОЙ ФУНКЦИЕЙ~$f$.
вМЕСТЕ С ТЕМ УПР.~3.1-11--3.1-15 ПОКАЗЫВАЮТ, ЧТО ЭТИ ПОСЛЕДОВАТЕЛЬНОСТИ
%% 41
ВЕДУТ СЕБЯ СОВСЕМ НЕ ТАК ХОРОШО, КАК ЕСЛИ БЫ ФУНКЦИЯ~(1) БЫЛА ЧЕТКО
ОПРЕДЕЛЕНА.

рАССМОТРИМ ДРУГОЙ ПОДХОД, ПЫТАЯСЬ ГЕНЕРИРОВАТЬ "БОЛЕЕ СЛУЧАЙНЫЕ" ЧИСЛА.
лИНЕЙНЫЙ КОНГРУЭНТНЫЙ МЕТОД МОЖНО ОБОБЩИТЬ, ПРЕВРАТИВ ЕГО, СКАЖЕМ, В
КВАДРАТИЧНЫЙ КОНГРУЭНТНЫЙ МЕТОД:
$$
X_{n+1}=(dX_n^2+aX_n+c) \bmod m.
\eqno(3)
$$

в УПР.~8 ОБОБЩАЕТСЯ ТЕОРЕМА~3.2.1.2A С ЦЕЛЬЮ ПОЛУЧИТЬ НЕОБХОДИМЫЕ И
ДОСТАТОЧНЫЕ УСЛОВИЯ ДЛЯ~$a$, $c$ И~$d$, ТАКИЕ, ЧТОБЫ ПОСЛЕДОВАТЕЛЬНОСТЬ,
ОПРЕДЕЛЕННАЯ СООТНОШЕНИЕМ~(3), ИМЕЛА БЫ МАКСИМАЛЬНЫЙ ПЕРИОД~$m$.
оГРАНИЧЕНИЯ ОКАЗЫВАЮТСЯ НЕ БОЛЕЕ ЖЕСТКИМИ, ЧЕМ В ЛИНЕЙНОМ МЕТОДЕ.

дЛЯ СЛУЧАЯ, КОГДА $m$~ПРЕДСТАВЛЯЕТСЯ СТЕПЕНЬЮ ДВОЙКИ, ИНТЕРЕСНЫЙ
КВАДРАТИЧНЫЙ МЕТОД ПРЕДЛОЖИЛ р.~кОВЭЮ. пУСТЬ
$$
X_0 \bmod 4 =2, \quad
X_{n+1}=X_n(X_n+1) \bmod 2^e, \rem{$n\ge 0$.}
\eqno(4)
$$
эТУ ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖНО ВЫЧИСЛЯТЬ ПОЧТИ С ТОЙ ЖЕ ЭФФЕКТИВНОСТЬЮ,
КАК И~(1), НЕ ЗАБОТЯСЬ О ПЕРЕПОЛНЕНИИ. оНА ИМЕЕТ ИНТЕРЕСНУЮ СВЯЗЬ С
ПЕРВОНАЧАЛЬНЫМ МЕТОДОМ СЕРЕДИНЫ КВАДРАТА ФОН нЕЙМАНА. вОЗЬМЕМ~$Y_n$,
РАВНОЕ~$2^eX_n$, ТАК ЧТО~$Y_n$---ЧИСЛО, ПРЕДСТАВЛЕННОЕ С ДВОЙНОЙ ТОЧНОСТЬЮ
ПУТЕМ ПРИПИСЫВАНИЯ СПРАВА $e$~НУЛЕЙ ДВОИЧНОМУ ПРЕДСТАВЛЕНИЮ~$X_n$.
тОГДА~$Y_{n+1}$ СОСТОИТ В ТОЧНОСТИ ИЗ $2e$~СРЕДНИХ ЦИФР
ЧИСЛА~$Y_n^2+2^eY_n$! тАКИМ ОБРАЗОМ, МЕТОД кОВЭЮ ПОЧТИ ИДЕНТИЧЕН МЕТОДУ
СЕРЕДИНЫ КВАДРАТА С ДВОЙНОЙ ТОЧНОСТЬЮ, С ТОЙ РАЗНИЦЕЙ, ЧТО ОН ГАРАНТИРУЕТ
БОЛЬШОЙ ПЕРИОД. мОЖНО ПРИВЕСТИ И ДАЛЬНЕЙШИЕ ДОКАЗАТЕЛЬСТВА СЛУЧАЙНОСТИ
ПОЛУЧАЕМОЙ ПОСЛЕДОВАТЕЛЬНОСТИ (СМ. УПР. 3.3.4-25).

дРУГИЕ ОБОБЩЕНИЯ СООТНОШЕНИЯ~(1) ТАКЖЕ ДОВОЛЬНО ОЧЕВИДНЫ. нАПРИМЕР, МЫ
МОГЛИ БЫ ПОПЫТАТЬСЯ УВЕЛИЧИТЬ ПЕРИОД ПОСЛЕДОВАТЕЛЬНОСТИ. пЕРИОД ЛИНЕЙНОЙ
КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ЧРЕЗВЫЧАЙНО ВЕЛИК. оБЫЧНО, ЕСЛИ
$m$~ПРИБЛИЖАЕТСЯ К РАЗМЕРУ МАШИННОГО СЛОВА, МЫ ИМЕЕМ ДЕЛО С ПЕРИОДАМИ
ПОРЯДКА~$10^9$ И БОЛЬШЕ, ТАК ЧТО В ТИПИЧНЫХ ЗАДАЧАХ ИСПОЛЬЗУЕТСЯ ТОЛЬКО
ОЧЕНЬ МАЛАЯ ЧАСТЬ ПОСЛЕДОВАТЕЛЬНОСТИ. с ДРУГОЙ СТОРОНЫ, ВЕЛИЧИНА
ПЕРИОДА ВЛИЯЕТ НА СТЕПЕНЬ СЛУЧАЙНОСТИ, КОТОРАЯ ДОСТИГАЕТСЯ В
ПОСЛЕДОВАТЕЛЬНОСТИ (СМ.\ ЗАМЕЧАНИЯ, ПРИВЕДЕННЫЕ ПОСЛЕ
СООТНОШЕНИЯ~3.3.4-13). пОЭТОМУ ОБЫЧНО МЫ СТРЕМИМСЯ ПОЛУЧАТЬ БОЛЬШОЙ ПЕРИОД,
ДЛЯ ЧЕГО И СУЩЕСТВУЕТ РЯД МЕТОДОВ. в ОДНОМ ИЗ НИХ ВВОДИТСЯ
ЗАВИСИМОСТЬ~$X_{n+1}$ ОТ~$X_n$ И~$X_{n-1}$ ВМЕСТО ПРОСТОЙ ЗАВИСИМОСТИ
ТОЛЬКО ОТ~$X_n$. тОГДА ДЛИНУ ПЕРИОДА МОЖНО УВЕЛИЧИТЬ ДО~$m^2$, ТАК
КАК ПОСЛЕДОВАТЕЛЬНОСТЬ НАЧНЕТ ПОВТОРЯТЬСЯ НЕ РАНЬШЕ, ЧЕМ БУДЕТ ВЫПОЛНЕНО
РАВЕНСТВО~$(X_{n+\lambda}, X_{n+\lambda+1})=(X_n, X_{n+1})$.

пРОСТЕЙШИЙ СЛУЧАЙ ЗАВИСИМОСТИ~$X_{n+1}$ ОТ БОЛЕЕ ЧЕМ ОДНОГО ИЗ ПРЕДЫДУЩИХ
ЗНАЧЕНИЙ РЕАЛИЗУЕТСЯ В ПОСЛЕДОВАТЕЛЬНОСТИ фИБОНАЧЧИ
$$
X_{n+1}=(X_n+X_{n-1}) \bmod m.
\eqno (5)
$$
%% 42
эТОТ ДАТЧИК РАССМАТРИВАЛСЯ В НАЧАЛЕ ПЯТИДЕСЯТЫХ ГОДОВ. оН ДАЕТ ОБЫЧНО
ДЛИНУ ПЕРИОДА, БОЛЬШУЮ, ЧЕМ~$m$. оДНАКО ТЕСТЫ С ОПРЕДЕЛЕННОСТЬЮ ПОКАЗАЛИ,
ЧТО ЧИСЛА, ПОЛУЧАЕМЫЕ ИЗ СООТНОШЕНИЯ фИБОНАЧЧИ~(5), ЯВЛЯЮТСЯ
\emph{НЕДОСТАТОЧНО} СЛУЧАЙНЫМИ. пОЭТОМУ В НАСТОЯЩЕЕ ВРЕМЯ ФОРМУЛА~(5)
ИНТЕРЕСНА ГЛАВНЫМ ОБРАЗОМ КАК ПРЕКРАСНЫЙ "ПЛОХОЙ ПРИМЕР".

мОЖНО ТАКЖЕ РАССМОТРЕТЬ ДАТЧИКИ ВИДА
$$
X_{n+1}=(X_n+X_{n-k}) \bmod m,
\eqno(6)
$$
ГДЕ~$k$---ДОСТАТОЧНО БОЛЬШОЕ ЧИСЛО, ПРЕДЛОЖЕННЫЕ гРИНОМ, сМИТОМ И кЛЕМОМ
(Green, Smith, Klem, {\sl JACM,\/} {\bf 6} (1959), 527--537).
пРИ СООТВЕТСТВУЮЩЕМ ВЫБОРЕ~$X_0$, $X_1$,~\dots, $X_k$ ЭТА ФОРМУЛА
ОБЕЩАЕТ СТАТЬ ИСТОЧНИКОМ ХОРОШИХ СЛУЧАЙНЫХ ЧИСЕЛ. нА ПЕРВЫЙ
ВЗГЛЯД СООТНОШЕНИЕ~(6) ВЫГЛЯДИТ НЕ СЛИШКОМ УДОБНЫМ ДЛЯ ИСПОЛЬЗОВАНИЯ В
МАШИНЕ, ТЕМ НЕ МЕНЕЕ СУЩЕСТВУЕТ ОЧЕНЬ ЭФФЕКТИВНАЯ ПРОЦЕДУРА ДЛЯ ЕЕ РЕАЛИЗАЦИИ.

\alg A.(аДДИТИВНЫЙ ДАТЧИК ЧИСЕЛ.) сНАЧАЛА В ЯЧЕЙКИ~$Z$, $Y[0]$, $Y[1]$,~\dots,
$Y[k]$ ЗАНОСЯТСЯ СООТВЕТСТВЕННО ЗНАЧЕНИЯ~$X_k$, $X_k$, $X_{k-1}$,~\dots,
$X_0$, А $j$~ПРИНИМАЕТСЯ РАВНЫМ~$k$. пОСЛЕДОВАТЕЛЬНОЕ ИСПОЛЬЗОВАНИЕ
АЛГОРИТМА ПРИВОДИТ К ПОЛУЧЕНИЮ ПОСЛЕДОВАТЕЛЬНОСТИ~$X_{k+1}$, $X_{k+2}$,
$\ldots\,$.
\st[$j<0$?] еСЛИ~$j<0$, УСТАНОВИТЬ~$j\asg k$.

\st[пРИБАВИТЬ,     ЗАМЕНИТЬ.]    уСТАНОВИТЬ~$Z\asg Y[j] \asg (Z+Y[j]) \bmod m$.

\st[уМЕНЬШИТЬ~$j$.] уМЕНЬШИТЬ~$j$ НА~$1$, ВЫДАТЬ~$Z$.
\algend

эТОТ АЛГОРИТМ НА ЯЗЫКЕ~\MIX{} ВЫГЛЯДИТ ТАК (ПРИ УСЛОВИИ, ЧТО ИНДЕКСНЫЙ
РЕГИСТР~6 НЕ ИСПОЛЬЗУЕТСЯ В ОСНОВНОЙ ПРОГРАММЕ):
$$
\vcenter{
\mixcode
J6NN & *+2  & A1. $j<0$?
ENT6 & K    & уСТАНОВИТЬ~$j\asg k$.
LDA  & Z    & A2. пРИБАВИТЬ, ЗАМЕНИТЬ.
ADD  & Y, 6 & $Z+Y[j]$ (ВОЗМОЖНО ПЕРЕПОЛНЕНИЕ)
STA  & Y, 6 & $\rasg Y[j]$.
STA  & Z    & $\rasg Z$.
DEC6 & 1    & A3. уМЕНЬШИТЬ~$j$.
\endmixcode
}
\eqno(7)
$$
эТОТ ДАТЧИК РАБОТАЕТ ОБЫЧНО БЫСТРЕЕ, ЧЕМ ДАТЧИКИ, РЕАЛИЗУЮЩИЕ ПРЕДЫДУЩИЕ
МЕТОДЫ, ТАК КАК ЗДЕСЬ НЕ ТРЕБУЕТСЯ НИКАКОГО УМНОЖЕНИЯ.

сЕЙЧАС О ТАКОМ АДДИТИВНОМ ДАТЧИКЕ ИЗВЕСТНО НЕМНОГО. пРЕЖДЕ ЧЕМ ЕГО МОЖНО
БУДЕТ РЕКОМЕНДОВАТЬ, СЛЕДУЕТ РАЗВИТЬ ТЕОРИЮ, ПОЗВОЛЯЮЩУЮ УСТАНОВИТЬ
НЕОБХОДИМЫЕ ПОКАЗАТЕЛИ СЛУЧАЙНОСТИ ВЫРАБАТЫВАЕМЫХ ЧИСЕЛ, И ПРОВЕСТИ
ШИРОКИЕ ИСПЫТАНИЯ ДЛЯ ОТДЕЛЬНЫХ ЗНАЧЕНИЙ~$k$ И~$X_0$, $X_1$,~\dots,
$X_k$. дЛИНА ПЕРИОДА ОБСУЖДАЕТСЯ В УПР.~11; ВООБЩЕ ГОВОРЯ, ОНА НЕ НАМНОГО
БОЛЬШЕ~$m$. в СТАТЬЕ
%% 43
гРИНА, сМИТА И кЛЕМА ГОВОРИТСЯ, ЧТО ПРИ~$k\le 15$ ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ
УДОВЛЕТВОРЯЕТ ТЕСТУ "ПРОВЕРКА ИНТЕРВАЛОВ", ОПИСАННОМУ В П.~3.3.2, ХОТЯ
ПРИ~$k=16$ ТЕСТ ПРОХОДИТ НОРМАЛЬНО.

сУЩЕСТВУЕТ ПОХОЖИЙ, НО ГОРАЗДО БОЛЕЕ ЭФФЕКТИВНЫЙ СПОСОБ УЛУЧШЕНИЯ
СЛУЧАЙНОСТИ ЛИНЕЙНЫХ КОНГРУЭНТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ,
ЕСЛИ~\emph{$m$---ПРОСТОЕ ЧИСЛО.} нАПРИМЕР, $m$~МОЖНО ВЫБРАТЬ КАК САМОЕ
БОЛЬШОЕ ПРОСТОЕ ЧИСЛО, КОТОРОЕ МОЖНО ЗАПИСАТЬ В МАШИННОМ СЛОВЕ. тАКОЕ
ЧИСЛО МОЖНО ВЫЧИСЛИТЬ ЗА ПРИЕМЛЕМОЕ ВРЕМЯ, ПРИМЕНЯЯ ТЕХНИКУ П.~4.5.4.
кОГДА~$m=p$---ПРОСТОЕ ЧИСЛО, ИЗ ТЕОРИИ КОНЕЧНЫХ ПОЛЕЙ СЛЕДУЕТ, ЧТО
СУЩЕСТВУЮТ ТАКИЕ МНОЖИТЕЛИ~$a_1$,~\dots, $a_k$, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ,
ОПРЕДЕЛЕННАЯ ФОРМУЛОЙ
$$
X_n=(a_1X_{n-1}+\cdots+a_kX_{n-k}) \bmod p,
\eqno(8)
$$
ИМЕЕТ ПЕРИОД ДЛИНЫ~$p^k-1$. зДЕСЬ~$X_0$,~\dots, $X_{k-1}$ МОГУТ БЫТЬ
ВЫБРАНЫ ПРОИЗВОЛЬНО, НО НЕ ДОЛЖНЫ БЫТЬ ВСЕ РАВНЫ НУЛЮ.
(чАСТНЫЙ СЛУЧАЙ~$k=1$ СООТВЕТСТВУЕТ МУЛЬТИПЛИКАТИВНОЙ КОНГРУЭНТНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ПО ПРОСТОМУ МОДУЛЮ, С КОТОРОЙ МЫ УЖЕ ЗНАКОМЫ.) вЫБОР
ПОСТОЯННЫХ~$a_1$,~\dots, $a_k$ В~(8) ТОГДА И ТОЛЬКО ТОГДА ДАЕТ ЖЕЛАЕМЫЙ
РЕЗУЛЬТАТ, КОГДА ПОЛИНОМ
$$
f(x)=x^k-a_1x^{k-1}-\cdots-a_k
\eqno(9)
$$
ЯВЛЯЕТСЯ \dfn{"ПРИМИТИВНЫМ МНОГОЧЛЕНОМ ПО МОДУЛЮ~$p$",} Т.~Е.\
ИМЕЕТ КОРЕНЬ, ЯВЛЯЮЩИЙСЯ \emph{ПЕРВООБРАЗНЫМ ЭЛЕМЕНТОМ ПОЛЯ ИЗ~$p^k$} ЭЛЕМЕНТОВ\note{1}%
{эТОТ ЭЛЕМЕНТ---ОБРАЗУЮЩАЯ МУЛЬТИПЛИКАТИВНОЙ ГРУППЫ ПОЛЯ гАЛУА, КОТОРАЯ, КАК
ИЗВЕСТНО, ЦИКЛИЧНА.--- {\sl пРИМ. РЕД.\/}} (СМ. УПР. 4.6.2-16).

кОНЕЧНО, ПРОСТОЙ ФАКТ \emph{СУЩЕСТВОВАНИЯ} ПОДХОДЯЩИХ КОНСТАНТ~$a_1$,~\dots,
$a_k$, ОБЕСПЕЧИВАЮЩИХ ДЛИНУ ПЕРИОДА~$p^k-1$, НЕДОСТАТОЧЕН ДЛЯ
ПРАКТИЧЕСКИХ ЦЕЛЕЙ. мЫ ДОЛЖНЫ УМЕТЬ \emph{НАХОДИТЬ} ИХ, НЕ ПЕРЕБИРАЯ ВСЕ
$p^k$~ВАРИАНТОВ, ТАК КАК $p$~ИМЕЕТ ПОРЯДОК РАЗМЕРА МАШИННОГО СЛОВА. к
СЧАСТЬЮ, СУЩЕСТВУЕТ В ТОЧНОСТИ~$\varphi(p^k-1)/k$ ПОДХОДЯЩИХ
КОМБИНАЦИЙ~$(a_1,~\ldots, a_k)$, ТАК ЧТО ИМЕЕТСЯ ДОВОЛЬНО БОЛЬШОЙ ШАНС
ОБНАРУЖИТЬ ОДНУ ИЗ НИХ ПОСЛЕ НЕСКОЛЬКИХ СЛУЧАЙНЫХ ПОПЫТОК. нО, КРОМЕ
ВСЕГО ПРОЧЕГО, НАМ НУЖНО УМЕТЬ БЫСТРО ОПРЕДЕЛИТЬ, ЯВЛЯЕТСЯ ЛИ~(9)
ПРИМИТИВНЫМ МНОГОЧЛЕНОМ ПО МОДУЛЮ~$p$. сОВЕРШЕННО НЕМЫСЛИМО ВЫРАБАТЫВАТЬ
$p^k-1$~ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТИ В ОЖИДАНИИ ПОВТОРЕНИЯ! мЕТОДЫ
ПРОВЕРКИ ТОГО, ЯВЛЯЕТСЯ ЛИ МНОГОЧЛЕН ПРИМИТИВНЫМ ПО МОДУЛЮ~$p$,
ОБСУЖДАЛИСЬ эЛАНЕНОМ И кНУТОМ
(Alanen, Knuth, {\sl Sankhy\=a\/}, Ser.~A, {\bf 26} (1964), 305--328).
мОЖНО ИСПОЛЬЗОВАТЬ СЛЕДУЮЩИЙ КРИТЕРИЙ.

пУСТЬ~$r=(p^k-1)/(p-1)$.
\medskip
\item{i)}~вЕЛИЧИНА~$(-1)^{k+1}a_k$ ДОЛЖНА БЫТЬ ПЕРВООБРАЗНЫМ КОРНЕМ ПО
МОДУЛЮ~$p$ (СР.~П.~3.2.1.2).

\item{ii)}~пОЛИНОМ~$x^r$ ДОЛЖЕН БЫТЬ СРАВНИМ С~$(-1)^{k+1}a_k$ ПО
МОДУЛЮ~$f(x)$ И~$p$.

%% 44
\item{iii)}~сТЕПЕНЬ~$x^{r/q} \bmod f(x)$, ГДЕ ПОДРАЗУМЕВАЕТСЯ
ПОЛИНОМИАЛЬНАЯ АРИФМЕТИКА ПО МОДУЛЮ~$p$, ДОЛЖНА БЫТЬ ПОЛОЖИТЕЛЬНОЙ ДЛЯ
ВСЯКОГО ПРОСТОГО ДЕЛИТЕЛЯ~$q$ ЧИСЛА~$r$.
\medskip
\noindent эФФЕКТИВНЫЕ МЕТОДЫ ВЫЧИСЛЕНИЯ~$x^n \bmod f(x)$, ИСПОЛЬЗУЮЩИЕ
ПОЛИНОМИАЛЬНУЮ АРИФМЕТИКУ ПО МОДУЛЮ ПРОСТОГО~$p$, ОБСУЖДАЮТСЯ В~П.~4.6.2.

чТОБЫ СДЕЛАТЬ ТАКУЮ ПРОВЕРКУ, НАМ НУЖНО ЗНАТЬ
ФАКТОРИЗАЦИЮ~$r=(p^k-1)/(p-1)$ С ПОМОЩЬЮ ПРОСТЫХ ЧИСЕЛ. эТО
ОГРАНИЧИВАЕТ ВОЗМОЖНОСТИ ВЫЧИСЛЕНИЙ. зА ПРИЕМЛЕМОЕ ВРЕМЯ МОЖНО
ФАКТОРИЗОВАТЬ~$r$ ПРИ~$k=2$, $3$ И, МОЖЕТ БЫТЬ, $4$, НО С БОЛЬШИМИ
ЗНАЧЕНИЯМИ~$k$, ЕСЛИ $p$~ВЕЛИКО, ТРУДНО ИМЕТЬ ДЕЛО. дАЖЕ ПРИ~$k=2$ ЧИСЛО
"ЗНАЧИМЫХ СЛУЧАЙНЫХ ЦИФР" УДВАИВАЕТСЯ ПО СРАВНЕНИЮ С~$k=1$. пОЭТОМУ
БОЛЬШИЕ ЗНАЧЕНИЯ~$k$ РЕДКО НЕОБХОДИМЫ.

дЛЯ ОЦЕНКИ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ, ПОЛУЧАЕМЫХ С ПОМОЩЬЮ~(8), МОЖНО
ВОСПОЛЬЗОВАТЬСЯ ВАРИАНТОМ СПЕКТРАЛЬНОГО ТЕСТА, ОПИСАННЫМ В П.~3.3.4
(СМ.~УПР.~3.3.4-26). иЗ ИЗЛОЖЕННОГО В ЭТОМ ПУНКТЕ СЛЕДУЕТ, ЧТО
\emph{НЕЦЕЛЕСООБРАЗНО} ОГРАНИЧИВАТЬСЯ ОЧЕВИДНЫМИ ЗНАЧЕНИЯМИ~$a_1=+1$
ИЛИ~$a_1=-1$, ДАЖЕ ЕСЛИ ЭТО ВОЗМОЖНО. лУЧШЕ ВЗЯТЬ БОЛЬШИЕ, СУЩЕСТВЕННО
"СЛУЧАЙНЫЕ" ЧИСЛА~$a_1$,~\dots, $a_k$, УДОВЛЕТВОРЯЮЩИЕ УСЛОВИЯМ, А ЗАТЕМ
ПРОВЕРИТЬ ВЫБОР С ПОМОЩЬЮ СПЕКТРАЛЬНОГО ТЕСТА. дЛЯ ОПРЕДЕЛЕНИЯ~$a_1$,~\dots,
$a_k$, ТРЕБУЕТСЯ ПРОВЕСТИ МНОГО ВЫЧИСЛЕНИЙ, НО ЕСТЬ ВСЕ
ОСНОВАНИЯ СЧИТАТЬ, ЧТО В РЕЗУЛЬТАТЕ МЫ ПОЛУЧИМ ВЕСЬМА УДОВЛЕТВОРИТЕЛЬНЫЙ
ИСТОЧНИК СЛУЧАЙНЫХ ЧИСЕЛ.

оСОБЫЙ ИНТЕРЕС ПРЕДСТАВЛЯЕТ ЗНАЧЕНИЕ~$p=2$. иНОГДА БЫВАЕТ НУЖЕН ДАТЧИК,
ПОРОЖДАЮЩИЙ СЛУЧАЙНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ \emph{БИТОВ}---НУЛЕЙ И ЕДИНИЦ
(В ОТЛИЧИЕ ОТ ДРОБЕЙ, ПРИНИМАЮЩИХ ЗНАЧЕНИЯ ОТ НУЛЯ ДО ЕДИНИЦЫ). сУЩЕСТВУЕТ
ПРОСТОЙ СПОСОБ ВЫРАБАТЫВАТЬ НА ДВОИЧНОЙ МАШИНЕ С $k\hbox{-РАЗРЯДНЫМИ}$
СЛОВАМИ ВЕСЬМА СЛУЧАЙНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ БИТОВ. нАЧИНАЕМ С
ПРОИЗВОЛЬНОГО ДВОИЧНОГО СЛОВА~$|Y|=(Y_1 Y_2 \ldots Y_k)_2$, ОТЛИЧНОГО ОТ
НУЛЯ. чТОБЫ ПОЛУЧИТЬ ОЧЕРЕДНОЙ СЛУЧАЙНЫЙ БИТ ПОСЛЕДОВАТЕЛЬНОСТИ, ПРОДЕЛАЕМ
СЛЕДУЮЩИЕ ОПЕРАЦИИ, ЗАПИСАННЫЕ НА ЯЗЫКЕ~\MIX:
$$
\vcenter{
\mixcode
LDA  & Y   & (пРЕДПОЛАГАЕМ, ЧТО СИГНАЛ ПЕРЕПОЛНЕНИЯ ВЫКЛЮЧЕН.)
ADD  & Y   & сДВИГ ВЛЕВО НА ОДИН РАЗРЯД.
JNOV & *+2 & пЕРЕХОД, ЕСЛИ В СТАРШЕМ РАЗРЯДЕ ВНАЧАЛЕ БЫЛ НУЛЬ.
XOR  & C   & в ПРОТИВНОМ СЛУЧАЕ КОРРЕКТИРУЕМ ЧИСЛО ОПЕРАЦИЕЙ "ИСКЛЮЧАЮЩЕЕ ИЛИ".
STA  & Y
\endmixcode
}
\eqno(10)
$$

чЕТВЕРТАЯ ПО ПОРЯДКУ ОПЕРАЦИЯ, "ИСКЛЮЧАЮЩЕЕ ИЛИ", ИМЕЕТСЯ ПОЧТИ НА ВСЕХ
ДВОИЧНЫХ МАШИНАХ (СР.~УПР.~2.5-28). оНА ИЗМЕНЯЕТ ЗНАЧЕНИЕ КАЖДОГО РАЗРЯДА,
СООТВЕТСТВУЮЩЕГО ТОМУ, ГДЕ |C|~СОДЕРЖИТ ЕДИНИЦУ, НА ОБРАТНОЕ. в
ЯЧЕЙКЕ~|C| НАХОДИТСЯ ДВОИЧНАЯ
%% 45
КОНСТАНТА~$(a_1\ldots{}a_k)_2$, ОПРЕДЕЛЯЮЩАЯ ПРИМИТИВНЫЙ МНОГОЧЛЕН
ПО МОДУЛЮ~$2$: $x^k-a_1x^{k-1}-\cdots-a_k$. пОСЛЕ ВЫПОЛНЕНИЯ
ПРОГРАММЫ~(10) В МЛАДШЕМ РАЗРЯДЕ~|Y| СОДЕРЖИТСЯ СЛЕДУЮЩИЙ БИТ
ПОСЛЕДОВАТЕЛЬНОСТИ (ЕСЛИ ЭТО БОЛЕЕ УДОБНО, МОЖНО, НАОБОРОТ,
ИСПОЛЬЗОВАТЬ СТАРШИЙ РАЗРЯД~|Y|). рАССМОТРИМ В КАЧЕСТВЕ ПРИМЕРА РИС.~1,
ИЛЛЮСТРИРУЮЩИЙ
$$\matrix{
 1011\cr
 0101\cr
 1010\cr
 0111\cr
 1110\cr
 1111\cr
 1101\cr
 1001\cr
 0001\cr
 0010\cr
 0100\cr
 1000\cr
 0011\cr
 0110\cr
 1100\cr
 1011\cr
}
$$
%% эТА МАТРИЦА И ЕСТЬ КАРТИНКА.
\picture{
  рИС.~1. пОСЛЕДОВАТЕЛЬНЫЕ СОСТОЯНИЯ МАШИННОГО СЛОВА~|Y| ПРИ ИСПОЛЬЗОВАНИИ
  ДВОИЧНОГО МЕТОДА ДЛЯ~$k=4$ И $c=|CONTENTS|(|C|)= (0011)_2$.
}
ПОЛУЧЕНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ ПРИ~$k=4$, $c=(0011)_2$ (ЭТО, КОНЕЧНО,
НЕСТАНДАРТНО МАЛОЕ ЗНАЧЕНИЕ~$k$). пРАВЫЙ СТОЛБЕЦ ТАБЛИЦЫ ПРЕДСТАВЛЯЕТ
ПОСЛЕДОВАТЕЛЬНОСТЬ БИТОВ, КОТОРАЯ ПОВТОРЯЕТСЯ С ПЕРИОДОМ~$2^k-1=15$:
$1101011110001001\ldots\,$. пОСЛЕДОВАТЕЛЬНОСТЬ ДОСТАТОЧНО СЛУЧАЙНАЯ,
ЕСЛИ УЧЕСТЬ, ЧТО ОНА ПОЛУЧЕНА С ПОМОЩЬЮ ЧЕТЫРЕХ РАЗРЯДОВ ПАМЯТИ. чТОБЫ
УБЕДИТЬСЯ В ЭТОМ, РАССМОТРИМ СОСЕДНИЕ ЧЕТВЕРКИ БИТОВ, ПОЯВЛЯЮЩИЕСЯ НА
ПРОТЯЖЕНИИ ПЕРИОДА, А ИМЕННО: $1101$, $1010$, $0101$, $1011$, $0111$,
$1111$, $1110$, $1100$, $1000$, $0001$, $0010$, $0100$, $1001$, $0011$,
$0110$. вООБЩЕ ГОВОРЯ, ТАК КАК ДЛИНА ПЕРИОДА РАВНА~$2^k-1$, КАЖДАЯ
ВОЗМОЖНАЯ КОМБИНАЦИЯ $k$~БИТОВ ВСТРЕЧАЕТСЯ ЗА ПЕРИОД ТОЧНО ОДИН РАЗ, ЗА
ИСКЛЮЧЕНИЕМ НАБОРА ИЗ ВСЕХ НУЛЕЙ. тАКИМ ОБРАЗОМ, СОСЕДНИЕ НАБОРЫ ИЗ
$k$~БИТОВ СУЩЕСТВЕННО НЕЗАВИСИМЫ. в \S~3.5 МЫ УВИДИМ, ЧТО СУЩЕСТВУЕТ
ОЧЕНЬ МОЩНЫЙ КРИТЕРИЙ СЛУЧАЙНОСТИ ДЛЯ~$k$, РАВНОГО, СКАЖЕМ, $30$ ИЛИ
БОЛЬШЕ. тЕОРЕТИЧЕСКИЕ РЕЗУЛЬТАТЫ, ИЛЛЮСТРИРУЮЩИЕ СЛУЧАЙНОСТЬ ЭТОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ, ПРИВОДЯТСЯ В СТАТЬЕ р.~тАУСВОРТА (R.~с.~Tausworthe,
{\sl Math. Comp.,\/} {\bf 19} (1965), 201--209).

пРИМИТИВНЫЕ МНОГОЧЛЕНЫ СТЕПЕНИ~$\le 100$ ПО МОДУЛЮ~$2$
БЫЛИ ПРОТАБУЛИРОВАНЫ э.~уОТСОНОМ (е.~J.~Watson, {\sl Math. Comp.,\/} {\bf 16}
(1962), 368--369). пРИ~$k=35$ МОЖНО ПРИНЯТЬ
$$
c = (00000000000000000000000000000000101)_2,
$$
%% 46
А ДЛЯ~$k=30$ МОЖНО ВЗЯТЬ
$$
c=(000000000000000000000001010011)_2.
$$
вСЕ ЖЕ, КАК СЛЕДУЕТ ИЗ УПР.~18 И~3.3.4-26, ДЛЯ ОПРЕДЕЛЕНИЯ ПРИМИТИВНЫХ
МНОГОЧЛЕНОВ ПО МОДУЛЮ~$2$ ЛУЧШЕ НАХОДИТЬ СУЩЕСТВЕННО "СЛУЧАЙНЫЕ" КОНСТАНТЫ~$c$.

\emph{пРЕДУПРЕЖДЕНИЕ:} нЕКОТОРЫЕ ПОПАДАЛИСЬ В ЛОВУШКУ,
ПЫТАЯСЬ ИСПОЛЬЗОВАТЬ МЕТОД ВЫРАБОТКИ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ БИТОВ
ДЛЯ ПОЛУЧЕНИЯ СЛУЧАЙНЫХ ДРОБЕЙ, ЗАНИМАЮЩИХ ЦЕЛОЕ
СЛОВО~$(.Y_0Y_1\ldots{}Y_{k-1})_2$,
$(.Y_kY_{k+1}\ldots{}Y_{2k-1})_2$,~$\ldots\,$. нА САМОМ ДЕЛЕ ЭТО ДОВОЛЬНО
ПЛОХОЙ СПОСОБ, ХОТЯ ОТДЕЛЬНЫЕ БИТЫ КАЖДОЙ ДРОБИ ВПОЛНЕ СЛУЧАЙНЫ (СМ.~УПР.~18)!

мЫ УЖЕ ВИДЕЛИ, ЧТО, КОГДА~$X_n$ ОПРЕДЕЛЯЕТСЯ ПОДХОДЯЩЕЙ ФУНКЦИЕЙ
ОТ~$X_{n-1}$,~\dots, $X_{n-k}$, МОЖНО НАЙТИ ТАКИЕ
ПОСЛЕДОВАТЕЛЬНОСТИ С~$0\le X_n < m$ И ПЕРИОДОМ~$m^k-1$, ГДЕ~$m$---ПРОСТОЕ
ЧИСЛО. нАИБОЛЬШИЙ ПЕРИОД, КОТОРЫЙ МОЖНО ПОЛУЧИТЬ ДЛЯ \emph{ПРОИЗВОЛЬНОЙ}
ПОСЛЕДОВАТЕЛЬНОСТИ, ОПРЕДЕЛЕННОЙ СООТНОШЕНИЕМ
$$
X_n=f(X_{n-1}, \ldots, X_{n-k}), \rem{$0\le X_n < m$,}
\eqno(11)
$$
КАК МОЖНО ВИДЕТЬ, РАВЕН~$m^k$. м.~мАРТИН (м.~H.~Martin
{\sl Bull. Amer. Math. Soc.,\/} {\bf 40} (1934), 859--864) ПЕРВЫЙ ПОКАЗАЛ,
ЧТО СУЩЕСТВУЮТ ФУНКЦИИ, ПОЗВОЛЯЮЩИЕ ДОСТИЧЬ ЭТОГО МАКСИМУМА ДЛЯ ЛЮБЫХ~$m$
И~$k$. еГО МЕТОД ЛЕГКО ОБОСНОВАТЬ, НО, К СОЖАЛЕНИЮ, ОН НЕУДОБЕН ДЛЯ
ПРОГРАММИРОВАНИЯ (СМ.~УПР.~17). иЗ ИЗВЕСТНЫХ ФУНКЦИЙ~$f$, ДАЮЩИХ
МАКСИМАЛЬНЫЙ ПЕРИОД~$m^k$, САМОЙ ПРОСТОЙ ЯВЛЯЕТСЯ ОПИСАННАЯ В УПР.~21.
сООТВЕТСТВУЮЩИЕ ПРОГРАММЫ, ВООБЩЕ ГОВОРЯ, НЕ ТАК ЭФФЕКТИВНЫ ДЛЯ ВЫРАБОТКИ
СЛУЧАЙНЫХ ЧИСЕЛ, КАК ПРИ РЕАЛИЗАЦИИ ДРУГИХ РАНЕЕ ОПИСАННЫХ МЕТОДОВ. вСЕ ЖЕ
ОНИ ПОЗВОЛЯЮТ ПРОДЕМОНСТРИРОВАТЬ ЯВНУЮ СЛУЧАЙНОСТЬ ПОСЛЕДОВАТЕЛЬНОСТИ
(КОГДА РЕЧЬ ИДЕТ О ПЕРИОДЕ В ЦЕЛОМ).

дРУГОЙ ВАЖНЫЙ КЛАСС МЕТОДОВ СВОДИТСЯ К \emph{КОМБИНАЦИИ} ДАТЧИКОВ
СЛУЧАЙНЫХ ЧИСЕЛ ДЛЯ ПОЛУЧЕНИЯ "ЕЩЕ БОЛЕЕ СЛУЧАЙНЫХ" ПОСЛЕДОВАТЕЛЬНОСТЕЙ.
вСЕГДА НАЙДУТСЯ СКЕПТИКИ, ПОЛАГАЮЩИЕ, ЧТО ЛИНЕЙНЫЕ КОНГРУЭНТНЫЕ МЕТОДЫ,
АДДИТИВНЫЕ МЕТОДЫ И Т.~Д.\ СЛИШКОМ ПРОСТЫ ДЛЯ ВЫРАБОТКИ ДОСТАТОЧНО
СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ. а ТАК КАК НЕВОЗМОЖНО \emph{ДОКАЗАТЬ,} ЧТО
ИХ СКЕПТИЦИЗМ НЕОПРАВДАН (ХОТЯ МЫ И ВЕРИМ, ЧТО ЭТО ТАК), ДОВОЛЬНО
БЕСПОЛЕЗНО ОСПАРИВАТЬ ПОДОБНОЕ МНЕНИЕ. сУЩЕСТВУЮТ ВПОЛНЕ
ЭФФЕКТИВНЫЕ МЕТОДЫ ДЛЯ ТОГО, ЧТОБЫ ПОЛУЧАТЬ ИЗ ДВУХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ НАСТОЛЬКО СЛУЧАЙНУЮ ТРЕТЬЮ, ЧТО ТОЛЬКО САМЫМ
ОТЎЯВЛЕННЫМ СКЕПТИКАМ ОНА МОЖЕТ НЕ ПОНРАВИТЬСЯ.

пРЕДПОЛОЖИМ, ЧТО МЫ ИМЕЕМ ДВЕ ПОСЛЕДОВАТЕЛЬНОСТИ~$X_0$, $X_1$,~\dots,
И~$Y_0$, $Y_1$,~\dots, СЛУЧАЙНЫХ ЧИСЕЛ, РАСПОЛОЖЕННЫХ МЕЖДУ НУЛЕМ И~$m-1$,
ПОЛУЧЕННЫЕ ДВУМЯ НЕЗАВИСИМЫМИ СПОСОБАМИ. оДНО ИЗ ПРЕДЛОЖЕНИЙ СВОДИТСЯ К
ТОМУ, ЧТОБЫ СКЛАДЫВАТЬ ЧИСЛА ПОПАРНО ПО
%% 47
МОДУЛЮ~$m$, ПОЛУЧАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ~$Z_n=(X_n+Y_n)\bmod m$. в ЭТОМ
СЛУЧАЕ ЖЕЛАТЕЛЬНО, ЧТОБЫ ДЛИНЫ ПЕРИОДОВ~$\<X_n>$ И~$\<Y_n>$ БЫЛИ ВЗАИМНО
ПРОСТЫМИ ЧИСЛАМИ (СМ.~УПР.~13).

мЕТОД, ПРЕДЛОЖЕННЫЙ мАКЛАРЕНОМ И мАРСАЛЬЕЙ ЗНАЧИТЕЛЬНО ЛУЧШЕ И УДИВИТЕЛЬНО
УДОБЕН ДЛЯ ПРОГРАММИРОВАНИЯ.

\alg M.(вПОЛНЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ.) пРИ ЗАДАННЫХ МЕТОДАХ
ВЫРАБОТКИ ДВУХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\<X_n>$ И~$\<Y_n>$ ЭТОТ МЕТОД
ПОЗВОЛЯЕТ ГЕНЕРИРОВАТЬ ЧЛЕНЫ "ЗНАЧИТЕЛЬНО БОЛЕЕ СЛУЧАЙНОЙ"
ПОСЛЕДОВАТЕЛЬНОСТИ. мЫ ИСПОЛЬЗУЕМ ВСПОМОГАТЕЛЬНУЮ ТАБЛИЦУ~$V[0]$, $V[1]$,~\dots,
$V[k-1]$, ГДЕ~$k$---НЕКОТОРОЕ ЧИСЛО, ВЫБИРАЕМОЕ ОБЫЧНО ДЛЯ
УДОБСТВА РАВНЫМ ПРИМЕРНО~$100$. сНАЧАЛА $V\hbox{-ТАБЛИЦА}$ ЗАПОЛНЯЕТСЯ
ПЕРВЫМИ $k$~ЗНАЧЕНИЯМИ $X\hbox{-ПОСЛЕДОВАТЕЛЬНОСТИ}$.

\st[вЫРАБОТАТЬ~$X$, $Y$.] уСТАНОВИТЬ В~$X$  И~$Y$ ЗНАЧЕНИЯ ОЧЕРЕДНЫХ
ЧЛЕНОВ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\<X_n>$ И~$\<Y_n>$ СООТВЕТСТВЕННО.

\st[вЫЧИСЛИТЬ~$j$.] уСТАНОВИТЬ~$j\asg \floor{kY/m}$, ГДЕ~$m$---МОДУЛЬ,
ИСПОЛЬЗУЮЩИЙСЯ В ПОСЛЕДОВАТЕЛЬНОСТИ~$\<Y_n>$. тАКИМ ОБРАЗОМ,
$j$~ПРИНИМАЕТ СЛУЧАЙНОЕ ЗНАЧЕНИЕ, ОПРЕДЕЛЯЕМОЕ С ПОМОЩЬЮ~$Y$; $0 \le j <k$.

\st[зАМЕНИТЬ.] вЫДАТЬ~$V[j]$ И УСТАНОВИТЬ~$V[j]\asg X$.
\algend

эТОТ МЕТОД МОЖНО УСИЛЕННО РЕКОМЕНДОВАТЬ. оН ПОЗВОЛЯЕТ ПОЛУЧАТЬ
НЕВЕРОЯТНО БОЛЬШИЕ ПЕРИОДЫ, ЕСЛИ ПЕРИОДЫ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$\<X_n>$
И~$\<Y_n>$ ВЗАИМНО ПРОСТЫЕ. и ДАЖЕ ЕСЛИ ДЛИНА ПЕРИОДА НЕ ОЧЕНЬ СУЩЕСТВЕННА,
СОСЕДНИЕ ЧЛЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ ПОЧТИ НЕ КОРРЕЛИРУЮТ ДРУГ С ДРУГОМ.
пРИЧИНОЙ ТОГО, ЧТО ЭТОТ МЕТОД НАМНОГО ПРЕВОСХОДИТ МЕТОД СЕРЕДИНЫ КВАДРАТА
ИЛИ МЕТОД, ОСНОВАННЫЙ НА СООТНОШЕНИИ~(2), ЯВЛЯЕТСЯ ДОСТАТОЧНАЯ
СЛУЧАЙНОСТЬ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$X_n$ И~$Y_n$, КОТОРЫЕ НЕ МОГУТ
ВЫРОЖДАТЬСЯ. чИТАТЕЛЮ РЕКОМЕНДУЕТСЯ РАЗОБРАТЬ УПР.~3, ЧТОБЫ УВИДЕТЬ,
КАК МЕТОД РАБОТАЕТ В ЧАСТНОМ СЛУЧАЕ.

нА МАШИНЕ~\MIX{} МОЖНО РЕАЛИЗОВАТЬ АЛГОРИТМ~M, ПРИНИМАЯ~$k$ НА ЕДИНИЦУ
БОЛЬШИМ МАКСИМАЛЬНОГО ЗНАЧЕНИЯ, РАЗМЕЩАЮЩЕГОСЯ В ОДНОМ БАЙТЕ (РАВНЫМ
РАЗМЕРУ БАЙТА). шАГИ~M2 И~M3 ЛЕГКО ПРОГРАММИРУЮТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\vcenter{
\mixcode
LD6 & Y(l:l) & $j\asg \hbox{СТАРШИЙ БАЙТ } Y$.
LDA & V, 6   & $|rA|\asg \hbox{СЛЕДУЮЩИЙ ЭЛЕМЕНТ НОВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.}$
LDX & х
STX & V,6    & $V[j]\asg X$.
\endmixcode
}
\eqno(12)
$$

дЛЯ ПРИМЕРА ПРЕДПОЛОЖИМ, ЧТО АЛГОРИТМ~M ПРИМЕНЯЕТСЯ К ТАКИМ ДВУМ
ПОСЛЕДОВАТЕЛЬНОСТЯМ С~$k=64$:
$$
\matrix{
 X_0=5772156649, & X_{n+1}=(3141592653 X_n + 2718281829) \bmod 2^{35};\cr
 Y_0=1781072418, & Y_{n+1}=(2718281829 Y_n + 3141592653) \bmod 2^{35}.\cr
}
$$
%% 48
мЫ УТВЕРЖДАЕМ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ, ПОЛУЧЕННАЯ С ПОМОЩЬЮ АЛГОРИТМА~M,
БУДЕТ УДОВЛЕТВОРЯТЬ ФАКТИЧЕСКИ \emph{ЛЮБОМУ} КРИТЕРИЮ СЛУЧАЙНОСТИ ДЛЯ
ГЕНЕРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНОЙ МАШИНОЙ ПОСЛЕДОВАТЕЛЬНОСТЕЙ. бОЛЕЕ ТОГО,
ВРЕМЯ ВЫРАБОТКИ ЧУТЬ БОЛЬШЕ ЧЕМ ВДВОЕ ПРЕВЫШАЕТ ВРЕМЯ ПОЛУЧЕНИЯ ОДНОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ~$<X_n>$.

ф.~гЕБХАРДТ ПОКАЗАЛ [F.~Gebhardt, {\sl Math. Comp.,\/} {\bf 21} (1967),708--709],
ЧТО АЛГОРИТМ~M ПОЗВОЛЯЕТ ПОЛУЧАТЬ УДОВЛЕТВОРИТЕЛЬНЫЕ
РЕЗУЛЬТАТЫ, ДАЖЕ ЕСЛИ ЕГО ПРИМЕНЯТЬ К ТАКИМ
НЕСЛУЧАЙНЫМ ПОСЛЕДОВАТЕЛЬНОСТЯМ, КАК ПОСЛЕДОВАТЕЛЬНОСТЬ фИБОНАЧЧИ
С~$X_n=F_2 \bmod m$ И~$Y_n=F_{2n+1} \bmod m$. дРУГОЙ СПОСОБ
КОМБИНИРОВАТЬ ДВЕ ПОСЛЕДОВАТЕЛЬНОСТИ ОСНОВАН НА ЦИКЛИЧЕСКОМ СДВИГЕ И
"ИСКЛЮЧАЮЩЕМ ИЛИ" В ДВОИЧНОЙ МАШИНЕ. еГО ПРЕДЛОЖИЛ
у.~уЭСТЛЭЙК (W.~J.~Westlake, {\sl JACM,\/} {\bf 14} (1967), 337--340).

\excercises
\rex[12] пРАКТИЧЕСКИ МЫ ПОЛУЧАЕМ СЛУЧАЙНЫЕ ЧИСЛА, ПОЛЬЗУЯСЬ
СООТНОШЕНИЕМ~$X_{n+1}=(aX_n+c) \bmod m$, ГДЕ~$X_n$---\emph{ЦЕЛЫЕ.} пОСЛЕ
ЧЕГО МЫ ОБРАЩАЕМСЯ С НИМИ, КАК С \emph{ДРОБЯМИ:} $U_n=X_n/m$. рЕКУРРЕНТНАЯ
ФОРМУЛА ДЛЯ~$U_n$ В ДЕЙСТВИТЕЛЬНОСТИ ТАКОВА:
$$
U_{n+1}=(aU_n+c/m) \bmod 1.
$$
оБДУМАЙТЕ \emph{ПРЯМОЕ} ИСПОЛЬЗОВАНИЕ ЭТОЙ ФОРМУЛЫ ДЛЯ ВЫРАБОТКИ СЛУЧАЙНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ С ПОМОЩЬЮ ОПЕРАЦИЙ С ПЛАВАЮЩЕЙ ТОЧКОЙ, ИМЕЮЩИХСЯ В МАШИНЕ.

\rex[м20] дЛЯ ХОРОШЕГО ИСТОЧНИКА СЛУЧАЙНЫХ ЧИСЕЛ
СООТНОШЕНИЕ~$X_{n-1}<X_{n+1}<X_n$ ДОЛЖНО ВЫПОЛНЯТЬСЯ ПРИМЕРНО В ТЕЧЕНИЕ
ОДНОЙ ШЕСТОЙ ВСЕГО ВРЕМЕНИ, ТАК КАК ВСЕ ВОЗМОЖНЫЕ ПОРЯДКОВЫЕ
КОМБИНАЦИИ~$X_{n-1}$, $X_n$ И~$X_{n+1}$ РАВНОВЕРОЯТНЫ. пОКАЖИТЕ, ЧТО
УКАЗАННЫЙ ВЫШЕ  ПОРЯДОК ТЕМ НЕ МЕНЕЕ \emph{НИКОГДА} НЕ ВСТРЕЧАЕТСЯ В
ПОСЛЕДОВАТЕЛЬНОСТИ фИБОНАЧЧИ~(5).

\ex[21] кАКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ПОЛУЧИТСЯ ПРИ ИСПОЛЬЗОВАНИИ АЛГОРИТМА~M,
ЕСЛИ~$X_0=0$, $X_{n+1}=(5X_n+3)\bmod 8$, $Y_0=0$, $Y_{n+1}=(5Y_n+1)\bmod8$
И~$k=4$? (зАМЕТЬТЕ, ЧТО МОЩНОСТЬ РАВНА ДВУМ, ТАК ЧТО ИСХОДНЫЕ~$<X_n>$
И~$\<Y_n>$ НЕ СЛИШКОМ СЛУЧАЙНЫ.)

\ex[00] пОЧЕМУ В ПЕРВОЙ КОМАНДЕ ПРОГРАММЫ~(12) ИСПОЛЬЗУЕТСЯ ИМЕННО СТАРШИЙ
БАЙТ, А НЕ КАКОЙ-НИБУДЬ ДРУГОЙ?

\rex[20] рАССМОТРИТЕ ВОЗМОЖНОСТЬ ИСПОЛЬЗОВАНИЯ УСЛОВИЯ~$X_n=Y_n$ ДЛЯ
УСКОРЕНИЯ РАБОТЫ АЛГОРИТМА~M.

\ex[10] в ТЕКСТЕ ПРИ ИССЛЕДОВАНИИ ДВОИЧНОГО МЕТОДА~(10) УТВЕРЖДАЕТСЯ, ЧТО
МЛАДШИЙ БИТ СЛОВА~$X$ СЛУЧАЕН, ЕСЛИ МНОГОКРАТНО ПРИМЕНЯТЬ ЭТОТ
МЕТОД. пОЧЕМУ НЕ СЛУЧАЙНО ВСЕ \emph{СЛОВО}~$X$?

\ex[20] пОКАЖИТЕ, ЧТО МОЖНО ПОЛУЧИТЬ ПОЛНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ
ДЛИНЫ~$2^e$ (Т.~Е.\ КАЖДЫЙ ИЗ $2^e$~ВОЗМОЖНЫХ ВАРИАНТОВ СОСЕДНИХ $e$~БИТОВ,
КОТОРЫЙ РЕАЛИЗУЕТСЯ ТОЛЬКО ОДИН РАЗ НА ПРОТЯЖЕНИИ ПЕРИОДА), ЕСЛИ
ИЗМЕНИТЬ ПРОГРАММУ~(10) СЛЕДУЮЩИМ ОБРАЗОМ:
%% !!! нЕПРИЯТНАЯ ШТУКА: ТАК КАК БЛОК \mixcode ВХОДИТ В АРГУМЕНТ МАКРОСА \ex,
%% ЕГО ТОКЕНЫ ПОЛУЧАЮТ КАТЕГОРИЮ, ДО ТОГО, КАК В \mixcode ПРОИЗОЙДЕТ
%% ВЫПОЛНЕНИЕ \obeylines. в ИТОГЕ КОНЦЫ СТРОК НЕ СЧИТАЮТСЯ \cr ? кАК ЭТО СДЕЛАТЬ?
$$
\vcenter{
\mixcode
LDA  & х   \cr
JANZ & *+2 \cr
LDA  & C   \cr
ADD  & X   \cr
JNOV & *+3 \cr
JAZ  & *+2 \cr
XOR  & C   \cr
STA  & X   \cr
\endmixcode
}
$$
%% 49

\ex[M39] дОКАЖИТЕ, ЧТО КВАДРАТИЧНАЯ КОНГРУЭНТНАЯ
ПОСЛЕДОВАТЕЛЬНОСТЬ~$(3)$ ИМЕЕТ ПЕРИОД ДЛИНЫ~$m$ ТОГДА И ТОЛЬКО ТОГДА,
КОГДА ВЫПОЛНЯЮТСЯ СЛЕДУЮЩИЕ УСЛОВИЯ:
\medskip
\item{i)}~$c$ И~$m$---ВЗАИМНО ПРОСТЫЕ ЧИСЛА;
\item{ii)}~$d$ И~$a-1$ КРАТНЫ~$p$---ВСЕМ НЕЧЕТНЫМ ПРОСТЫМ ДЕЛИТЕЛЯМ~$m$;
\item{iii)}~$d$---ЧЕТНОЕ И~$d\equiv a-1\pmod{4}$, ЕСЛИ~$m$ КРАТНО~$4$,
 $d\equiv a-1 \pmod{2}$, ЕСЛИ~$m$ КРАТНО~$2$;
\item{iv)}~ИЛИ~$d=0$, ИЛИ~$a\equiv 1$ И~$cd\equiv 6\pmod{9}$, ЕСЛИ~$m$
КРАТНО~$9$. [\emph{уКАЗАНИЕ.} пОСЛЕДОВАТЕЛЬНОСТЬ, ОПРЕДЕЛЕННАЯ
СООТНОШЕНИЯМИ~$X_0=0$, $X_{n+1}=dX_n^2+aX_n+c$, ИМЕЕТ ПО МОДУЛЮ~$m$ ПЕРИОД
ДЛИНЫ~$m$, ЕСЛИ ТОЛЬКО ЭТА ДЛИНА ПЕРИОДА РАВНА~$d$ ПО МОДУЛЮ~$d$,
ГДЕ~$d$---ПРОИЗВОЛЬНЫЙ ДЕЛИТЕЛЬ~$m$.]

\rex[м24] (р.~кОВЭЮ.) иСПОЛЬЗУЙТЕ РЕЗУЛЬТАТ УПР.~8, ЧТОБЫ ДОКАЗАТЬ, ЧТО В
МОДИФИЦИРОВАННОМ МЕТОДЕ СЕРЕДИНЫ КВАДРАТА~(4) ДЛИНА ПЕРИОДА РАВНА~$2^{e-2}$.

\ex[м29] пОКАЖИТЕ, ЧТО ЕСЛИ~$X_0$ И~$X_1$ НЕ ЯВЛЯЮТСЯ ОБА ЧЕТНЫМИ
И~$m=2^e$, ТО ПЕРИОД ПОСЛЕДОВАТЕЛЬНОСТИ фИБОНАЧЧИ~(5) РАВЕН~$3\cdot 2^{e-1}$.

\ex[м36] зАДАЧА ЭТОГО УПРАЖНЕНИЯ СОСТОИТ В ТОМ, ЧТОБЫ ПРОАНАЛИЗИРОВАТЬ
ОПРЕДЕЛЕННЫЕ СВОЙСТВА ЦЕЛОЧИСЛЕННЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ
РЕКУРРЕНТНОМУ СООТНОШЕНИЮ
$$
X_n=a_1X_{n-1}+\cdots+a_kX_{n-k}, \rem{$n\ge k$.}
$$
еСЛИ МЫ МОЖЕМ ВЫЧИСЛИТЬ ДЛИНУ ПЕРИОДА ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ПО
МОДУЛЮ~$m=p^e$, ГДЕ~$p$---ПРОСТОЕ ЧИСЛО, ТО ДЛИНА ПЕРИОДА ОТНОСИТЕЛЬНО
ПРОИЗВОЛЬНОГО МОДУЛЯ~$m$ РАВНА НАИМЕНЬШЕМУ ОБЩЕМУ КРАТНОМУ ДЛИН ПЕРИОДОВ,
ВЫЧИСЛЕННЫХ ОТНОСИТЕЛЬНО СТЕПЕНЕЙ ПРОСТЫХ СОМНОЖИТЕЛЕЙ~$m$.
\medskip
%
\item{a)}~пУСТЬ~$f(z)$, $a(z)$, $b(z)$)---ПОЛИНОМЫ С ЦЕЛОЧИСЛЕННЫМИ КОЭФФИЦИЕНТАМИ;
БУДЕМ ПИСАТЬ~$a(z)\equiv b(z) \pmod{f(z)\hbox{ И } m}$,
ЕСЛИ~$a(z)=b(z)+f(z)u(z)+mv(z)$ ДЛЯ НЕКОТОРЫХ ПОЛИНОМОВ~$u(z)$, $v(z)$ С
ЦЕЛОЧИСЛЕННЫМИ КОЭФФИЦИЕНТАМИ. дОКАЖИТЕ, ЧТО ПРИ~$f(0)=1$ И~$p^e>2$
СПРАВЕДЛИВО СЛЕДУЮЩЕЕ: "ЕСЛИ~$z^\lambda\equiv 1 \pmod{f(z)\hbox{ И }p^e}$,
$z^\lambda\not\equiv 1\pmod{f(z)\hbox{ И }p^{e+1}}$,
ТОГДА~$z^{p\lambda}\equiv 1 \pmod{f(z)\hbox{ И }p^{e+1}}$,
$z^{p\lambda}\not\equiv 1 \pmod{f(z)\hbox{ И } p^{e+2}}$".
%
\item{b)}~пУСТЬ
$$
\eqalign{
f(z)&=1-a_1z-\cdots-a_kz^k,\cr
G(z)&=1/f(z)=A_0+A_1z+A_2z^2+\ldots\,.\cr
}
$$
оБОЗНАЧИМ СИМВОЛОМ~$\lambda(m)$ ДЛИНУ ПЕРИОДА
ПОСЛЕДОВАТЕЛЬНОСТИ~$\<A_n\bmod m>$.  дОКАЖИТЕ, ЧТО~$\lambda(m)$---НАИМЕНЬШЕЕ
ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ~$\lambda$, ТАКОЕ, ЧТО~$z^\lambda\equiv 1
\pmod{f(z)\hbox{ И } m}$.
%
\item{c)}~пУСТЬ~$p$---ПРОСТОЕ, $p^e>2$ И~$\lambda(p^e)\ne \lambda(p^{e+1})$.
дОКАЖИТЕ, ЧТО~$\lambda(p^{e+r})=p^r\lambda(p^e)$ ДЛЯ ВСЕХ~$r\ge0$. (тАКИМ
ОБРАЗОМ, ЧТОБЫ НАЙТИ ДЛИНУ ПЕРИОДА ПОСЛЕДОВАТЕЛЬНОСТИ~$\<A_n \bmod 2^e>$,
МОЖНО ВЫЧИСЛЯТЬ~$\lambda(4)$, $\lambda(8)$, $\lambda(16)$,~\dots{}
ВРУЧНУЮ ДО ТЕХ ПОР, ПОКА МЫ НЕ НАЙДЕМ НАИМЕНЬШЕЕ~$r\ge2$, ТАКОЕ,
ЧТО~$\lambda(2^{r+1})\ne\lambda(4)$. тОГДА ДЛИНА ПЕРИОДА ОПРЕДЕЛЕНА
ПО~$\bmod 2^e$ ДЛЯ ВСЕХ~$e$.)
%
\item{d)}~пОКАЖИТЕ, ЧТО ЛЮБАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫХ ЧИСЕЛ,
УДОВЛЕТВОРЯЮЩАЯ РЕКУРРЕНТНОМУ СООТНОШЕНИЮ, ПРИВЕДЕННОМУ В НАЧАЛЕ
УПРАЖНЕНИЯ, ИМЕЕТ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$g(z)/f(z)$, ГДЕ~$g(z)$---НЕКОТОРЫЙ
ПОЛИНОМ С ЦЕЛОЧИСЛЕННЫМИ КОЭФФИЦИЕНТАМИ.
%
\item{e)}~пУСТЬ ПОЛИНОМЫ~$f(z)$ И~$g(z)$ ИЗ~(d) ВЗАИМНО ПРОСТЫЕ ПО
МОДУЛЮ~$p$ (СР.~П.~4.6.1). дОКАЖИТЕ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_n \bmod
p^e>$ ИМЕЕТ ДЛИНУ ПЕРИОДА В ТОЧНОСТИ ТАКУЮ ЖЕ, КАК И СПЕЦИАЛЬНАЯ
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<A_n \bmod p^e>$ В~(b). (нИКАКИМ ВЫБОРОМ~$X_0$,~\dots,
 $X_{k-1}$ НЕЛЬЗЯ ПОЛУЧИТЬ БОЛЕЕ ДЛИННЫЙ ПЕРИОД, ТАК КАК ОБЩАЯ
ПОСЛЕДОВАТЕЛЬНОСТЬ ПРЕДСТАВЛЯЕТСЯ ЛИНЕЙНОЙ КОМБИНАЦИЕЙ
"СДВИГОВ" СПЕЦИАЛЬНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.) [\emph{уКАЗАНИЕ.} сУЩЕСТВУЮТ
ПОЛИНОМЫ, ТАКИЕ, ЧТО~$a(z)f(z)+b(z)g(z)\equiv 1 \pmod{p^e}$. эТО СЛЕДУЕТ
ИЗ УПР.~4.6.2-22 (ЛЕММА гЕНЗЕЛЯ).]

\rex[м28] нАЙДИТЕ ЦЕЛЫЕ ЧИСЛА~$X_0$, $X_1$, $a$, $b$ И~$c$, ТАКИЕ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
X_{n+1}=(aX_n+bX_{n-1}+c)\bmod 2^e, \rem{$n\ge 1$,}
$$
%% 50
ИМЕЕТ САМЫЙ БОЛЬШОЙ ПЕРИОД ИЗ ВСЕХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЭТОГО ТИПА.
[\emph{уКАЗАНИЕ.} $X_{n+2}=((a+1)X_{n+1}+(b-a)X_n-bX_{n-1})\bmod 2^e$ сМ.~УПР.~11~(c).]

\ex[м20] пУСТЬ~$\<X_n>$ И~$\<Y_n>$--- ПОСЛЕДОВАТЕЛЬНОСТИ ЦЕЛЫХ ЧИСЕЛ ПО
МОДУЛЮ~$m$ С ПЕРИОДАМИ ДЛИНЫ~$\lambda_1$ И~$\lambda_2$; ОБРАЗУЕМ НОВУЮ
ПОСЛЕДОВАТЕЛЬНОСТЬ~$Z_n=(X_n+Y_n)\bmod m$. пОКАЖИТЕ, ЧТО, ЕСЛИ~$\lambda_1$
И~$\lambda_2$---ВЗАИМНО ПРОСТЫЕ ЧИСЛА, ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<Z_n>$ ИМЕЕТ
ДЛИНУ ПЕРИОДА~$\lambda_1\lambda_2$.

\ex[м24] пУСТЬ~$X_n$, $Y_n$, $Z_n$, $\lambda_1$, $\lambda_2$, ТАКИЕ ЖЕ,
КАК И В ПРЕДЫДУЩЕМ УПРАЖНЕНИИ. пРЕДПОЛОЖИМ,
ЧТО~$\lambda_1=2^{e_2}3^{e_3}5^{e_5}\ldots$---РАЗЛОЖЕНИЕ~$\lambda_1$ НА
ПРОСТЫЕ МНОЖИТЕЛИ, И АНАЛОГИЧНО~$\lambda_2=2^{f_2}3^{f_3}5^{f_5}\ldots\,$.
пУСТЬ~$\lambda_0=2^{g_2}3^{g_3}5^{g_5}\ldots$, ГДЕ~$g_p=(\max(e_p, f_p)$,
ЕСЛИ~$e_p\ne f_p$, И~$0$, ЕСЛИ~$e_p=f_p$). пОКАЖИТЕ, ЧТО
ПЕРИОД~$\lambda'$ ПОСЛЕДОВАТЕЛЬНОСТИ~$Z_n$  КРАТЕН~$\lambda_0$, НО
ЯВЛЯЕТСЯ ДЕЛИТЕЛЕМ~$\lambda$---НАИМЕНЬШЕГО ОБЩЕГО КРАТНОГО~$\lambda_1$,
$\lambda_2$. в ЧАСТНОСТИ, $\lambda'=\lambda$, ЕСЛИ
$(e_p\ne f_p \ror e_p=f_p=0)$ ДЛЯ ВСЯКОГО ПРОСТОГО~$p$.

\ex[м46] чТО МОЖНО СКАЗАТЬ ПО ПОВОДУ ДЛИНЫ ПЕРИОДА ПОСЛЕДОВАТЕЛЬНОСТИ,
 ВЫРАБАТЫВАЕМОЙ АЛГОРИТМОМ~M?

\rex[м28] пУСТЬ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ КОНСТАНТЫ~$c$, ФИГУРИРУЮЩЕЙ В
МЕТОДЕ~(10), ИМЕЕТ ВИД~$(a_1 a_2 \ldots a_k)_2$. пОКАЖИТЕ, ЧТО
ПОСЛЕДОВАТЕЛЬНОСТЬ БИТОВ~$Y_0$, $Y_1$,~\dots{} УДОВЛЕТВОРЯЕТ СООТНОШЕНИЮ
$$
Y_n=(a_1Y_{n-1}+a_2Y_{n-2}+\cdots+a_kY_{n-k}) \bmod 2.
$$
[эТo МОЖНО РАССМАТРИВАТЬ КАК ДРУГОЙ СПОСОБ ОПРЕДЕЛЕНИЯ
ПОСЛЕДОВАТЕЛЬНОСТИ. ХОТЯ НА ПЕРВЫЙ ВЗГЛЯД СВЯЗЬ МЕЖДУ ЭТИМ СООТНОШЕНИЕМ И
ЭФФЕКТИВНОЙ ПРОГРАММОЙ~(10) НЕ ОЧЕВИДНА!]

\ex[м33] (м.~мАРТИН, 1934.) пУСТЬ~$m, k\ge 1$---ЦЕЛЫЕ ЧИСЛА
И~$X_1=X_2=\ldots=X_k=0$. дЛЯ~$n>0$ ПОЛОЖИМ~$X_{n+k}$ РАВНЫМ НАИБОЛЬШЕМУ
НЕОТРИЦАТЕЛЬНОМУ ЗНАЧЕНИЮ~$y<m$, ТАКОМУ, ЧТО $k\hbox{-НАБОР}$ $(X_{n+1},~\ldots,
X_{n+k-1}, y)$ БОЛЬШЕ НЕ ВСТРЕЧАЕТСЯ В ПОСЛЕДОВАТЕЛЬНОСТИ. дРУГИМИ
СЛОВАМИ, $(X_{n+1},~\ldots, X_{n+k-1}, y)$ НЕ ДОЛЖЕН СОВПАДАТЬ С~$(X_{r+1},~\ldots,
X_{r+k})$ ДЛЯ~$0\le r < n$. в ТАКОМ СЛУЧАЕ КАЖДЫЙ ВОЗМОЖНЫЙ НАБОР
ИЗ $k$~ЧИСЕЛ БУДЕТ ВСТРЕЧАТЬСЯ В ПОСЛЕДОВАТЕЛЬНОСТИ САМОЕ БОЛЬШЕЕ ОДИН РАЗ.
в КОНЦЕ КОНЦОВ ПРОЦЕСС ОСТАНОВИТСЯ, КОГДА МЫ ДОСТИГНЕМ ТАКОГО
ЗНАЧЕНИЯ~$n$, ЧТО~$(X_{n+1},~\ldots, X_{n+k-1}, y)$ УЖЕ ВСТРЕЧАЛСЯ В
ПОСЛЕДОВАТЕЛЬНОСТИ ДЛЯ ВСЕХ~$y$, $0\le y < m$. нАПРИМЕР, ЕСЛИ~$m=k=3$,
ПОСЛЕДОВАТЕЛЬНОСТЬ ТАКОВА:
$$
00022212202112102012001110100
$$
И НА ЭТОМ ПРОЦЕСС ОСТАНАВЛИВАЕТСЯ. a)~дОКАЖИТЕ, ЧТО, КОГДА
ПОСЛЕДОВАТЕЛЬНОСТЬ ЗАКАНЧИВАЕТСЯ, МЫ ИМЕЕМ~$X_{n+1}=\ldots=X_{n+k-1}=0$.
b)~дОКАЖИТЕ, ЧТО \emph{КАЖДЫЙ} $k\hbox{-НАБОР}$ $(a_1, a_2,~\ldots, a_k)$
ЭЛЕМЕНТОВ~$a_j$, $0\le a_j<m$, ВСТРЕЧАЕТСЯ В ПОСЛЕДОВАТЕЛЬНОСТИ.
сЛЕДОВАТЕЛЬНО, ОНА ЗАКАНЧИВАЕТСЯ, КОГДА~$n=m^k$. [\emph{уКАЗАНИЕ.}
дОКАЖИТЕ ИНДУКЦИЕЙ ПО~$s$, ЧТО ПОЯВЛЯЕТСЯ~$(a_1,~\ldots, a_s, 0,~\ldots, 0)$
С~$a_s\ne0$.] зАМЕТИМ, ЧТО ЕСЛИ ТЕПЕРЬ
ОПРЕДЕЛИТЬ~$f(X_n,~\ldots, X_{n+k-1})=X_{n+k}$ ДЛЯ~$1 \le n \le m^k$,
ПОЛАГАЯ~$X_{m^k+k}=0$, ТО ПОЛУЧИМ ФУНКЦИЮ С МАКСИМАЛЬНО ВОЗМОЖНЫМ ПЕРИОДОМ.

\ex[м22] пУСТЬ~$Y_n$---ПОСЛЕДОВАТЕЛЬНОСТЬ БИТОВ, ПОЛУЧЕННАЯ
МЕТОДОМ~(10) ПРИ~$k=35$ И~$c=(00000000000000000000000000000000101)_2$.
пУСТЬ~$U_n$---ДВОИЧНАЯ ДРОБЬ~$(.Y_{nk}Y_{nk+1}\ldots{}Y_{nk+k-1})$. пОКАЖИТЕ,
ЧТО ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ НЕ УДОВЛЕТВОРЯЕТ ТЕСТУ~3.3.2D ПРИ~$d=8$.

\ex[M41] нАЙДИТЕ ДЛЯ КАЖДОГО ПРОСТОГО~$p$ ИЗ ПЕРВОГО СТОЛБЦА ТАБЛ.~1 В
П.~4.5.4 ПОДХОДЯЩИЕ (В СМЫСЛЕ, УКАЗАННОМ В ТЕКСТЕ) КОНСТАНТЫ~$a_1$, $a_2$,
ТАКИЕ,  ЧТО ДЛИНА ПЕРИОДА~(8) ПРИ~$k=2$ РАВНА~$p^2-1$.

\ex[м40] вЫЧИСЛИТЕ КОНСТАНТЫ~$c$, УДОБНЫЕ ДЛЯ ИСПОЛЬЗОВАНИЯ ИХ В
МЕТОДЕ~(10), ИМЕЮЩИЕ ПРИМЕРНО ОДИНАКОВОЕ ЧИСЛО НУЛЕЙ И ЕДИНИЦ,
ДЛЯ~$1\le k \le 64$.

\ex[м35] (д. рИС.) в ТЕКСТЕ ОБЎЯСНЯЕТСЯ, КАК НАХОДИТЬ ФУНКЦИИ~$f$, ТАКИЕ,
ЧТО У ПОСЛЕДОВАТЕЛЬНОСТИ~(11) ДЛИНА ПЕРИОДА РАВНА~$m^k-1$ ПРИ УСЛОВИИ,
ЧТО~$m$---ПРОСТОЕ ЧИСЛО, А~$X_0$,~\dots, $X_{k-1}$ ОТЛИЧНЫ ОТ НУЛЯ. пОКАЖИТЕ,
ЧТО ЭТИ ФУНКЦИИ МОЖНО МОДИФИЦИРОВАТЬ, ЧТОБЫ ПОЛУЧИТЬ ПОСЛЕДОВАТЕЛЬНОСТИ ВИДА~(11)
%% 51
С ДЛИНОЙ ПЕРИОДА~$m^k$ ДЛЯ \emph{ВСЕХ}~$m$. [\emph{уКАЗАНИЕ.}
вОСПОЛЬЗУЙТЕСЬ ЛЕММОЙ~3.2.1.2Q, ИСКУССТВЕННЫМ ПРИЕМОМ УПР.~7 И
ПОСЛЕДОВАТЕЛЬНОСТЯМИ ВИДА~$\<pX_{2n}+X_{2n+1}>$.]

\rex[м24] в ТЕКСТЕ ОБСУЖДЕНИЕ ОБОБЩЕННЫХ ЛИНЕЙНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ~(8) ОГРАНИЧИВАЕТСЯ СЛУЧАЕМ, КОГДА~$m$---ПРОСТОЕ ЧИСЛО.
дОКАЖИТЕ, ЧТО ДОСТАТОЧНО БОЛЬШИЕ ПЕРИОДЫ МОЖНО ПОЛУЧИТЬ, КОГДА~$m$
"СВОБОДНО ОТ КВАДРАТОВ", Т.~Е.\ ПРЕДСТАВЛЯЕТСЯ В ВИДЕ ПРОИЗВЕДЕНИЯ
РАЗЛИЧНЫХ ПРОСТЫХ ЧИСЕЛ. (пРОВЕРКА ТАБЛ.~3.2.1.1-1 ПОКАЗЫВАЕТ,
ЧТО~$m=w\pm1$ ЧАСТО УДОВЛЕТВОРЯЕТ ЭТОЙ ГИПОТЕЗЕ. мНОГИЕ РЕЗУЛЬТАТЫ,
ПОЛУЧЕННЫЕ В ТЕКСТЕ, МОЖНО ПОЭТОМУ ПРИМЕНЯТЬ И В ЭТОМ СЛУЧАЕ, НЕСКОЛЬКО
БОЛЕЕ УДОБНОМ ДЛЯ ВЫЧИСЛЕНИЙ.)

%% 52
\subchap{статистические тесты} % 3.3
нАША ОСНОВНАЯ ЗАДАЧА СОСТОИТ В ПОЛУЧЕНИИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, КОТОРЫЕ
ПОХОЖИ НА СЛУЧАЙНЫЕ. мЫ УЖЕ ВИДЕЛИ, КАК ДОБИТЬСЯ ТАКОГО БОЛЬШОГО ПЕРИОДА
ПОСЛЕДОВАТЕЛЬНОСТИ, ЧТОБЫ В ПРАКТИЧЕСКИХ ЗАДАЧАХ ИСКЛЮЧИТЬ ВОЗМОЖНОСТЬ ЕЕ
ПОВТОРЕНИЯ. хОТЯ ЭТО И ВАЖНО, НО БОЛЬШОЙ ПЕРИОД ЕЩЕ ВОВСЕ НЕ ОЗНАЧАЕТ, ЧТО
ПОСЛЕДОВАТЕЛЬНОСТЬ ХОРОША ДЛЯ РАБОТЫ. кАК ЖЕ РЕШАТЬ, ДОСТАТОЧНО ЛИ
СЛУЧАЙНА ПОСЛЕДОВАТЕЛЬНОСТЬ?

еСЛИ ДАТЬ ЛЮБОМУ ЧЕЛОВЕКУ КАРАНДАШ И БУМАГУ И ПОПРОСИТЬ ЕГО НАПИСАТЬ
100~СЛУЧАЙНЫХ ДЕСЯТИЧНЫХ ЦИФР, ОЧЕНЬ МАЛО ШАНСОВ НА ТО, ЧТО ОН
ДОСТАТОЧНО ХОРОШО СМОЖЕТ С ЭТИМ СПРАВИТЬСЯ. лЮДИ СТРЕМЯТСЯ ИЗБЕГАТЬ
КОМБИНАЦИЙ, КАЖУЩИХСЯ ИМ НЕСЛУЧАЙНЫМИ, ТАКИХ, КАК ПАРЫ ОДИНАКОВЫХ
СОСЕДНИХ ЦИФР (ХОТЯ ПРИМЕРНО КАЖДАЯ ИЗ 10~ЦИФР ДОЛЖНА СОВПАДАТЬ С
ПРЕДЫДУЩЕЙ). пОЭТОМУ, УВИДЕВ ТАБЛИЦУ ДЕЙСТВИТЕЛЬНО СЛУЧАЙНЫХ ЧИСЕЛ,
ЛЮБОЙ ЧЕЛОВЕК СКОРЕЕ ВСЕГО СКАЖЕТ, ЧТО ОНИ СОВСЕМ НЕ СЛУЧАЙНЫЕ, ЕГО ГЛАЗ
СРАЗУ ЖЕ ОТМЕТИТ НЕКОТОРЫЕ ВИДИМЫЕ ЗАКОНОМЕРНОСТИ.

кАК ЗАМЕТИЛ Д-Р~мАТРИЦА (ЦИТИРУЕТСЯ ПО РАБОТЕ м.~Gardner, {\sl Scientific
American,\/} ЯНВАРЬ, 1965), "МАТЕМАТИКИ РАССМАТРИВАЮТ ДЕСЯТИЧНОЕ
ПРЕДСТАВЛЕНИЕ ЧИСЛА~$\pi$ КАК СЛУЧАЙНЫЙ РЯД, ТОГДА КАК ДЛЯ СОВРЕМЕННОГО
ТОЛКОВАТЕЛЯ ЧИСЕЛ---ЭТО КЛАДЕЗЬ ЗАМЕЧАТЕЛЬНЫХ ЗАКОНОМЕРНОСТЕЙ". д-Р~мАТРИЦА
УКАЗАЛ, НАПРИМЕР, ЧТО ПЕРВОЕ ПОВТОРЯЮЩЕЕСЯ ДВУЗНАЧНОЕ ЧИСЛО В
РАЗЛОЖЕНИИ~$\pi$---ЭТО 26, А ВТОРОЕ ЕГО ПОЯВЛЕНИЕ ПРИХОДИТСЯ ТОЧНО
ПОСЕРЕДИНЕ ОДНОЙ ЛЮБОПЫТНОЙ КОНФИГУРАЦИИ:
\picture{(1) p. 52}
вЫПИСАВ ОКОЛО ДЮЖИНЫ ДРУГИХ СВОЙСТВ ЭТИХ ЦИФР, ОН ОБНАРУЖИЛ, ЧТО, БУДУЧИ
ПРАВИЛЬНО ИНТЕРПРЕТИРОВАНО, ЧИСЛО~$\pi$ ОТРАЖАЕТ ВСЮ ИСТОРИЮ ЧЕЛОВЕЧЕСТВА!

вСЕ МЫ ВЫДЕЛЯЕМ ОСОБЕННОСТИ ТЕЛЕФОННЫХ НОМЕРОВ, НОМЕРНЫХ ЗНАКОВ МАШИН И
Т.~Д., ЧТОБЫ ЛЕГЧЕ ИХ ЗАПОМНИТЬ. гЛАВНАЯ МЫСЛЬ ВСЕГО СКАЗАННОГО
ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО МЫ НЕ МОЖЕМ ДОВЕРЯТЬ СЕБЕ В ОЦЕНКЕ, СЛУЧАЙНА ИЛИ
НЕТ ДАННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЧИСЕЛ. нЕОБХОДИМО ИСПОЛЬЗОВАТЬ КАКИЕ-ТО
НЕПРЕДВЗЯТЫЕ МЕХАНИЧЕСКИЕ ТЕСТЫ.

%% 53

сТАТИСТИЧЕСКАЯ ТЕОРИЯ ДАЕТ НАМ НЕКОТОРЫЕ КОЛИЧЕСТВЕННЫЕ КРИТЕРИИ
СЛУЧАЙНОСТИ. вОЗМОЖНЫМ ЖЕ ТЕСТАМ БУКВАЛЬНО НЕТ КОНЦА. мЫ ОБСУДИМ ТОЛЬКО
ТЕ ИЗ НИХ, КОТОРЫЕ, БУДУЧИ НАИБОЛЕЕ ПОЛЕЗНЫМИ И ПОУЧИТЕЛЬНЫМИ,
ОДНОВРЕМЕННО ЛЕГКО РЕАЛИЗУЮТСЯ НА ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ.

еСЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ ВЕДЕТ СЕБЯ УДОВЛЕТВОРИТЕЛЬНО ОТНОСИТЕЛЬНО
ТЕСТОВ~$T_1$, $T_2$,~\dots{}, $T_n$, МЫ НЕ МОЖЕМ БЫТЬ \emph{УВЕРЕНЫ} В ТОМ,
 ЧТО ОНА ВЫДЕРЖИТ, И СЛЕДУЮЩЕЕ ИСПЫТАНИЕ~$T_{n+1}$. оДНАКО КАЖДЫЙ ТЕСТ
ДАЕТ НАМ ВСЕ БОЛЬШЕ И БОЛЬШЕ УВЕРЕННОСТИ В СЛУЧАЙНОСТИ ПОСЛЕДОВАТЕЛЬНОСТИ.
оБЫЧНО ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОВЕРЯЕТСЯ С ПОМОЩЬЮ ПОЛУДЮЖИНЫ РАЗНЫХ ТЕСТОВ.
еСЛИ ИХ РЕЗУЛЬТАТЫ ОКАЗЫВАЮТСЯ УДОВЛЕТВОРИТЕЛЬНЫМИ, МЫ СЧИТАЕМ ЕЕ
СЛУЧАЙНОЙ (ОНА СЧИТАЕТСЯ НЕВИНОВНОЙ ДО ТЕХ ПОР, ПОКА НЕ ДОКАЗАНА ЕЕ ВИНОВНОСТЬ).

кАЖДУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ, КОТОРАЯ БУДЕТ ИНТЕНСИВНО ИСПОЛЬЗОВАТЬСЯ,
СЛЕДУЕТ ТЩАТЕЛЬНО ПРОВЕРИТЬ. пОЭТОМУ В СЛЕДУЮЩИХ РАЗДЕЛАХ ОБЎЯСНЯЕТСЯ,
КАК ПРАВИЛЬНО ПРОВОДИТЬ ТАКУЮ ПРОВЕРКУ. рАЗЛИЧАЮТСЯ ДВА СОРТА ТЕСТОВ:
\dfn{ЭМПИРИЧЕСКИЕ ТЕСТЫ,} КОГДА МАШИНА МАНИПУЛИРУЕТ С ГРУППАМИ ЧИСЕЛ
ПОСЛЕДОВАТЕЛЬНОСТИ И ПРОИЗВОДИТ ОЦЕНКУ С ПОМОЩЬЮ ОПРЕДЕЛЕННЫХ
СТАТИСТИЧЕСКИХ КРИТЕРИЕВ, И \dfn{ТЕОРЕТИЧЕСКИЕ ТЕСТЫ,} КОГДА МЫ НАХОДИМ
НЕКОТОРЫЕ ХАРАКТЕРИСТИКИ ПОСЛЕДОВАТЕЛЬНОСТИ, ПОЛЬЗУЯСЬ МЕТОДАМИ
ТЕОРИИ ЧИСЕЛ, БАЗИРУЮЩИМИСЯ НА РЕКУРРЕНТНОМ СООТНОШЕНИИ, С
ПОМОЩЬЮ КОТОРОГО ВЫРАБАТЫВАЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. в КНИГЕ
д.~хАФФА [D.~Huff, How to Lie With Statistics, (Norton, 1954)]
ЧИТАТЕЛЬ МОЖЕТ НАЙТИ РЯД ДРУГИХ РЕКОМЕНДАЦИЙ.

\subsubchap{уНИВЕРСАЛЬНЫЕ ТЕСТЫ ДЛЯ АНАЛИЗА СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ} % 3.3.1
\section{A. кРИТЕРИЙ~$\chi^2$}. кРИТЕРИЙ~$\chi^2$ ("ХИ-КВАДРАТ"), ВЕРОЯТНО,
САМЫЙ РАСПРОСТРАНЕННЫЙ ИЗ ВСЕХ СТАТИСТИЧЕСКИХ КРИТЕРИЕВ. оН ИСПОЛЬЗУЕТСЯ
НЕ ТОЛЬКО САМ ПО СЕБЕ, НО И КАК СОСТАВНАЯ ЧАСТЬ МНОГИХ ДРУГИХ ТЕСТОВ.
пРЕЖДЕ ЧЕМ ПРИСТУПИТЬ К ОБЩЕМУ ОПИСАНИЮ КРИТЕРИЯ~$\chi^2$, РАССМОТРИМ
СНАЧАЛА В КАЧЕСТВЕ ПРИМЕРА, КАК МОЖНО БЫЛО БЫ ПРИМЕНИТЬ ЭТОТ КРИТЕРИЙ ДЛЯ
АНАЛИЗА ИГРЫ В КОСТИ. пУСТЬ КАЖДЫЙ РАЗ БРОСАЮТСЯ НЕЗАВИСИМО ДВЕ
"ПРАВИЛЬНЫЕ" КОСТИ, ПРИЧЕМ БРОСАНИЕ КАЖДОЙ ИЗ НИХ ПРИВОДИТ С РАВНОЙ
ВЕРОЯТНОСТЬЮ К ВЫПАДЕНИЮ ОДНОГО ИЗ ЧИСЕЛ~$1$, $2$, $3$, $4$, $5$ И~$6$.
вЕРОЯТНОСТИ ВЫПАДЕНИЯ ЛЮБОЙ СУММЫ s ПРИ ОДНОМ БРОСАНИИ ПРЕДСТАВЛЕНЫ В ТАБЛИЦЕ:
$$
\vcenter{\halign{
#\hfil\bskip&\hfil$#{}$&\hfil$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
сУММА      &   s=&2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\cr
вЕРОЯТНОСТЬ& p_s=&{1\over 36} & 1\over 18 & 1\over 12 & 1\over 9 & 5\over 36
                & 1\over 6 & 5 \over 36 & 1\over 9 & 1\over 12 & 1 \over 18
                & 1 \over 36 \cr
}}
\eqno(1)
$$(нАПРИМЕР, СУММА s=4 МОЖЕТ БЫТЬ ПОЛУЧЕНА ТРЕМЯ СПОСОБАМИ:
%% 54
$1+3$, $2+2$, $3+1$; ПРИ $36$~ВОЗМОЖНЫХ ИСХОДАХ ЭТО СОСТАВЛЯЕТ~$3/36=1/12=p_4$.)

еСЛИ БРОСАТЬ КОСТИ $n$~РАЗ, МОЖНО ОЖИДАТЬ, ЧТО СУММА~$s$ ПОЯВИТСЯ В
СРЕДНЕМ $np_s$~РАЗ. нАПРИМЕР, ПРИ 144~БРОСАНИЯХ ЗНАЧЕНИЕ~$4$ ДОЛЖНО
ПОЯВИТЬСЯ ОКОЛО 12~РАЗ. сЛЕДУЮЩАЯ ТАБЛИЦА ПОКАЗЫВАЕТ, КАКИЕ РЕЗУЛЬТАТЫ
БЫЛИ В \emph{ДЕЙСТВИТЕЛЬНОСТИ,} ПОЛУЧЕНЫ ПРИ 144~БРОСАНИЯХ.
$$
\vcenter{\halign{
#\hfil\bskip&\hfil$#{}$&\hfil$#$\bskip&&\bskip\hfil$#$\hfil\bskip\cr
сУММА  &
     s=& 2 & 3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 \cr
фАКТИЧЕСКОЕ ЧИСЛО ВЫПАДЕНИЙ&
   Y_s=& 2 & 4 & 10 & 12 & 22 & 29 & 21 & 15 & 14 &  9 &  6\cr
сРЕДНЕЕ ЧИСЛО ВЫПАДЕНИЙ &
  np_s=& 4 & 8 & 12 & 16 & 20 & 24 & 20 & 16 & 12 &  8 &  4 \cr
}}
\eqno(2)
$$
оТМЕТИМ, ЧТО ФАКТИЧЕСКОЕ ЧИСЛО ВЫПАДЕНИЙ ОТЛИЧАЕТСЯ ОТ СРЕДНЕГО ВО ВСЕХ
СЛУЧАЯХ. в ЭТОМ НЕТ НИЧЕГО УДИВИТЕЛЬНОГО. дЕЛО В ТОМ, ЧТО ВСЕГО ИМЕЕТСЯ
$36{144}$~ВОЗМОЖНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИСХОДОВ ДЛЯ 144~БРОСАНИЙ, И ВСЕ
ОНИ РАВНОВЕРОЯТНЫ. оДНА ИЗ ТАКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СОСТОИТ, НАПРИМЕР,
ТОЛЬКО ИЗ ДВОЕК ("ЗМЕИНЫЕ ГЛАЗА"), И КАЖДЫЙ, У КОГО "ЗМЕИНЫЕ ГЛАЗА"
ВЫПАДУТ ПОДРЯД 144~РАЗА, БУДЕТ УВЕРЕН, ЧТО КОСТИ ПОДДЕЛЬНЫЕ. мЕЖДУ ТЕМ ЭТА
ПОСЛЕДОВАТЕЛЬНОСТЬ ТАК ЖЕ ВЕРОЯТНА, КАК И ЛЮБАЯ ДРУГАЯ. кАКИМ ЖЕ ОБРАЗОМ
В ТАКОМ СЛУЧАЕ МЫ МОЖЕМ ПРОВЕРИТЬ, ПРАВИЛЬНО ЛИ ИЗГОТОВЛЕНА ДАННАЯ ПАРА
КОСТЕЙ? оТВЕТ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО СКАЗАТЬ ОПРЕДЕЛЕННО "ДА" ИЛИ "НЕТ"
МЫ НЕ МОЖЕМ, НО МОЖЕМ ДАТЬ \emph{ВЕРОЯТНОСТНЫЙ} ОТВЕТ, Т.~Е.~УКАЗАТЬ,
НАСКОЛЬКО ВЕРОЯТНО ИЛИ НЕВЕРОЯТНО ДАННОЕ СОБЫТИЕ.

еСТЕСТВЕННЫЙ ПУТЬ РЕШЕНИЯ НАШЕЙ ЗАДАЧИ СОСТОИТ В СЛЕДУЮЩЕМ. вЫЧИСЛИМ
(ПРИБЕГНУВ К ПОМОЩИ эвм) СУММУ КВАДРАТОВ РАЗНОСТЕЙ ФАКТИЧЕСКОГО ЧИСЛА
ВЫПАДЕНИЙ~$Y_s$ И СРЕДНЕГО ЧИСЛА ВЫПАДЕНИЙ~$np_s$ (СМ.~(2)):
$$
V=(Y_2-np_2)^2+(Y_3-np_3)^2+\cdots+(Y_{12}-np_{12})^2.
\eqno(3)
$$
дЛЯ ПЛОХОГО КОМПЛЕКТА КОСТЕЙ ДОЛЖНЫ ПОЛУЧАТЬСЯ ОТНОСИТЕЛЬНО ВЫСОКИЕ
ЗНАЧЕНИЯ~$V$. вОЗНИКАЕТ ВОПРОС, НАСКОЛЬКО ВЕРОЯТНЫ ТАКИЕ ВЫСОКИЕ ЗНАЧЕНИЯ?
еСЛИ ВЕРОЯТНОСТЬ ИХ ПОЯВЛЕНИЯ ОЧЕНЬ МАЛА, СКАЖЕМ РАВНА~$1/100$,---Т.~Е.\
ОТКЛОНЕНИЕ РЕЗУЛЬТАТА ОТ СРЕДНЕГО ЗНАЧЕНИЯ НА ТАКУЮ БОЛЬШУЮ ВЕЛИЧИНУ
ВОЗМОЖНО ТОЛЬКО В ОДНОМ СЛУЧАЕ ИЗ~$100$,---ТО У НАС ЕСТЬ ОПРЕДЕЛЕННЫЕ
ОСНОВАНИЯ ДЛЯ ПОДОЗРЕНИЙ. (нЕ СЛЕДУЕТ ЗАБЫВАТЬ, ОДНАКО, ЧТО ДАЖЕ
\emph{ХОРОШИЕ} КОСТИ БУДУТ ДАВАТЬ ТАКОЕ ВЫСОКОЕ ЗНАЧЕНИЕ~$V$ ОДИН РАЗ
ИЗ~100, ТАК ЧТО ДЛЯ БОЛЬШЕЙ УВЕРЕННОСТИ СЛЕДОВАЛО БЫ ПОВТОРИТЬ
ЭКСПЕРИМЕНТ И ПОСМОТРЕТЬ, ПОЛУЧИТСЯ ЛИ ПОВТОРНО ВЫСОКОЕ ЗНАЧЕНИЕ~$V$.)

в СТАТИСТИКУ~$V$ ВСЕ КВАДРАТЫ РАЗНОСТЕЙ ВХОДЯТ С РАВНЫМ ВЕСОМ,
ХОТЯ~$(Y_7-np_7)^2$, НАПРИМЕР, ВЕРОЯТНО, БУДЕТ НАМНОГО БОЛЬШЕ,
ЧЕМ~$(Y_2-np_2)^2$, ТАК КАК~$s=7$ ВСТРЕЧАЕТСЯ В ШЕСТЬ РАЗ ЧАЩЕ,
%% 55
ЧЕМ~$s=2$. оКАЗЫВАЕТСЯ, ЧТО В "ПРАВИЛЬНУЮ" СТАТИСТИКУ, ИЛИ ПО КРАЙНЕЙ МЕРЕ
ТАКУЮ, ДЛЯ КОТОРОЙ ДОКАЗАНО, ЧТО ОНА НАИБОЛЕЕ ЗНАЧИМА, ЧЛЕН~$(Y_7-np_7)^2$
ВХОДИТ С МНОЖИТЕЛЕМ, КОТОРЫЙ В ШЕСТЬ РАЗ МЕНЬШЕ МНОЖИТЕЛЯ
ПРИ~$(Y_2-np_2)^2$. тАКИМ ОБРАЗОМ, СЛЕДУЕТ ЗАМЕНИТЬ~(3) НА СЛЕДУЮЩУЮ ФОРМУЛУ:
$$
V={(Y_2-np_2)^2 \over np_2}+{(Y_3-np_3)^2\over np_3}+\cdots+{(Y_{12}-np_{12})^2\over np_{12}}.
\eqno(4)
$$
оПРЕДЕЛЕННУЮ ТАКИМ ОБРАЗОМ ВЕЛИЧИНУ~$V$ НАЗЫВАЮТ СТАТИСТИКОЙ~$\chi^2$,
СООТВЕТСТВУЮЩЕЙ ЗНАЧЕНИЯМ~$Y_2$,~\dots, $Y_{12}$, ПОЛУЧЕННЫМ В ЭКСПЕРИМЕНТЕ.
пОДСТАВЛЯЯ В ЭТУ ФОРМУЛУ ЗНАЧЕНИЯ ИЗ~(2), ПОЛУЧАЕМ
$$
V={(2-4)^2\over 4}+{(4-8)^2\over 8}+\cdots+{(9-8)^2\over 8}+{(6-4)^2\over4}=7{7\over 48}.
\eqno(5)
$$
тЕПЕРЬ, ЕСТЕСТВЕННО, ВОЗНИКАЕТ ВОПРОС, ЯВЛЯЕТСЯ ЛИ ЗНАЧЕНИЕ~$7{7\over48}$
НАСТОЛЬКО БОЛЬШИМ, ЧТО ЕГО СЛУЧАЙНОЕ ПОЯВЛЕНИЕ МОЖНО СЧИТАТЬ МАЛОВЕРОЯТНЫМ.
пРЕЖДЕ ЧЕМ ОТВЕЧАТЬ НА ЭТОТ ВОПРОС, СФОРМУЛИРУЕМ КРИТЕРИЙ~$\chi^2$ В
БОЛЕЕ ОБЩЕМ ВИДЕ.

пРЕДПОЛОЖИМ, ЧТО ВСЕ ВОЗМОЖНЫЕ РЕЗУЛЬТАТЫ ИСПЫТАНИЙ РАЗДЕЛЕНЫ НА
$k$~КАТЕГОРИЙ. пРОВОДИТСЯ  $n$~\dfn{НЕЗАВИСИМЫХ ИСПЫТАНИЙ;}
ЭТО ОЗНАЧАЕТ, ЧТО ИСХОД КАЖДОГО ИСПЫТАНИЯ АБСОЛЮТНО НЕ ВЛИЯЕТ НА ИСХОД
ОСТАЛЬНЫХ. пУСТЬ~$p_s$---ВЕРОЯТНОСТЬ ТОГО, ЧТО РЕЗУЛЬТАТ ИСПЫТАНИЯ ПОПАДЕТ В
КАТЕГОРИЮ~$s$, И ПУСТЬ~$Y_s$---ЧИСЛО ИСПЫТАНИЙ, КОТОРЫЕ ДЕЙСТВИТЕЛЬНО
\emph{ПОПАЛИ} В КАТЕГОРИЮ~$s$. сФОРМИРУЕМ СТАТИСТИКУ
$$
V=\sum_{1\le s\le k} {(Y_s-np_s)^2\over np_s}.
\eqno(6)
$$

в ПРЕДЫДУЩЕМ ПРИМЕРЕ ИМЕЛОСЬ $11$~ВОЗМОЖНЫХ ИСХОДОВ ПРИ КАЖДОМ БРОСАНИИ
КОСТЕЙ, ТАК ЧТО~$k=11$. [фОРМУЛЫ~(4) И~(6) РАЗЛИЧАЮТСЯ ТОЛЬКО
НУМЕРАЦИЕЙ: В ОДНОМ СЛУЧАЕ ОНА ПРОИЗВОДИТСЯ ОТ~2 ДО~12, А В ДРУГОМ---ОТ~$1$ ДО~$k$.]

иСПОЛЬЗУЯ ТОЖДЕСТВО~$(Y_s-np_s)^2=Y_s^2-2np_sY_s+n^2p_s^2$ И РАВЕНСТВА
$$
\eqalign{
Y_1+Y_2+\cdots+Y_k&=n,\cr
p_1+p_2+\cdots+p_k&=1,\cr
}
\eqno(7)
$$
МОЖНО ПРЕОБРАЗОВАТЬ ФОРМУЛУ~(6) К ВИДУ
$$
V={1\over n}\sum_{1\le s \le k} \left({Y_s^2\over p_s}\right)-n,
\eqno(8)
$$
ПРИЧЕМ В БОЛЬШИНСТВЕ СЛУЧАЕВ ТАКАЯ ЗАПИСЬ ОБЛЕГЧАЕТ ВЫЧИСЛЕНИЯ.

вЕРНЕМСЯ К ВОПРОСУ О ТОМ, КАКИЕ ЗНАЧЕНИЯ~$V$ МОЖНО СЧИТАТЬ РАЗУМНЫМИ.
оТВЕТ НА ЭТО ДАЕТ ТАБЛ.~1, В КОТОРОЙ ПРИВЕДЕНО "РАСПРЕДЕЛЕНИЕ~$\chi^2$ С
$\nu$~СТЕПЕНЯМИ СВОБОДЫ" ПРИ РАЗНЫХ ЗНАЧЕНИЯХ~$\nu$. сЛЕДУЕТ ПОЛЬЗОВАТЬСЯ
СТРОКОЙ ТАБЛИЦЫ С~$\nu=k-1$; \emph{ЧИСЛО "СТЕПЕНЕЙ СВОБОДЫ" РАВНО~$k-1$,
Т.~Е.\ НА ЕДИНИЦУ МЕНЬШЕ ЧИСЛА КАТЕГОРИЙ.}
%% 56
{\everycr={\noalign{\hrule}}
\htable{тАБЛИЦА~1}%
{нЕКОТОРЫЕ ДАННЫЕ ДЛЯ РАСПРЕДЕЛЕНИЯ~$\chi^2$}%
{\offinterlineskip
\strut\vrule\bskip$#$\bskip\hfil\vrule&&\bskip\hfil$#$\bskip\hfil\vrule\cr
\noalign{
\embedpar{
\noindent
(бОЛЕЕ ПОЛНЫЕ ТАБЛИЦЫ СМ. В Handbook of Mathematical Functions, ed.\
 by M.~Abramowitz and I.~A.~Stegun, U.~S. Government Printing Office, 1964,
Table~26.8)
}
}
       & p=99\%  & p=95\%  & p=75\% & p=50\% & p=25\%& p=5\% & p=1\% \cr
\nu=1  & 0.00016 & 0.00393 & 0.1015 & 0.4549 & 1.323 & 3.841 & 6.635\cr
\nu=2  & 0.00201 & 0.1026  & 0.5753 & 1.386  & 2.773 & 5.991 & 9.210\cr
\nu=3  & 0.1148  & 0.3518  & 1.213  & 2.366  & 4.108 & 7.815 & 11,34\cr
\nu=4  & 0.2971  & 0.7107  & 1.923  & 3.357  & 5.385 & 9.488 & 13.28\cr
\nu=5  & 0.5543  & 1.1455  & 2.675  & 4.351  & 6.626 & 11.07 & 15.09\cr
\nu=6  & 0.8720  & 1.635   & 3.455  & 5.348  & 7.841 & 12.59 & 16.81\cr
\nu=7  & 1.239   & 2.167   & 4.255  & 6.346  & 9.037 & 14.07 & 18.48\cr
\nu=8  & 1.646   & 2.733   & 5.071  & 7.344  & 10.22 & 15.51 & 20.09\cr
\nu=9  & 2.088   & 3.325   & 5.899  & 8.343  & 11.39 & 16.92 & 21.67\cr
\nu=10 & 2.558   & 3.940   & 6.737  & 9.342  & 12.55 & 18.31 & 23.21\cr
\nu=11 & 3.053   & 4.575   & 7.584  & 10.34  & 13.70 & 19.68 & 24.73\cr
\nu=12 & 3.571   & 5.226   & 8.438  & 11.34  & 14.84 & 21.03 & 26.22\cr
\nu=15 & 5.229   & 7.261   & 11.04  & 14.34  & 18.25 & 25.00 & 30.58\cr
\nu=20 & 8.260   & 10.85   & 15.45  & 19.34  & 23.83 & 31.41 & 37.57\cr
\nu=30 & 14.95   & 18.49   & 24.48  & 29.34  & 34.80 & 43.77 & 50.89\cr
\nu=50 & 29.71   & 34.76   & 42.94  & 49.33  & 56.33 & 67.50 & 76.15\cr
\nu>30 & \multispan{7} \hfil\emph{ПРИБЛИЗИТЕЛЬНО~$\nu+2\sqrt{\nu}x_p+{4\over3}x^2_p-{2\over3}$\hfil}\vrule\cr
x_p=   & -2.33   & -1.64   & -.675  & 0.00   & 0.675 & 1.64  & 2.33\cr
}}
(нА ИНТУИТИВНОМ УРОВНЕ ЭТО МОЖНО ПОЯСНИТЬ СЛЕДУЮЩИМ ОБРАЗОМ:
ЗНАЧЕНИЯ~$Y_1$, $Y_2$,~\dots, $Y_k$ НЕ СОВСЕМ НЕЗАВИСИМЫ, ТАК КАК~$Y_1$,
СОГЛАСНО~(7), МОЖНО ВЫЧИСЛИТЬ, ЗНАЯ~$Y_2$,~\dots, $Y_k$. сЛЕДОВАТЕЛЬНО,
ИМЕЕТСЯ $k-1$~СТЕПЕНЕЙ СВОБОДЫ. бОЛЕЕ СТРОГАЯ АРГУМЕНТАЦИЯ БУДЕТ
ПРИВЕДЕНА НИЖЕ.)

еСЛИ В ТАБЛИЦЕ В СТРОКЕ~$\nu$ И КОЛОНКЕ~$p$ НАХОДИТСЯ ЧИСЛО~$x$, ТО ЭТО
ОЗНАЧАЕТ, ЧТО ЗНАЧЕНИЕ~$V$, ОПРЕДЕЛЯЕМОЕ ПО ФОРМУЛЕ~(8), БУДЕТ БОЛЬШЕ~$x$
С ВЕРОЯТНОСТЬЮ~$p$. нАПРИМЕР, ДЛЯ~$p=5$\% И~$\nu=10$ ТАБЛИЦА ДАЕТ
ЗНАЧЕНИЕ~$x=18.31$; ЭТО ОЗНАЧАЕТ, ЧТО~$V>18.31$ ТОЛЬКО В~$5$\% ВСЕХ СЛУЧАЕВ.

пРЕДПОЛОЖИМ, ЧТО ОПИСАННЫЙ ПРОЦЕСС БРОСАНИЯ КОСТЕЙ МОДЕЛИРУЕТСЯ НА эвм С
ПОМОЩЬЮ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ, КОТОРЫЕ
%% 57
ПРЕДПОЛАГАЮТСЯ СЛУЧАЙНЫМИ, И ЧТО ПОЛУЧЕНЫ СЛЕДУЮЩИЕ РЕЗУЛЬТАТЫ:
$$
\vcenter{
\halign{#\bskip\hfil&\bskip\hfil$#{}$&$#$\bskip\hfil&&\bskip\hfil$#$\bskip\cr
              &   s=& 2 &  3&  4&  5&  6&  7&  8&  9& 10& 11& 12\cr
эКСПЕРИМЕНТ~1 & Y_s=& 4 & 10& 10& 13& 20& 18& 18& 11& 13& 14& 13\cr
эКСПЕРИМЕНТ~2 & Y_s=& 3 &  7& 11& 15& 19& 24& 21& 17& 13&  9&  5\cr
}
}
\eqno(9)
$$
вЫЧИСЛЯЯ СТАТИСТИКУ КРИТЕРИЯ~$\chi^2$, ПОЛУЧАЕМ В ПЕРВОМ
СЛУЧАЕ $V_1=29{59\over 120}$, А ВО ВТОРОМ СЛУЧАЕ~$V_2=1{17\over 120}$.
тАБЛИЧНЫЕ ЗНАЧЕНИЯ, СООТВЕТСТВУЮЩИЕ $10$~СТЕПЕНЯМ СВОБОДЫ, ПОКАЗЫВАЮТ,
ЧТО~$V_1$ \emph{ЯВНО СЛИШКОМ, ВЕЛИКО;} $V$~БЫВАЕТ БОЛЬШЕ, ЧЕМ~$23.2$,
ТОЛЬКО В ОДНОМ ПРОЦЕНТЕ СЛУЧАЕВ! (бОЛЕЕ ПОЛНЫЕ ТАБЛИЦЫ ПОКАЗЫВАЮТ, ЧТО
ВЕРОЯТНОСТЬ ПОЯВЛЕНИЯ СТОЛЬ БОЛЬШОГО ЗНАЧЕНИЯ~$V$ РАВНА~$0.1$\%.)
тАКИМ ОБРАЗОМ, В ЭКСПЕРИМЕНТЕ~1 ЗАРЕГИСТРИРОВАНО ЗНАЧИТЕЛЬНОЕ ОТКЛОНЕНИЕ
ОТ НОРМЫ.

с ДРУГОЙ СТОРОНЫ, $V_2$ ОЧЕНЬ МАЛО, ПОТОМУ ЧТО~$Y_s$ В ЭКСПЕРИМЕНТЕ~2
ОКАЗАЛИСЬ ОЧЕНЬ БЛИЗКИ К СРЕДНИМ ЗНАЧЕНИЯМ~$np_s$ [СР.~С~(2)]. иЗ ТАБЛИЦЫ
РАСПРЕДЕЛЕНИЯ~$\chi^2$ СЛЕДУЕТ, ЧТО В~$99$\% СЛУЧАЕВ $V$~ДОЛЖНО БЫТЬ
БОЛЬШЕ, ЧЕМ~$2.56$. зНАЧЕНИЕ~$V_2$ \emph{ЯВНО СЛИШКОМ МАЛО;} ПОЛУЧЕННЫЕ В
ЭКСПЕРИМЕНТЕ ЗНАЧЕНИЯ~$V_3$
%% ?? V_s
НАСТОЛЬКО БЛИЗКИ К СРЕДНЕМ ЗНАЧЕНИЯМ, ЧТО НЕВОЗМОЖНО СЧИТАТЬ ЭТОТ
ЭКСПЕРИМЕНТ СЛУЧАЙНЫМ ИСПЫТАНИЕМ. (в САМОМ ДЕЛЕ, ИЗ БОЛЕЕ ПОЛНЫХ
ТАБЛИЦ СЛЕДУЕТ, ЧТО ПРИ $10$~СТЕПЕНЯХ СВОБОДЫ ТАКИЕ НИЗКИЕ
ЗНАЧЕНИЯ~$V$ ВСТРЕЧАЮТСЯ ТОЛЬКО В $0.03$\%~СЛУЧАЕВ). нАКОНЕЦ, С ПОМОЩЬЮ
ТАБЛИЦЫ РАСПРЕДЕЛЕНИЯ~$\chi^2$ МОЖНО ПРОВЕРИТЬ ПОЛУЧЕННОЕ НАМИ В~(5)
ЗНАЧЕНИЕ~$V=7{7\over 48}$. оНО ПОПАДАЕТ В ИНТЕРВАЛ МЕЖДУ~$75$ И~$50$\%,
ТАК ЧТО МЫ НЕ МОЖЕМ СЧИТАТЬ ЕГО СЛИШКОМ ВЫСОКИМ ИЛИ СЛИШКОМ НИЗКИМ; ДАННЫЕ,
ПРЕДСТАВЛЕННЫЕ В~(2), УДОВЛЕТВОРЯЮТ КРИТЕРИЮ~$\chi^2$.

бОЛЬШИМ ПРЕИМУЩЕСТВОМ РАССМАТРИВАЕМОГО МЕТОДА ЯВЛЯЕТСЯ ТО, ЧТО ОДНИ И ТЕ
ЖЕ ТАБЛИЧНЫЕ ЗНАЧЕНИЯ ИСПОЛЬЗУЮТСЯ ПРИ ЛЮБЫХ~$n$ И ЛЮБЫХ
ВЕРОЯТНОСТЯХ~$p_s$. еДИНСТВЕННОЙ ПЕРЕМЕННОЙ ЯВЛЯЕТСЯ~$\nu=k-1$. нА САМОМ
ДЕЛЕ ПРИВЕДЕННЫЕ В ТАБЛИЦЕ ЗНАЧЕНИЕ НЕ ЯВЛЯЮТСЯ АБСОЛЮТНО ТОЧНЫМИ ВО ВСЕХ
СЛУЧАЯХ: \emph{ЭТО ПРИБЛИЖЕННЫЕ ЗНАЧЕНИЯ, СПРАВЕДЛИВЫЕ ЛИШЬ ПРИ ДОСТАТОЧНО
БОЛЬШИХ ЗНАЧЕНИЯХ~$n$.} кАК ВЕЛИКО ДОЛЖНО БЫТЬ~$n$? дОСТАТОЧНО
БОЛЬШИМИ МОЖНО СЧИТАТЬ ТАКИЕ ЗНАЧЕНИЯ~$n$, ПРИ КОТОРЫХ ЛЮБОЕ ИЗ~$np_s$
НЕ МЕНЬШЕ~$5$; ОДНАКО ЛУЧШЕ БРАТЬ~$n$ ЗНАЧИТЕЛЬНО БОЛЬШИМИ, ЧТОБЫ ПОВЫСИТЬ
НАДЕЖНОСТЬ КРИТЕРИЯ. зАМЕТИМ, ЧТО В РАССМОТРЕННЫХ ПРИМЕРАХ МЫ
БРАЛИ~$n=144$, И $np_2$~РАВНЯЛОСЬ ВСЕГО~$4$, ЧТО ПРОТИВОРЕЧИТ ТОЛЬКО ЧТО
СФОРМУЛИРОВАННОМУ ПРАВИЛУ. еДИНСТВЕННАЯ ПРИЧИНА ЭТОГО НАРУШЕНИЯ КРОЕТСЯ
В ТОМ, ЧТО АВТОРУ НАДОЕЛО БРОСАТЬ КОСТИ; В РЕЗУЛЬТАТЕ ЧИСЛА ИЗ ТАБЛИЦЫ
ОКАЗАЛИСЬ НЕ ОЧЕНЬ ПОДХОДЯЩИМИ ДЛЯ НАШЕГО СЛУЧАЯ. бЫЛО БЫ ГОРАЗДА ЛУЧШЕ
ПРОВЕСТИ ЭТИ ЭКСПЕРИМЕНТЫ НА МАШИНЕ ПРИ~$n=1000$ ИЛИ~$10\,000$,
ИЛИ ДАЖЕ~$100\,000$.

%% 58

нА САМОМ ДЕЛЕ ВОПРОС О ВЫБОРЕ~$n$ НЕ ТАК ПРОСТ. еСЛИ БЫ КОСТИ БЫЛИ
ДЕЙСТВИТЕЛЬНО НЕПРАВИЛЬНЫЕ, ЭТО ПРОЯВЛЯЛОСЬ БЫ ПРИ СКОЛЬ УГОДНО
БОЛЬШИХ~$n$ (СМ.~УПР.~12). нО ПРИ БОЛЬШИХ ЗНАЧЕНИЯХ~$n$ МОГУТ СГЛАЖИВАТЬСЯ
\emph{ЛОКАЛЬНЫЕ} ОТКЛОНЕНИЯ, ТАКИЕ, КАК СЛЕДУЮЩИЕ ДРУГ ЗА ДРУГОМ БЛОКИ
ЧИСЕЛ С СИЛЬНЫМ СИСТЕМАТИЧЕСКИМ СМЕЩЕНИЕМ В ПРОТИВОПОЛОЖНЫЕ СТОРОНЫ. пРИ
ДЕЙСТВИТЕЛЬНОМ БРОСАНИИ КОСТЕЙ ЭТОГО МОЖНО НЕ ОПАСАТЬСЯ, ТАК КАК
ВСЕ ВРЕМЯ ИСПОЛЬЗУЮТСЯ ОДНИ И ТЕ ЖЕ КОСТИ, НО ЕСЛИ РЕЧЬ ИДЕТ
О ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ, ПОЛУЧЕННЫХ НА эвм, ТО ТАКОЙ ТИП ОТКЛОНЕНИЯ ОТ
СЛУЧАЙНОГО ПОВЕДЕНИЯ ВПОЛНЕ ВОЗМОЖЕН. в СВЯЗИ
\picture{
 рИС.~2. рЕЗУЛЬТАТЫ 90~ПРОВЕРОК С ИСПОЛЬЗОВАНИЕМ КРИТЕРИЯ~$\chi^2$ (СР. С~РИС.~5).
}
С ЭТИМ ЖЕЛАТЕЛЬНО ПРОВОДИТЬ ПРОВЕРКУ С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ ПРИ
РАЗНЫХ ЗНАЧЕНИЯХ~$n$, НО В ЛЮБОМ СЛУЧАЕ ЭТИ ЗНАЧЕНИЯ ДОЛЖНЫ БЫТЬ
ДОВОЛЬНО БОЛЬШИМИ.

иТАК, ПРОВЕРКА С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ ЗАКЛЮЧАЕТСЯ В СЛЕДУЮЩЕМ.
пРОВОДИТСЯ $n$~НЕЗАВИСИМЫХ ИСПЫТАНИЙ, ГДЕ~$n$---ДОСТАТОЧНО БОЛЬШОЕ ЧИСЛО.
(сЛЕДУЕТ ИЗБЕГАТЬ ПРИМЕНЕНИЯ КРИТЕРИЯ~$\chi^2$ В СЛУЧАЯХ, ЕСЛИ ИСПЫТАНИЯ
НЕ НЕЗАВИСИМЫ; СМ., НАПРИМЕР, УПР.~10, ГДЕ РАССМОТРЕН СЛУЧАЙ, КОГДА ОДНА
ПОЛОВИНА СОБЫТИЙ ЗАВИСИТ ОТ ДРУГОЙ.) пОДСЧИТЫВАЕТСЯ ЧИСЛО ИСПЫТАНИЙ,
РЕЗУЛЬТАТ КОТОРЫХ ОТНОСИТСЯ К КАЖДОЙ ИЗ $k$~КАТЕГОРИЙ, И ПО ФОРМУЛАМ~(6)
ИЛИ~(8) ВЫЧИСЛЯЕТСЯ ЗНАЧЕНИЕ~$V$. зАТЕМ~$V$ СРАВНИВАЕТСЯ С ЧИСЛАМИ
ИЗ ТАБЛ.~1 ПРИ~$\nu=k-1$. еСЛИ $V$~МЕНЬШЕ ЗНАЧЕНИЯ,
СООТВЕТСТВУЮЩЕГО~$p=99\%$, ИЛИ БОЛЬШЕ ЗНАЧЕНИЯ, СООТВЕТСТВУЮЩЕГО~$p=1\%$,
ТО РЕЗУЛЬТАТЫ БРАКУЮТСЯ КАК НЕДОСТАТОЧНО СЛУЧАЙНЫЕ. еСЛИ~$p$
%% 59
ЛЕЖИТ МЕЖДУ~99 И~95\% ИЛИ МЕЖДУ~5 И~1\%, ТО РЕЗУЛЬТАТЫ СЧИТАЮТСЯ
"ПОДОЗРИТЕЛЬНЫМИ"; ПРИ ЗНАЧЕНИЯХ~$p$, ПОЛУЧЕННЫХ ИНТЕРПОЛЯЦИЕЙ ПО
ТАБЛИЦЕ, ЗАКЛЮЧЕННЫХ МЕЖДУ~$95$ И~$90$\% ИЛИ~$10$ И~$5$\%, РЕЗУЛЬТАТЫ
"СЛЕГКА ПОДОЗРИТЕЛЬНЫ". чАСТО С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ ПРОВЕРЯЮТ ПО
КРАЙНЕЙ МЕРЕ ТРИ РАЗА РАЗНЫЕ ЧАСТИ ИССЛЕДУЕМОГО РЯДА ЧИСЕЛ, И, ЕСЛИ НЕ
МЕНЕЕ ДВУХ РАЗ ИЗ ТРЕХ РЕЗУЛЬТАТЫ ОКАЗЫВАЮТСЯ ПОДОЗРИТЕЛЬНЫМИ, ЧИСЛА
ОТБРАСЫВАЮТСЯ КАК НЕДОСТАТОЧНО СЛУЧАЙНЫЕ.

рАССМОТРИМ В КАЧЕСТВЕ ПРИМЕРА РИС.~2, ГДЕ СХЕМАТИЧЕСКИ ПРЕДСТАВЛЕНЫ
РЕЗУЛЬТАТЫ ПРОВЕРКИ С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ ШЕСТИ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
СЛУЧАЙНЫХ ЧИСЕЛ. дЛЯ КАЖДОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДЕЛАЛОСЬ ПЯТЬ РАЗНЫХ
ПРОВЕРОК (ОСНОВАННЫХ НА КРИТЕРИИ~$\chi^2$), КАЖДАЯ ИЗ КОТОРЫХ
ПОВТОРЯЛАСЬ НА ТРЕХ РАЗНЫХ УЧАСТКАХ ПОСЛЕДОВАТЕЛЬНОСТИ. в ДАТЧИКЕ~A
ИСПОЛЬЗОВАН МЕТОД мАКЛАРЕНА-мАРСАЛЬИ (АЛГОРИТМ~3.2.2м), В ДАТЧИКЕ~E---МЕТОД
фИБОНАЧЧИ, ОСТАЛЬНЫЕ ДАТЧИКИ СООТВЕТСТВУЮТ ЛИНЕЙНЫМ
КОНГРУЭНТНЫМ ПОСЛЕДОВАТЕЛЬНОСТЯМ СО СЛЕДУЮЩИМИ ПАРАМЕТРАМИ:
\ctable{#\hfil\bskip&\bskip # \hfil\cr
дАТЧИК~в:& $X_0=0$, $a=3141592653$, $c=2718281829$, $m=2^{35}$.\cr
дАТЧИК~C:& $X_0=0$, $a=2^7+1$, $c=1$, $m=2^{35}$.\cr
дАТЧИК~D:& $X_0=47594118$, $a=23$, $c=0$,  $m=10^8+1$.\cr
дАТЧИК~F:& $X_0=314159265$, $a=2^{18}+1$, $c=1$, $m=2^{35}$.\cr
}
рЕЗУЛЬТАТЫ, ПРИВЕДЕННЫЕ НА РИС.~2, ПОЗВОЛЯЮТ СДЕЛАТЬ СЛЕДУЮЩИЕ ВЫВОДЫ.
дАТЧИКИ~A, B, D ПРОШЛИ ИСПЫТАНИЯ УДОВЛЕТВОРИТЕЛЬНО, ДАТЧИК~C НАХОДИТСЯ
НА ГРАНИ И ДОЛЖЕН БЫТЬ, ПО-ВИДИМОМУ, ЗАБРАКОВАН, А ДАТЧИКИ~E И~F
ОПРЕДЕЛЕННО НЕ ПРОШЛИ ИСПЫТАНИЙ. дАТЧИК~F, БЕЗУСЛОВНО, МАЛОМОЩЕН;
ДАТЧИКИ~C И~D ОБСУЖДАЛИСЬ В ЛИТЕРАТУРЕ, НО У НИХ СЛИШКОМ МАЛО
ЗНАЧЕНИЕ~$a$. в ДАТЧИКЕ~D РЕАЛИЗОВАН МЕТОД ВЫЧЕТОВ В ТОМ ВИДЕ, В КАКОМ
ОН БЫЛ ВПЕРВЫЕ ПРЕДЛОЖЕН лЕМЕРОМ В~1948~Г., А В ДАТЧИКЕ~C---ЛИНЕЙНЫЙ
КОНГРУЭНТНЫЙ МЕТОД С~$c\ne 0$ ТАКЖЕ В ЕГО ПЕРВОНАЧАЛЬНОМ ВИДЕ (рОТЕНБЕРГ, 1960).

нЕСКОЛЬКО ДРУГОЙ ПОДХОД К СУЖДЕНИЮ О РЕЗУЛЬТАТАХ ПРОВЕРКИ ПО
КРИТЕРИЮ~$\chi^2$, БЕЗ ИСПОЛЬЗОВАНИЯ ТАКИХ ПОНЯТИЙ, КАК "ПОДОЗРИТЕЛЬНЫЙ",
"СЛЕГКА ПОДОЗРИТЕЛЬНЫЙ" И~Т.~Д., И МЕНЕЕ ПОЗВОЛЯЮЩИЙ ПОЛАГАТЬСЯ НА
МНЕНИЕ ad hoc, ОПИСЫВАЕТСЯ НИЖЕ В ЭТОМ РАЗДЕЛЕ.

\section{B. кРИТЕРИЙ кОЛМОГОРОВА-сМИРНОВА (кс-КРИТЕРИЙ)}. кАК МЫ
ВИДЕЛИ, КРИТЕРИЙ~$\chi^2$ ПРИМЕНЯЕТСЯ В ТЕХ СЛУЧАЯХ, КОГДА РЕЗУЛЬТАТЫ
ИСПЫТАНИЙ РАСПАДАЮТСЯ НА КОНЕЧНОЕ ЧИСЛО $k$~КАТЕГОРИЙ. оДНАКО НЕРЕДКО
СЛУЧАЙНЫЕ ВЕЛИЧИНЫ МОГУТ ПРИНИМАТЬ БЕСКОНЕЧНО МНОГО ЗНАЧЕНИЙ. в ЧАСТНОСТИ,
БЕСКОНЕЧНО МНОГО ЗНАЧЕНИЙ ПРИНИМАЮТ ВЕЩЕСТВЕННЫЕ СЛУЧАЙНЫЕ ЧИСЛА В
ИНТЕРВАЛЕ МЕЖДУ~$0$ И~$1$. хОТЯ МНОЖЕСТВО ЗНАЧЕНИЙ СЛУЧАЙНЫХ ЧИСЕЛ,
ПОЛУЧЕННЫХ В
%%60
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ, НЕИЗБЕЖНО ОГРАНИЧЕНО, ХОТЕЛОСЬ БЫ, ЧТОБЫ ЭТО НИКАК НЕ
СКАЗЫВАЛОСЬ НА РЕЗУЛЬТАТАХ РАСЧЕТОВ.

в ТЕОРИИ ВЕРОЯТНОСТЕЙ И СТАТИСТИКЕ ПРИНЯТО ИСПОЛЬЗОВАТЬ ОДНИ И ТЕ ЖЕ
ОБОЗНАЧЕНИЯ ПРИ ОПИСАНИИ ДИСКРЕТНЫХ И НЕПРЕРЫВНЫХ РАСПРЕДЕЛЕНИЙ. пУСТЬ
ТРЕБУЕТСЯ ОПИСАТЬ РАСПРЕДЕЛЕНИЕ ЗНАЧЕНИЙ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$. эТО
ДЕЛАЕТСЯ С ПОМОЩЬЮ \dfn{ФУНКЦИИ РАСПРЕДЕЛЕНИЯ~$F(x)$,} ГДЕ
$$
F (x) = \hbox{ВЕРОЯТНОСТЬ ТОГО, ЧТО~$(X\le x)$.}
$$
нА РИС.~3 ПРЕДСТАВЛЕНЫ ТРИ ПРИМЕРА. пЕРВЫЙ ИЗ НИХ---ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ
\emph{СЛУЧАЙНОГО БИТА,} Т.~Е.\ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$,
\picture{рИС.~3. пРИМЕРЫ ФУНКЦИЙ РАСПРЕДЕЛЕНИЯ.}
ПРИНИМАЮЩЕЙ ЗНАЧЕНИЯ~$0$ ИЛИ~$1$, КАЖДОЕ С ВЕРОЯТНОСТЬЮ~$1/2$. нА РИС.~3,~b
ПОКАЗАНА ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ \emph{ВЕЩЕСТВЕННОЙ СЛУЧАЙНОЙ ВЕЛИЧИНЫ,
РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ} МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ, ТАК ЧТО ВЕРОЯТНОСТЬ
ТОГО, ЧТО~$X\le x$, ПРОСТО РАВНА~$x$, ЕСЛИ~$0\le x \le 1$. нАПРИМЕР,
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$X\le{2\over3}$, РАВНА~$2\over3$.
нА РИС.~3,~c ПОКАЗАНО ПРЕДЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ ЗНАЧЕНИЙ~$V$
В КРИТЕРИИ~$\chi^2$ (ПРИ 10~СТЕПЕНЯХ СВОБОДЫ); ЭТО ЖЕ РАСПРЕДЕЛЕНИЕ, НО В
ДРУГОЙ ФОРМЕ, БЫЛО УЖЕ ПРЕДСТАВЛЕНО В ТАБЛ.~1. зАМЕТИМ, ЧТО~$F(x)$ ВСЕГДА
ВОЗРАСТАЕТ ОТ~$0$ ДО~$1$ ПРИ УВЕЛИЧЕНИИ~$x$ ОТ~$-\infty$ ДО~$+\infty$.

иСПОЛЬЗУЯ ЗНАЧЕНИЯ~$X_1$, $X_2$,~\dots, $X_n$ СЛУЧАЙНОЙ ВЕЛИЧИНЫ~$X$,
ПОЛУЧЕННЫЕ В РЕЗУЛЬТАТЕ НЕЗАВИСИМЫХ ИСПЫТАНИЙ, МОЖНО ПОСТРО-
%% 61
\bye