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

Далее будем предполагать, что с делится на d.

Тогда мы можем записать а = dp, b = dq и с = dr, где р и q — взаимно простые.

Сначала рассмотрим случай с = 0, то есть однородное уравнение ах + by = 0.

91

Разделив на d первый член уравнения, получим следующее: достаточно решить уравнение рх + qy = 0, или, что аналогично, рх = —qy. Будем рассуждать следующим образом: так как рх равно — qy, qy должно делиться на р. Однако р и q взаимно простые, следовательно, остается единственный вариант: у делится на р, то есть существует целое число Λ такое, что у = Λр. Аналогично доказывается, что х делится на q, поэтому существует другое целое число μ такое, что х = μq. Подставив значения х и у в уравнение, получим: μpq = —Λpq, то есть μ = —Λ, так как pq отлично от нуля. Следовательно, решениями уравнения ах + by = 0 будет пара чисел (q, —р) и всех кратных им чисел (Λq, —Λр).

Теперь предположим, что с отлично от нуля. Если известно два решения (x 0, у 0) и (х 1y 1) уравнения ах + by = с, то:

а(х 0- х 1) + b(у 0- у 1) = (ах 0+ by 1-(ax 1+by 1) = с-с = О,

откуда следует, что (x 0— x 1, у 0— y 1) — решение однородного уравнения ах + by = 0.

Так как все решения этого уравнения имеют вид (Λq, —Λр), найдется целое число Λ такое, что x 0— x 1= Λq и у 0— у 1= —Λр, или, что аналогично, х = x 0— Λq и y 1= y 0+Λр. Иными словами, уравнение имеет бесконечно много решений, но все они выводятся из частного решения (x 0, у 0). Напомню, что р и q — результат деления а и b на наибольший общий делитель. Следовательно, мы доказали, что все решения выглядят так:

где (x 0, у 0) — частное решение, Λ — любое целое число. Теперь всего лишь осталось найти метод, позволяющий получить (x 0, у 0). Найти эти решения нетрудно, если р и q — взаимно простые, так как по соотношению Безу существуют два целых числа u и v такие, что рu + qv— 1. Умножив u и v на r, получим два числа x 0= ur и у 0= vr такие, что ax 0+ by 0= с.

Рассмотрим пример. Допустим, мы хотим решить диофантово уравнение 50х + 120у = 20.

Мы уже знаем, что наибольший общий делитель 50 и 120 равен 10.

Так как 20 делится на 10, уравнение имеет решение.

92

В этом случае в упрощенном виде уравнение выглядит так: 5х + 12у = 2. Найдем числа, которые мы обозначили через u и v. Так как 1 = 5 — 2 ·2 и 2 = 12 — 2·5, имеем

1 = 5 - 2 · (12 - 2 · 5) = 5 · 5 - 2 · 12,

то есть u = 5, v = —2. Умножив эти значения на 2, получим частное решение (10, —4), на основе которого можно найти общее решение:

Посмотрим, как диофантовы уравнения используются в системе шифрования с открытым ключом. Напомним, что для данного натурального числа n группа целых чисел со сложением по модулю n состоит из элементов [0], [1], [2]...[n — 1], а сложение выполняется следующим образом: сначала мы складываем элементы группы как обычные числа, затем вычитаем n из полученного результата до тех пор, пока не получим число, заключенное на интервале от 0 до n — 1. Аналогично можно определить операцию умножения. Допустим, n = 7 и нам нужно вычислить произведение 4*5. Сначала умножим эти два числа так же, как и целые числа. Получим 20.

Теперь нужно вычесть из этого результата 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, которое не является квадратом.