Предисловие

Эта книга в первую очередь — книга по теории чисел, по науке, которую древние называли «царицей математики». И действительно, вряд ли в какой-нибудь другой части математики встретится такое количество столь простых и изящных по формулировке, и столь трудных для решения задач, настолько оторванных от практических надобностей человека. Мало какая область математики может похвастаться столь древней и славной историей. Сегодняшняя же теория чисел, называемая зачастую математиками попросту «арифметикой», вдобавок, еще и очень сложна по своим методам, почерпнутым из почти всех прочих математических наук.

Предыдущий абзац относится ко всем без исключения книгам по теории чисел. В чем же особенность книги, предлагаемой сейчас читателю? Пожалуй, в том, что ни что из сказанного выше для нее неверно. Во-первых, во второй половине двадцатого века у теории чисел неожиданно появились приложения к вещам вполне практическим. Сегодня компьютер, телефон, кредитная карточка и многие другие устройства используют довольно тонкие результаты этой науки. Как пели

по радио в моем детстве: «Чтоб водить корабли или летчиком стать, надо прежде всего арифметику знать». Яркий пример подобного приложения — криптосистема с открытым ключей, подробно разбираемая в этой книге. Идея такой криптосистемы проста чрезвычайно: перемножить два больших целых числа очень легко, а вот найти сомножители, зная произведение — довольно трудно.

Вторая особенность этой книги — ее простота. Книга написана автором для студентов первого курса, что в переводе на русский язык означает, что она вполне доступна интересующемуся школьнику 9, 10, 11 класса. Никаких, или почти никаких, предварительных знаний ее чтение не потребует.

Прочтя ее, Вы узнаете многие интересные факты из теории чисел и из ее истории, поймете, на чем основаны ее приложения к криптографии. Если же Вы не сочтете за труд прорешать предлагаемые в ней задачи, то после этого Вы будете готовы читать и более сложные книги. А главное, Вы почувствуете красоту теории чисел, про которую Эсхил говорил: «наука чисел, из наук важнейшая».

М. А. Цфасман

Предисловие автора

Эта книга приглашает Вас в путешествие, конечная цель которого — (RSA), знаменитая система шифрования с открытым ключом Ривеста, Шамира и Адлемана (Rivest, Shamir, Adleman). Путешествие будет неспешным, с большим количеством остановок, на которых можно полюбоваться окружающим пейзажем и познакомиться с историческими достопримечательностями.

На самом деле, книга посвящена скорее математическим вопросам, чем криптографии. Хотя мы и изучим подробно работу системы шифрования RSA, детали ее реализации останутся в стороне. Вместо этого мы сосредоточимся на возникающих в связи с ней математических проблемах — разложение числа на простые множители и определение, является ли число составным или простым. Эти вопросы принадлежат к числу старейших в области, известной под именем теории чисел, которая с античных времен служит источником множества интригующих задач. В этой области работали такие математики, как Эвклид (Euclid), Ферма (Fermat), Эйлер (Еиler), Лагранж (Lagrange), Лежандр (Legendre), Гаусс (Gauss), Риман (Riemann), а также, во времена не столь отдаленные, А. Вейль (Weil), Делинь (Deligne) и Уайлс (Wiles).

Предлагаемый в этой книге подход к теории чисел отличается от классического подхода старых монографий в некоторых важных аспектах. Мы всюду подчеркиваем

алгоритмическую сторону дела, не забывая строго обосновать все встречающиеся на нашем пути алгоритмы. Разумеется, со времен Эвклида теория чисел была пронизана алгоритмами, однако до самого последнего времени этот подход казался несколько старомодным. Мы относимся к нему очень серьезно. Так, доказательству Эвклида бесконечности множества простых чисел предшествует обсуждение формулы праймориала, а существование примитивных корней по модулю простого числа доказывается с помощью алгоритма Гаусса, который тот изобрел для вычисления корней.

