Со времен Ферма теория чисел серьезно продвинулась вперед. То же произошло и с алгеброй, где акцент сместился с символьного представления неизвестных чисел на общие свойства символьных систем, определяемых конкретными правилами. Эти две области исследований в значительной мере перекрываются. Кое-какие интереснейшие идеи о тайных шифрах появились на стыке двух специальных разделов алгебры и теории чисел: конечных полей и эллиптических кривых. Чтобы понять, о чем идет речь, для начала нужно разобраться, что это такое.
Мы видели, что в арифметике по некоторому модулю можно складывать, вычитать и умножать «числа», подчиняясь при этом обычным алгебраическим правилам. Чтобы не отвлекаться, я не стал перечислять эти правила, но типичными их примерами могут служить переместительный (коммутативный) ab = ba и сочетательный (ассоциативный) (ab)c = a(bc) законы умножения. Аналогичные законы существуют и для сложения. Распределительный (дистрибутивный) закон a(b + c) = ab + ac тоже выполняется, и есть еще простые правила относительно 0 и 1, такие как 0 + a = a и 1a = a. Любая система, в которой выполняются эти законы, называется кольцом. Если в системе возможно также деление (кроме деления на 0) и стандартные правила выполняются, мы получаем поле. Эти названия традиционны, заимствованы из немецкого и означают просто «некий набор вещей, подчиняющихся обозначенным правилам». Целые числа по модулю 26 образуют кольцо, известное как Z26. Мы видели, что там есть проблемы с делением на 2 и 13, так что это не поле. Я сказал (не поясняя почему), что целые числа по простому модулю не имеют подобных проблем, так что Z2, Z3, Z5, Z7 и т. д. – целые числа по модулю 2, 3, 5, 7 и т. д. – все являются полями.
Обычные целые числа продолжаются до бесконечности и образуют бесконечное множество. Такие системы, как Z26 и Z7, напротив, конечны. Первая из них включает в себя только числа 0–25, а вторая – числа 0–6. Первая представляет собой конечное кольцо, вторая – конечное поле. Конечные числовые системы, если они не слишком велики, очень хорошо подходят для компьютерных вычислений, потому что те могут проводиться точно. Поэтому неудивительно, что на основе конечных полей построено множество различных кодов. Это не только криптографические шифры, которые должны обеспечивать секретность, но и коды распознавания и коррекции ошибок, задача которых – обеспечить прием сообщений без ошибок, возникающих из-за случайного «шума», такого как электрические помехи. Этими вопросами занимается целая новая область математики – теория кодирования.
Простейшими конечными полями являются Zp, целые числа по простому модулю p. Тот факт, что они образуют поле, был известен (хотя и не в такой формулировке) Ферма. Французский революционер Эварист Галуа, убитый на дуэли в 20-летнем возрасте, доказал, что это не единственные существующие конечные поля. Он нашел их все: существует одно конечное поле для каждой простой степени pn, и содержит оно ровно pn различных «чисел». (Предупреждение: если n больше 1, это поле не является полем целых чисел по модулю pn.) Таким образом, существуют конечные поля с 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, … элементами, но не с 1, 6, 10, 12, 14, 15, 18, 20, 21, 22, 24, … элементами. Очень любопытная теорема.
Эллиптические кривые (с эллипсами они связаны лишь очень опосредованно) зародились в другой области – в классической теории чисел. Около 250 года древнегреческий математик Диофант Александрийский написал трактат о решении алгебраических уравнений с использованием натуральных (или рациональных) чисел. Например, знаменитый треугольник 3–4–5 имеет прямой угол, спасибо Пифагору, потому что 32 + 42 = 52. Следовательно, эти числа являются решением Пифагорова уравнения x2 + y2 = z2. Одна из теорем Диофанта показывает, как найти все решения этого уравнения в долях и, в частности, в натуральных числах. Область в целом, где речь идет о решении уравнений в рациональных числах, получила известность как диофантовы уравнения. Ограничение до рациональных чисел меняет правила игры; например, x2 = 2 может быть решено в действительных числах, но не в рациональных.
Одна из задач Диофанта звучит так: «Разделить заданное число на два числа, произведение которых равно кубу за вычетом его стороны». Если первоначальное число равно a, мы можем разбить его на Y и a – Y, и тогда нам потребуется решить уравнение
Y (a – Y) = X3 – X.
Диофант исследовал случай, когда a = 6. Подходящая замена переменных (вычесть 9, заменить Y на y + 3, а X на – x) превращает это уравнение в
y2 = x3 – x + 9.
Отсюда он вывел решение X = 17/9, Y = 26/27.
Чтобы «сложить» две точки P и Q на эллиптической кривой, соедините их прямой, которая пересечет кривую в третьей точке P*Q. Затем постройте точку, симметричную данной относительно оси x, это и будет P + Q
Интересно, что аналогичные уравнения появились в геометрии, когда математики попытались использовать аналитический метод (продвинутый вариант дифференциального и интегрального исчисления) для расчета длины дуги сегмента эллипса. Именно отсюда берет начало термин «эллиптическая кривая». Ученые знали, как найти ответ на аналогичный вопрос для окружности с использованием интегрального исчисления, так что задача сводилась к нахождению интеграла функции, в которой присутствовал квадратный корень из квадратного многочлена, а это можно сделать при помощи (обратных) тригонометрических функций. Этот же метод в применении к эллипсу дает интеграл функции, в которой присутствует квадратный корень из кубического многочлена, и после нескольких бесплодных экспериментов стало ясно, что необходим какой-то новый класс функций. Эти функции оказались довольно красивыми, хотя и сложными и получили наименование эллиптических функций из-за их связи с длиной дуги эллипса. Квадратный корень из кубического многочлена есть решение y уравнения
y2= x3+ ax + b
(любое слагаемое с x2 может быть превращено в 0 при помощи эквивалентных преобразований). В координатной геометрии это уравнение определяет кривую на плоскости, так что такие кривые (и их алгебраический вариант в виде уравнения) стали называть эллиптическими кривыми.
Если коэффициенты целые, мы можем рассмотреть данное уравнение в модулярной арифметике, скажем в Z7. Каждое решение в обычных целых числах приведет нас к решению в арифметике по модулю 7. Поскольку эта система конечна, можно воспользоваться методом проб и ошибок. Для диофантова уравнения y2 = x3 – x + 9 мы быстро обнаруживаем все его решения (mod 7):
Из этих решений можно сделать вывод, обязательный для любого решения в обычных целых числах: по модулю 7 любое решение должно сводиться к одному из этих шести. То же относится и к рациональным решениям при условии, что знаменатель у них не кратен 7 – такие решения запрещены, поскольку в Z7 такой знаменатель превращается в 0. Если заменить 7 на какое-нибудь другое число, то можно получить больше информации о форме любого рационального решения.
Теперь мы смотрим на эллиптические кривые – уравнения – через призму конечных колец и полей. Геометрический образ кривой здесь, по существу, неприменим, поскольку имеется всего лишь конечное множество точек, но нам удобно пользоваться прежним названием. На рисунке показана типичная фигура и ее дополнительное свойство, известное еще Ферма и Эйлеру и интриговавшее математиков в начале XX века. Имея два решения, можно «сложить» их, чтобы получить еще одно решение, как показано на рисунке. Если решения – рациональные числа, то рациональным числом будет и их сумма. Это не просто «купи два, получи третье бесплатно», а «купи два, получи бесплатно уйму всего», потому что операцию и построение можно повторить. Иногда это вновь приводит нас в одну из начальных точек, но в основном подобные действия генерируют бесконечно много различных решений. Мало того, эти решения имеют красивую алгебраическую структуру: они образуют группу Морделла – Вейля эллиптической кривой. Луис Морделл доказал ее основные свойства, а Андре Вейль обобщил их. Слово «группа» здесь означает, что дополнение подчиняется короткому списку простых правил. Эта группа коммутативна, то есть P + Q = Q + P, что очевидно из рисунка, поскольку прямая, проведенная через P и Q, совпадает с прямой, проведенной через Q и P. Существование такой групповой структуры – явление необычное, и большинство диофантовых уравнений не может этим похвастаться. Многие из них вовсе не имеют решений, некоторые имеют всего по несколько, и трудно предсказать, какое именно уравнение находится перед вами. В настоящее время эллиптические кривые находятся в центре интенсивных исследований – по этой и другим причинам. Доказывая Великую теорему Ферма, Эндрю Уайлс доказал глубокую гипотезу об эллиптических кривых, которая стала одним из ключевых этапов доказательства.
Групповая структура эллиптической кривой интересует и криптографов. Обычно она рассматривается как форма «дополнения» к решениям, хотя формула там намного сложнее, потому что она коммутативна, и символ + стал традиционным в теории коммутативных групп. В частности, если есть решение (x, y), которое можно рассматривать как точку на плоскости, то мы можем генерировать решения