Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 24)

Простейшими конечными полями являются Z_p, целые числа по простому модулю p. Тот факт, что они образуют поле, был известен (хотя и не в такой формулировке) Ферма. Французский революционер Эварист Галуа, убитый на дуэли в 20-летнем возрасте, доказал, что это не единственные существующие конечные поля. Он нашел их все: существует одно конечное поле для каждой простой степени pⁿ, и содержит оно ровно pⁿ различных «чисел». (Предупреждение: если n больше 1, это поле не является полем целых чисел по модулю pⁿ.) Таким образом, существуют конечные поля с 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 имеет прямой угол, спасибо Пифагору, потому что 3² + 4² = 5². Следовательно, эти числа являются решением Пифагорова уравнения x² + y² = z². Одна из теорем Диофанта показывает, как найти все решения этого уравнения в долях и, в частности, в натуральных числах. Область в целом, где речь идет о решении уравнений в рациональных числах, получила известность как диофантовы уравнения. Ограничение до рациональных чисел меняет правила игры; например, x² = 2 может быть решено в действительных числах, но не в рациональных.

Одна из задач Диофанта звучит так: «Разделить заданное число на два числа, произведение которых равно кубу за вычетом его стороны». Если первоначальное число равно a, мы можем разбить его на Y и a – Y, и тогда нам потребуется решить уравнение

Y (a – Y) = X³ – X.

Диофант исследовал случай, когда a = 6. Подходящая замена переменных (вычесть 9, заменить Y на y + 3, а X на – x) превращает это уравнение в

y² = x³ – x + 9.

Отсюда он вывел решение X = 17/9, Y = 26/27.

Чтобы «сложить» две точки P и Q на эллиптической кривой, соедините их прямой, которая пересечет кривую в третьей точке P*Q. Затем постройте точку, симметричную данной относительно оси x, это и будет P + Q

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

y² = x³ + ax + b

(любое слагаемое с x² может быть превращено в 0 при помощи эквивалентных преобразований). В координатной геометрии это уравнение определяет кривую на плоскости, так что такие кривые (и их алгебраический вариант в виде уравнения) стали называть эллиптическими кривыми.

Если коэффициенты целые, мы можем рассмотреть данное уравнение в модулярной арифметике, скажем в Z₇. Каждое решение в обычных целых числах приведет нас к решению в арифметике по модулю 7. Поскольку эта система конечна, можно воспользоваться методом проб и ошибок. Для диофантова уравнения y² = x³ – x + 9 мы быстро обнаруживаем все его решения (mod 7):

Из этих решений можно сделать вывод, обязательный для любого решения в обычных целых числах: по модулю 7 любое решение должно сводиться к одному из этих шести. То же относится и к рациональным решениям при условии, что знаменатель у них не кратен 7 – такие решения запрещены, поскольку в Z₇ такой знаменатель превращается в 0. Если заменить 7 на какое-нибудь другое число, то можно получить больше информации о форме любого рационального решения.

Теперь мы смотрим на эллиптические кривые – уравнения – через призму конечных колец и полей. Геометрический образ кривой здесь, по существу, неприменим, поскольку имеется всего лишь конечное множество точек, но нам удобно пользоваться прежним названием. На рисунке показана типичная фигура и ее дополнительное свойство, известное еще Ферма и Эйлеру и интриговавшее математиков в начале XX века. Имея два решения, можно «сложить» их, чтобы получить еще одно решение, как показано на рисунке. Если решения – рациональные числа, то рациональным числом будет и их сумма. Это не просто «купи два, получи третье бесплатно», а «купи два, получи бесплатно уйму всего», потому что операцию и построение можно повторить. Иногда это вновь приводит нас в одну из начальных точек, но в основном подобные действия генерируют бесконечно много различных решений. Мало того, эти решения имеют красивую алгебраическую структуру: они образуют группу Морделла – Вейля эллиптической кривой. Луис Морделл доказал ее основные свойства, а Андре Вейль обобщил их. Слово «группа» здесь означает, что дополнение подчиняется короткому списку простых правил. Эта группа коммутативна, то есть P + Q = Q + P, что очевидно из рисунка, поскольку прямая, проведенная через P и Q, совпадает с прямой, проведенной через Q и P. Существование такой групповой структуры – явление необычное, и большинство диофантовых уравнений не может этим похвастаться. Многие из них вовсе не имеют решений, некоторые имеют всего по несколько, и трудно предсказать, какое именно уравнение находится перед вами. В настоящее время эллиптические кривые находятся в центре интенсивных исследований – по этой и другим причинам. Доказывая Великую теорему Ферма, Эндрю Уайлс доказал глубокую гипотезу об эллиптических кривых, которая стала одним из ключевых этапов доказательства.

Групповая структура эллиптической кривой интересует и криптографов. Обычно она рассматривается как форма «дополнения» к решениям, хотя формула там намного сложнее, потому что она коммутативна, и символ + стал традиционным в теории коммутативных групп. В частности, если есть решение (x, y), которое можно рассматривать как точку на плоскости, то мы можем генерировать решения P + P, P + P + P и т. д. Естественно называть такие решения 2P, 3P и т. д.

В 1985 году Нил Коблиц и Виктор Миллер независимо друг от друга поняли, что можно применить этот групповой закон к эллиптической кривой, чтобы получить шифр. Идея в том, чтобы работать в конечном поле с большим числом элементов. Чтобы зашифровать P, мы получаем kP для очень большого целого числа k, что несложно сделать при помощи компьютера, и называем результат Q. Чтобы обратить этот процесс, мы должны начать с Q и найти P – по существу, разделить Q на k. Из-за сложности групповой формулы обратный расчет очень труден, так что мы придумали новый тип «односторонней» функции с потайным входом, а следовательно, новую криптосистему с открытым ключом. Этот подход известен как шифрование на основе эллиптических кривых, или ECC (Elliptic Curve Cryptography). Точно так же, как RSA может применяться с использованием множества разных простых чисел, ECC может применяться с использованием множества разных эллиптических кривых над множеством разных конечных полей, с разным выбором P и множителя k. Здесь опять же имеется секретный ключ, который позволяет выполнить быструю расшифровку.

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

Как и в случае RSA, не существует строгого доказательства надежности системы ECC. Диапазон возможных атак аналогичен диапазону атак, осуществляемых в отношении RSA.

В настоящее время наблюдается серьезный интерес к криптовалютам, которые представляют собой финансовые системы, не контролируемые традиционными банками, хотя банки тоже начинают интересоваться ими. Банки – они такие: всегда начеку, всегда в поисках новых способов делать деньги. Самая известная криптовалюта – биткоин. Надежность биткоинов обеспечивается таким методом, как блокчейн, который представляет собой шифрованную запись всех транзакций с участием конкретной «монеты» (coin). Новые биткоины появляются в результате майнинга, который, по существу, означает выполнение громадного количества бессмысленных в остальном вычислений. Майнинг биткоинов потребляет значительное количество электроэнергии без какой бы то ни было полезной цели, за исключением обогащения нескольких индивидов. В Исландии, где электричество очень дешево благодаря геотермальным электростанциям, на майнинг биткоинов уходит больше электричества, чем используют все домохозяйства страны, вместе взятые. Вряд ли эта деятельность помогает бороться с глобальным потеплением и климатическим кризисом, но дело обстоит именно так.