Таким образом, в действительности эта книга об алгоритмической теории чисел и ее применениях к системе шифрования RSA. Но хотя цель и обозначена очень четко, изложение ни в коем случае не зациклено на ней. На самом деле, мы не всегда следуем кратчайшим путем, предпочитая тот, который способен пролить больше света на интересующий нас вопрос. Этим объясняется обращение к понятию группы, с помощью которого различные методы разложения числа на простые множители получают в главах 10 и 11 единое толкование. Наше отклонение в теорию групп заводит аж до теоремы Лагранжа и содержит обсуждение групп симметрий.

В основу книги легли записки лекций, предназначенных для программистов-первокурсников. Некоторые ее особенности объясняются слабой подготовкой студентов. Так, она предполагает у читателя лишь незначительные предварительные математические познания. Практически не используется ничего, кроме формулы для суммы геометрической прогрессии и биномиального разложения. Кроме того, хотя предметом книги и являются алгоритмы, никакого предварительного знакомства с программированием не требуется. Можно ожидать, однако (благодаря самому выбору предмета), что процент компьютерно грамотных читателей окажется значительным. Поэтому в конце каждой главы приведены (необязательные) упражнения, иллюстрирующие описанные в тексте алгоритмы.

Цель многих из них состоит в получении числовых данных для проверки известных формул или гипотез в теории чисел. Их можно отнести к тому, что некоторые называют компьютерным экспериментом.

Скажем несколько слов о стиле. Иногда математические книги представляют собой сухую последовательность определений, теорем и доказательств. Такой стиль восходит к «Элементам» Эвклида, и в конце двадцатого века он приобрел силу стандарта. Не будем забывать, однако, что этот монументальный стиль не был доминирующим даже среди греческих математиков. Архимед (Archimedes), к примеру, рассказывал читателям о возникавших на его пути трудностях и тупиках, куда ему случалось забредать, и даже предупреждал их об утверждениях, которыми он пользовался и которые впоследствии оказывались ложными. В этой книге я следую скорее примеру Архимеда, нежели Эвклида, и сделанный мною выбор заметно влияет на способ изложения. Во-первых, исторические комментарии вживлены в текст, а не выделены в отдельные примечания, а их предметом может служить все, что угодно: от истоков теории групп до анекдотов. Во-вторых, алгоритмы записаны на обычном языке, и я не стремлюсь к их оптимизации — если только она не работает на понимание. Пять лет преподавания излагаемого материала убедили меня в том, что программирование предложенных алгоритмов не вызывает сколь-нибудь заметных трудностей у всякого, имеющего необходимую подготовку.

Следует отметить еще одну особенность книги: у каждой важной теоремы и у всякого важного алгоритма есть свое имя. В большинстве своем это классические имена, которые используются в этом качестве уже десяти- или столетиями. Другие изобретены мной. По некоторым из них, как, скажем, теорема о примитивном корне, формулировка результата немедленно восстанавливается всяким, знакомым с предметом изложения; для других сделать это труднее. Чтобы облегчить поиск, я

выделил названия основных теорем и алгоритмов в отдельный указатель, снабдив их дополнительно кратким описанием. Ссылка на безымянные результаты идет по номерам глав и разделов, в которых они содержатся.

Этот труд представляет собой переработанный вариант книги, опубликованной впервые на португальском языке в 1997 году, и в ее основе лежат лекции, прочитанные студентам-первокурсникам факультета программирования Федерального университета Рио де Жанейро. Я обязан студентам, слушавшим этот курс в течение последних пяти лет, больше, чем я способен выразить словами. Их участие повлияло как на стиль изложения, так и на содержание книги, а их предложения и критика помогли мне исправить ошибки и упростить многие доказательства.

Я особенно благодарен Жонасу де Миранда Гомесу. Именно он первым высказал мысль об издании английского варианта и провел все необходимые переговоры. Без него книга попросту не зародилась бы. Я также чрезвычайно благодарен Амилькару Пачеко и Мартину Холланду за предложения и комментарии.

И, наконец, я выражаю благодарность всем работникам издательства А. К. Петере, с которыми я сотрудничал при создании этой книги. Их поддержка и спокойствие, даже в моменты, когда у меня опускались руки, помогли мне довести работу до завершения.

Рио де Жанейро, 18 июля 1998 года