93
Введем величину r = (р — 1)(q — 1) и выберем число е, меньшее r и взаимно простое с ним. Пара (n, е) будет открытым ключом. Чтобы сгенерировать закрытый ключ, нужно решить диофантово уравнение ex + ry = 1. Если мы обозначим через d первое число из пары, которая является решением этого уравнения, то закрытый ключ будет представлять собой пару (n, d).
Теперь, когда открытый и закрытый ключ известны, нужно действовать следующим образом: Боб шифрует сообщение, возведя m в степень е, находит результат возведения в степень по модулю n и отправляет Алисе полученное значение с =me (по модулю n).
Для расшифровки сообщения Алиса возводит с в степень d, определяемую закрытым ключом, и находит результат по модулю n. Этой простой операции достаточно для восстановления зашифрованной информации, так как можно доказать, что cd по модулю n всегда равно m.
Теперь, когда мы полностью рассказали о линейных диофантовых уравнениях, перейдем к диофантовым уравнениям второй степени.
Рассмотрим уравнение х² — dy² = 1, где d — целое положительное число.
Это уравнение имеет большую историю и упоминается в литературе как уравнение Пелля — Ферма, хотя Джон Пелль никогда не работал с ним.
Дело в том, что Эйлер ошибочно приписал Пеллю метод решения уравнений, который на самом деле нашел английский математик Уильям Броункер при решении задачи, предложенной Пьером Ферма.
Сначала предположим, что d = 1, то есть попробуем найти целые решения уравнения х² — у² = 1. Так как разность квадратов всегда можно представить в виде произведения по формуле
x² - y² = (х + у)(х - у),
нам нужно решить уравнение (х + у)(х — у) = 1. Произведение целых чисел может равняться 1 только тогда, когда оба сомножителя равны 1 или —1. Рассмотрим два этих случая по отдельности. В первом случае имеем:
94
Сложив уравнения системы, имеем 2х = 2, следовательно, х = 1, у = 0. Аналогично решениями системы х + у = х — у = — 1 будут х = —1, у = 0. Следовательно, уравнение х² — у² = 1 имеет всего два целых решения: (—1, 0) и (1, 0). Аналогично можно исключить случай, когда d — квадрат, то есть имеет вид d = е²: в этом случае х² — dy² = х² — е²у² = х² — (еу)². Путем замены переменной z = еу получим то же самое уравнение х² — z² = 1. Его решения уже известны. Далее будем предполагать, что d — целое число, большее либо равное 2, которое не является квадратом.
Основа анализа уравнений первой степени заключается в том, чтобы показать, как из двух решений ах + by = с получается пара целых чисел (х, у), таких что ах +
+ by = 0. В этом случае вы увидите, что если нам известны два решения уравнения
Пелля — Ферма, то из них можно вывести третье. Для этого нужно представить выражение х² — dy² в виде
х² - dy² =(x+y√d)(x-y√d).
Эти множители уже не будут целыми числами (они содержат квадратный корень числа, которое не является квадратом), следовательно, они не могут одновременно равняться 1 или —1. Но если (x1, y1) и (х2, у2) — решения уравнения, то
Перемножив уравнения, получим:
(x1+y1 √d)(x1-y1√d)(x2+y2√d)(x2-y2√d) = l. (*)
Начнем раскрывать скобки с выражений со знаком плюс:
(x1+y1√d)(x2+y2 √d) = x1x2 + x1y2√d + x2y1√d + y1y2(√d)2
Важно отметить, что произведение этих двух множителей будет иметь аналогичную структуру, так как (√d)2 равно d по определению. Если мы введем обозначения х3 = х1х2 + dy1y2 и у3 = x1y2 + x2y1 получим равенство:
(x1+у1√d)(x2+у2√d) = х3+y3√d.
95
Так как выполняется равенство
(x1-y1√d)(x2-y2 √d) = x1x2 - x1y2√d - x2y1√d + y1y2(√d)2 = х3-y3√d
мы можем записать уравнение (*) в следующем виде:
(х3+y3√d)(х3-y3√d) = 1.
Из этого равенства следует, что (х3, y3) является решением уравнения Пелля — Ферма.
Мы получили третье решение на основе двух известных. Кроме того, так как в формулах расчета х3 и у3 используются только сложение и умножение, то если решения (x1, y1) и (х2, у2) целочисленные, то целыми будут и (х3, у3).
Обозначим через • операцию, которая сопоставляет двум известным решениям третье. Наша цель — доказать следующий результат:
Предложение. Операция (х1, у1) • (х2, у2) = (х3, у3) определяет абелеву группу на множестве целых решений уравнения Пелля — Ферма.
Коммутативность этой операции следует из определения, так как значения х3 и у3 не изменятся, если мы поменяем местами (x1, y1) и (х2, у2). Следовательно, достаточно показать, что выполняются три аксиомы, которые включает определение группы. Первая из них, аксиома ассоциативности, непосредственно следует из ассоциативности произведения вещественных чисел. Теперь найдем нейтральный элемент группы. Заметим, что (1, 0) всегда будет решением уравнения х² — dy² = 1.
Посмотрим, что произойдет, если мы применим рассматриваемую операцию к этому решению и другому, произвольному решению (х2, у2). По нашим формулам, х3 = 1 · х2 + d * 0 · у2 = х2 и у3 = 1 у2 + х2 · 0 = yv следовательно, (1,0) • (х2, у2) = (х2, у2). Нейтральный элемент найден. Осталось показать, что для каждого решения существует обратное, то есть что для данного (х1, у1) мы можем найти другое решение (х2, y2) такое, что (x1, y1) · (x2, y2) = (1, 0).
Проще всего доказать это утверждение для пары чисел (х1, -y1), которая вновь будет решением уравнения, поскольку квадраты любого числа и противоположного ему совпадают. Кроме того,
(x1, у1)•(x1, -у1) - (x1² -dy1² - x1y1 + x1y1) = (1,0),
96
так как пара чисел (х1, y1) является решением уравнения х² — dy² = 1. Отсюда следует, что целые решения уравнения Пелля — Ферма образуют абелеву группу. Возникает вопрос: какими особенностями обладает эта группа?
Выберем из всех положительных решений уравнения Пелля — Ферма пару чисел (х, у), при которой значение выражения х² + у² будет наименьшим. Назовем это решение фундаментальным. К примеру, при d = 2 фундаментальным решением будет (3, 2). Так как З² — 2 -2² = 9 — 2·4 = 1, то эта пара чисел действительно будет решением. Осталось показать, что значение выражения х² + у² при х = 3, у = 2 будет наименьшим. Заметим, что ни одно из положительных чисел в решении не может равняться 1, так как при х = 1 у=0, а 0 — не положительное число.
Если же у = 1, то х² = 3 — это уравнение не имеет целых решений. Таким образом, единственным решением, меньшим (3, 2), может быть пара чисел (2, 2).
Однако 2²—2 · 2² = —4, следовательно, эта пара чисел не является решением уравнения.
Мы доказали, что (3, 2) — фундаментальное решение. Если мы будем последовательно выполнять операцию • над этим решением, то получим бесконечное число решений уравнения Пелля — Ферма. К примеру, (3, 2) • (3, 2) = (17,12), (3, 2) • (3, 2) • (3, 2) = (99, 70) также будут решениями уравнения. Сложнее показать, что все решения, полученные подобным образом, будут положительными.
Теорема Дирихле о единицах. Все целые положительные решения уравнения Пелля — Ферма можно получить из фундаментального решения.
С учетом этой теоремы рассмотрим порожденную фундаментальным решением циклическую группу, которая будет изоморфной группе целых чисел. К этой группе принадлежат все положительные решения (х, у), а также нейтральный элемент
(1, 0) и все обратные элементы вида (х, —у). Пусть пара чисел (х, у) — решение уравнения Пелля — Ферма. Так как (—х)² = х², решением уравнения также будет пара чисел (—х, у). Но теперь —х будет положительным числом, следовательно, это решение уже содержится в циклической группе, порожденной фундаментальным решением. Таким образом, достаточно всего лишь добавить знак. На языке математики эта операция выражается как прямое произведение целых чисел по модулю 2.
Подведем итог: множество целых решений уравнения Пелля — Ферма образует группу, изоморфную группе ℤ х ℤ/2.
97
Перейдем к уравнениям третьей степени и посмотрим, как можно определить группу на множестве решений уравнения у² = х3 + ах + b, где а и b — любые рациональные числа. В этом случае применим чисто геометрические методы. Начнем с того, что представим на плоскости пары вещественных чисел (х, у), которые удовлетворяют соотношению у² = x3 + ах + b. Последовательно присваивая значения одной из двух переменных и вычисляя соответствующие значения второй переменной, получим последовательность точек, которые можно соединить отрезками. Результатом будет кривая на плоскости, которая в математике называется эллиптической. Рассмотрим пример. При а = —2 и b — 1 уравнение примет вид y² = x3 — 2х +1. Если мы подставим в уравнение х = 0, правая часть примет значение 1, и мы получим уравнение y² = 1. Это уравнение имеет два решения: у = 1 и у = —1. Имеем две точки кривой:(0, 1) и (0, —1).
