Андрей Райгородский - Кому нужна математика? Понятная книга о том, как устроен цифровой мир

K B = ( g x − kp) y (mod p ).

Заметим, что в выражении для K A можно расписать ( g y − lp ) x следующим образом:

где А – это целое число, то есть рА делится на р. Таким образом получаем

K A = (( g y − lp ) x ) (mod p ) = (( g y ) x + pA ) (mod p ) = ( g y ) x (mod p ).

Совершенно аналогично для какого-то целого числа B получаем

K B = (( g x − kp ) y ) (mod p ) = (( g x ) y + pB ) (mod p ) = ( g x ) y (mod p ).

Результат теперь очевиден, поскольку

( g y ) x = g yx = g xy = ( g x ) y .

Вспомним, что логарифм числа у по основанию g – это такое число х, для которого выполняется

g x = y .

Легко заметить, что очень похожая операция лежит в основе схемы Диффи – Хеллмана.

После возведения в степень мы берем остаток от деления на р. Как мы уже упоминали выше, в математике такая операция обозначается g x (mod p ) (читается « g в степени х по модулю р »). При этом, естественно, g и х натуральные числа и у g нет общих делителей с р.

Одна нетривиальная теорема из теории чисел (см., например, {35}) утверждает, что для каждого простого р существует такое число g, что все числа

разные, то есть служат перестановкой множества 1, 2, …, p − 1 (среди них нет нуля, поскольку g < p и, значит, g х не делится на р ). Например,

Из этого следует возможность корректного определения дискретного логарифма, который еще называется индексом. А именно: «логарифм» произвольного числа y ∈ {1, 2, …, p − 1} по основанию g – это тот самый, уникальный, x ∈ {1, 2, …, p − 1}, при котором выполняется g x (mod p ) = y . Поскольку для всех x < p остатки разные, то х определяется однозначно. Операция нахождения такого х называется операцией дискретного логарифмирования. Она очень сложная, и никто не знает, можно ли придумать способ ее быстрой реализации.

Как определить такое число g, чтобы все остатки в выражении (П.15) были разные? Число g обладает этим свойством, если оно является первообразным корнем числа р. Мы позволим себе рассказать об этом понятии немножко подробнее.

Есть такая теорема Эйлера: если х и m взаимно просты, то g φ (m) ≡ 1. Здесь a ≡ b , если a − b делится на m . Другими словами, у а и b одинаковый остаток от деления на m . А φ (m) это функция Эйлера, равная количеству чисел, не превосходящих m и взаимно простых с ним. Например, если m = p , где р простое, то φ (p) = p − 1 и теорема Эйлера превращается в малую теорему Ферма.

Условие теоремы Эйлера достаточное, но не необходимое. Вполне может случиться и так, что x a ≡ 1 (mod m ), хотя a < φ (m) . Самый простой пример такой ситуации – это, конечно, x = 1. Действительно, x a ≡ 1 (mod m ) для любых натуральных a и m . Но есть и менее тривиальные примеры. Скажем, p = 5, а 4² = 16 ≡ 1(mod 5), хотя 2 < p − 1 = 4.

Формально число g называется первообразным корнем по модулю m , если

Пример (отсутствие первообразных корней у m = 2 k ).Возьмем m = 2 k при k ≥ 3. В этом случае можно показать, что для любого натурального х выполняется