Кода

В своих «Принципах Человеческого Знания», изданных в 1710 году, Джордж Беркли (George Berkeley) говорит следующее о теории чисел и ее применении:

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

Через несколько строк он добавляет:

«Вы, возможно, разделяете мнение об этих высоких материях и абстракциях, и смотрите на все вопросы, связанные с числами, как на «difficiles nugae», поскольку они не содействуют решению практических задач и не способствуют улучшению жизни.»

Между прочим, латинское выражение «difficiles nugae» переводится как «трудные мелочи».

Беркли считал, что теория чисел — самый бесполезный из всех разделов математики, доживших до XX столетия. Так и Харди, заметив, что наука может служить как во зло, так и во благо, говорит:

«Как Гаусс, так и менее выдающиеся математики могут быть оправданы тем, что есть по крайней мере одна область науки, которой они занимаются, чья отдаленность от обычной человеческой деятельности сохраняет их в чистоте и спокойствии.»

Цитата взята из знаменитой книги Харди «Апология математика» ([22]). Но нельзя забывать, что книга написана во времена Второй Мировой Войны человеком, всегда остававшимся последовательным пацифистом. Можно только предполагать реакцию Харди на приложения теории чисел, описанные в настоящей книге. Несомненно только одно: современная криптография перевернула наше представление о практической пользе теории чисел.

Заканчивая книгу, лучше всего указать на темы теории чисел и криптографии, которые не были здесь затронуты. Они послужат руководством к дальнейшему изучению предмета.

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

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

третьей. Опираясь на этот факт, можно определить операцию сложения на множестве точек кривой. Более того, эта операция наделяет эллиптическую кривую структурой группы.

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

Проблема определения рациональных точек эллиптической кривой тесно связана с решением диофантовых уравнений, уже обсуждавшихся нами. Она изучалась многими известными маг тематиками, оставаясь на переднем крае развития теории чисел. Эллиптические кривые были центральным местом доказательства великой теоремы Ферма, которое анонсировал А. Уайлс. Фактически, Уайлс доказал одну знаменитую гипотезу об эллиптических кривых и затем показал, как использовать ее при доказательстве теоремы Ферма (см. [20], ).

В работе, опубликованной в 1987 году, Ленстра (Lenstra) показал, что групповые свойства эллиптической кривой могут быть использованы для разложения больших чисел на множители. Алгоритм Ленстры наиболее эффективно применяется к целым числам, которые трудно разлагаются делением методом проб, но имеют не более 30 знаков. К счастью, сейчас доступно мастерски написанное элементарное введение в теорию эллиптических кривых, которое включает в себя подробное обсуждение алгоритма Ленстры. Это — «Рациональные точки эллиптических кривых» (1992) Сильвермана (Silverman) и Тэйта (Tate). Алгоритм Ленстры первоначально появился в [34] и детально объясняется в [8] и [11] ([Д.7]).

Второй алгоритм разложения на множители, о котором мы упоминали (квадратичное решето) лучше, чем алгоритм Лен-стры, приспособлен для разложения больших чисел. Именно метод квадратичного решета был использован для разложения открытого ключа ESA-129, упомянутого в § 1.2. Преимущество этого алгоритма заключается в той легкости, с которой он позволяет распределить задачу о разложении между несколькими компьютерами. Таким образом, добровольцы могут тратить свободное время своих персональных компьютеров для участия в титанических усилиях по разложению. Конечно, это было бы невозможно без появления интернета, по крайней мере в масштабе, который потребовался для RSA-129.

В основе квадратичного решета лежит усиление алгоритма Ферма, предложенное М. Крайчиком (М. Kraitchik) в 1920-ых годах. Оно использует идеи и методы самой известной среди любителей теории чисел теоремы, так называемого закона квадратичной взаимности, доказанного Гауссом в 1796 году. Многие математики предлагали различные усовершенствования метода Крайчика, что дало возможность С. Померанцу в 1981 году сформулировать принцип квадратичного решета. Слово «решето» употреблено здесь по существу. Действительно, ключевая идея Померанца, ускоряющая метод, основана на использовании решета, очень похожего на решето Эратосфена.

Элементарное изложение квадратичного решета можно найти в [8]. Оно включает все необходимые предварительные сведения, в том числе и доказательство закона квадратной взаг имности. История решета, рассказанная самим Померанцом, напечатана в [37].

Решето числового поля подводит нас к области квадратичных числовых полей, уже не такой элементарной теме, как упоминаемые нами до сих пор. Идея метода была распространена в письме Полларда (J.Pollard) в 1988 году. Первым большим достижением этого алгоритма было разложение на множители

155-значного девятого числа Ферма в 1990 году (см. [33]). Статья содержит описание решета числового поля, которое также приведено в [37]. Разложение ключа к ESA-130 в апреле 1996 года стало следующим триумфом алгоритма. О квадратичных числовых полях можно прочесть в [25].

Перед тем, как мы перейдем к темам, лежащим вне RSA, проясним, что на практике при взломе системы шифрования можно обойтись и без раскладывания числа на множители. Это обосновал в 1995 году Кохер (P. Kocher), независимый консультант системы безопасности, который как раз к этому моменту получил диплом биолога. Он показал, что некоторые версии RSA можно взломать, анализируя информацию о количестве времени, затрачиваемого на получение и расшифровку сообщений (см. [31]). Это показывает, что безопасность RSA, да и других криптосистем, зависит не только от развития все более эффективных алгоритмов и мощных компьютеров.

Как мы видели в главе 12, RSA не единственная трудная для взлома криптосистема, предлагаемая теорией чисел. Мы упоминали также Эль-Гамаль. Другая система того же сорта была изобретена Коблитцом (N. Koblitz) в 1987 году. Вместо возведения в степень, используемого как в RSA, так и в Эль-Гамаль, в ней вычисляется кратность точки эллиптической кривой (см. [30]).

Наконец, теория чисел все еще популярна, благодаря красивым, но, главным образом, бесполезным результатам, так резко осужденным Джорджем Беркли. Наиболее ценимая элементарная книга по теории чисел — это, конечно, классический учебник Харди и Райта «Введение в теорию чисел». В ней вы найдете доказательство закона Гаусса о квадратной взаимности, изучение разбиений целых чисел, доказательство великой теоремы Ферма для обширную информацию о квадратичных полях и массу элементарных фактов о распределении простых чисел.

Многие знакомились с теорией чисел по этой книге. Математический физик Фриман Дайсон (Freeman Dyson), получивший книгу в качестве приза в возрасте 14 лет, был одним из них. Вот что он сказал об этом произведении в 1994 году в своем интервью (см. [3]).

«Это — изумительная книга. Это — самая прекрасная книга по теории чисел, которую я знаю. Это — не учебник, но чрезвычайно удобочитаемое объяснение предмета, стиль которого делает его, вероятно, лучшим введением в математику, которое когда-либо было написано.»

Более современное введение в теорию чисел — Айрланд (Ireland) и Розен (Rosen) «Классическое введение в современную теорию чисел». Книга содержит последние достижения теории, но Вам потребуются хорошие знания основ современной алгебры (групп, полей и колец) для чтения даже самых элементарных ее глав.

Наконец, для тех, кого больше интересует история, имеется книга А. Вейля «Теория чисел: исторический подход». Написанная мастером теории чисел, также известным своими работами по истории математики, книга повествует о вкладах в науку, оставленных Ферма, Эйлером, Лагранжем и Лежандром. Это очаровательная книга и Вы, вероятно, будете часто возвращаться к ней ради предоставляемого ею чистого наслаждения.