Хавьер Фресан - Мир математики - m. 35 Пока алгебра не разлучит нас. Теория групп и ее применение.

Теперь нужно вычесть из этого результата 7 нужное число раз: после первого вычитания получим 13, после второго — 6, что меньше 7. Следовательно, произведение 4 и 5 по модулю 7 равно 6.

Теперь перейдем к криптографии.

Допустим, что Боб хочет отправить Алисе секретное сообщение. Так как любую информацию можно представить с помощью чисел, достаточно решить задачу о защищенной передаче числа m. Боб знает открытый ключ Алисы (он доступен всем).

У Алисы также есть закрытый ключ, известный только ей. Следует различать три этапа передачи сообщения: генерация ключей, шифрование сообщения и расшифровка.

Сначала покажем, как генерируются ключи. Выберем два простых числа р и q.

В принципе, достаточно, чтобы произведение р и q (обозначим его через n), было больше числа m, которое нужно передать. Но наш метод шифрования будет обеспечивать достаточный уровень защиты только тогда, когда р и q будут достаточно большими и никакой компьютер не будет способен разложить n на простые множители за разумное время. Выберем два простых числа р и р, состоящие из 300—400 знаков.

93

Введем величину r = (р — 1)(q — 1) и выберем число е, меньшее r и взаимно простое с ним. Пара (n, е) будет открытым ключом. Чтобы сгенерировать закрытый ключ, нужно решить диофантово уравнение ex + ry = 1. Если мы обозначим через d первое число из пары, которая является решением этого уравнения, то закрытый ключ будет представлять собой пару (n, d).

Теперь, когда открытый и закрытый ключ известны, нужно действовать следующим образом: Боб шифрует сообщение, возведя m в степень е, находит результат возведения в степень по модулю n и отправляет Алисе полученное значение с =m e(по модулю n).

Для расшифровки сообщения Алиса возводит с в степень d, определяемую закрытым ключом, и находит результат по модулю n. Этой простой операции достаточно для восстановления зашифрованной информации, так как можно доказать, что c dпо модулю 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. Но если (x 1, y 1) и (х 2, у 2) — решения уравнения, то

Перемножив уравнения, получим:

(x 1+y 1√d)(x 1-y 1√d)(x 2+y 2√d)(x 2-y 2√d) = l. (*)

Начнем раскрывать скобки с выражений со знаком плюс:

(x 1+y 1√d)(x 2+y 2√d) = x 1x 2+ x 1y 2√d + x 2y 1√d + y 1y 2(√d) 2

Важно отметить, что произведение этих двух множителей будет иметь аналогичную структуру, так как (√d) 2равно d по определению. Если мы введем обозначения х 3= х 1х 2+ dy 1y 2и у 3= x 1y 2+ x 2y 1получим равенство: