\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