Расширенный Евклид и обратный элемент: как делить по модулю

Если ты найдёшь обратный элемент расширенным алгоритмом Евклида, объяснишь, почему у 6 нет обратного по модулю 9, и решишь сравнение 7x ≡ 5 (mod 40), - листай до «Теперь сам».

Как думаешь, как найти x

Нужно число x, для которого 7 · x при делении на 40 даёт остаток 1. Можно перебрать все x от 1 до 39 и проверить каждое - до тридцати девяти проб, и 23 найдётся.

Прежде чем читать дальше, ответь себе на два вопроса. Что делать, если модуль - не 40, а число из шестисот цифр, и перебор отпадает? И всегда ли такое x вообще существует - например, есть ли x, для которого 6 · x даёт остаток 1 при делении на 9?

На что это похоже

Представь два ведра - на 40 литров и на 7 - и бочку, в которой надо оставить ровно один литр. Воду можно наливать в бочку полными вёдрами и вычерпывать полными вёдрами.

Решение: три раза налить ведром на 40 и семнадцать раз вычерпать ведром на 7. 3 · 40 − 17 · 7 = 120 − 119 = 1. Вёдрами на 6 и на 9 литров один литр не получить никак: что ни наливай и ни вычерпывай, в бочке будет число литров, кратное трём.

Обратный элемент - это ответ на вопрос «сколько раз черпать». А существует он ровно тогда, когда вёдрами можно отмерить единицу.

Механизм: вести коэффициенты вместе с остатками

Обычный Евклид на каждом круге получает новый остаток: r = a − q · b. Каждый остаток, таким образом, собран из исходных чисел сложением и вычитанием. Расширенный алгоритм записывает, как именно: для каждого числа в цепочке он помнит пару (x, y), такую что число равно x · a₀ + y · b₀, где a₀ и b₀ - исходные числа.

Начало известно: a₀ = 1 · a₀ + 0 · b₀, пара (1, 0); b₀ = 0 · a₀ + 1 · b₀, пара (0, 1). Новый остаток равен старому числу минус q раз следующее - и его пара получается так же: старая пара минус q раз следующая.

числа 40 и 7                              каждая строка: число = x · 40 + y · 7

число    q        x      y         проверка
 40               1      0         1 · 40 + 0 · 7
  7      5        0      1         0 · 40 + 1 · 7
  5      1        1     −5         40 − 5 · 7 = 5
  2      2       −1      6         −40 + 6 · 7 = 2
  1      2        3    −17         3 · 40 − 17 · 7 = 1
  0

Столбец q - частное от деления числа строкой выше на число в этой строке. Пара каждой новой строки - пара двумя строками выше минус q из строки выше, умноженное на пару строкой выше: для числа 5 это (1, 0) − 5 · (0, 1) = (1, −5). Последнее ненулевое число - НОД, а его пара - искомые коэффициенты: 3 · 40 − 17 · 7 = 1.

Теперь возьми это равенство по модулю 40. Слагаемое 3 · 40 исчезает, остаётся −17 · 7 ≡ 1. Значит −17 - обратный к 7, и в привычном виде это −17 + 40 = 23. Обратный - коэффициент при том числе, к которому его ищут: в таблице это y, коэффициент при семёрке.

Обратный элемент к a по модулю m - число x от 1 до m − 1, для которого a · x ≡ 1 (mod m). Пишут a⁻¹. Разделить на a по модулю - значит умножить на a⁻¹.

Правило

Для любых целых a и b существуют целые x и y, такие что a · x + b · y = НОД(a, b); расширенный алгоритм Евклида находит их за то же число кругов, что и НОД. Обратный к a по модулю m существует тогда и только тогда, когда НОД(a, m) = 1, и равен коэффициенту при a, приведённому к диапазону от 0 до m − 1. Сравнение a · x ≡ b (mod m) при НОД(a, m) = g имеет решения, только если b делится на g, и тогда решений по модулю m ровно g.

Почему «только когда НОД равен единице». Если a · x ≡ 1 (mod m), то a · x − k · m = 1 для какого-то k. Любой общий делитель a и m делит левую часть, значит делит единицу. Общих делителей, кроме единицы, быть не может.

Разбор: программа и деление

def rasshirennyj(a, b):
    x0 = 1
    y0 = 0
    x1 = 0
    y1 = 1
    while b != 0:
        q = a // b
        r = a - q * b
        a = b
        b = r
        x2 = x0 - q * x1
        x0 = x1
        x1 = x2
        y2 = y0 - q * y1
        y0 = y1
        y1 = y2
    return [a, x0, y0]

def obratnyj(a, m):
    r = rasshirennyj(a, m)
    if r[0] != 1:
        return -1
    return r[1] % m

Пары (x0, y0) и (x1, y1) - коэффициенты для текущих a и b; каждый круг сдвигает их вместе с числами. rasshirennyj(7, 40) возвращает [1, -17, 3] - НОД и коэффициенты при 7 и при 40, в порядке аргументов, - а obratnyj(7, 40) возвращает одно число, 23: остаток в Python приводит −17 к диапазону от 0 до 39.

Ответ на первый вопрос из начала урока: перебор не нужен. obratnyj(123456, 1000003) возвращает 414 894 за 120 шагов тренажёра. Перебор сделал бы до миллиона проб.

Теперь деление. Решим 7 · x ≡ 5 (mod 40). Умножим обе части на обратный к 7: x ≡ 5 · 23 = 115 ≡ 35. Проверка: 7 · 35 = 245 = 6 · 40 + 5. Умножение на обратный сделало то, что в обычной арифметике делает деление на 7.

Разбор: когда обратного нет

rasshirennyj(6, 9) возвращает [3, -1, 1]: НОД равен трём, 6 · (−1) + 9 · 1 = 3. Единицу из шестёрок и девяток не собрать - obratnyj(6, 9) возвращает −1, признак отказа. Это ответ на второй вопрос.

Но сравнение с шестёркой иногда решается. 6 · x ≡ 3 (mod 9): правая часть делится на НОД. Раздели всё на три - и числа, и модуль: 6x − 3 делится на 9 ровно тогда, когда 2x − 1 делится на 3. Получается 2 · x ≡ 1 (mod 3); обратный к 2 по модулю 3 - это 2, откуда x ≡ 2 (mod 3). По модулю 9 это три решения: 2, 5 и 8. Проверка: 12, 30 и 48 дают остаток 3. А у 6 · x ≡ 4 (mod 9) решений нет: слева всегда число, кратное трём, по модулю девять - 0, 3 или 6.

Кто обратим, зависит от модуля:

модуль 7:    a      1  2  3  4  5  6          модуль 12:   a      1  5  7  11
             a⁻¹    1  4  5  2  3  6                       a⁻¹    1  5  7  11
                                              у 2, 3, 4, 6, 8, 9, 10 обратного нет

По модулю 7 обратим каждый ненулевой остаток: семь - простое, и общих делителей с ним ни у кого нет. По модулю 12 обратимы четыре остатка из одиннадцати. Поэтому там, где нужно делить, модуль берут простым: арифметика по простому модулю умеет все четыре действия.

Что ломается без этого

Первое: отрицательный коэффициент. Алгоритм выдаёт −17, а не 23. Без приведения % m это число уходит дальше, и в языке, где остаток от отрицательного отрицателен, ломает следующую формулу.

Второе: обратный, которого нет. Функция, не проверяющая НОД, вернёт для пары (6, 9) число 8 - коэффициент при шестёрке, приведённый по модулю. 6 · 8 = 48 ≡ 3, а не 1. Ошибки нет, ответ есть, ответ неверный.

Третье: деление остатков напрямую. (a / b) mod m нельзя считать как (a mod m) // (b mod m). 10 / 5 = 2, а по модулю 7 остатки 3 и 5, и 3 // 5 = 0. Правильно: 3 · 5⁻¹ = 3 · 3 = 9 ≡ 2.

Четвёртое: знаменатель, кратный модулю. Число сочетаний по модулю p через обратные работает, пока в знаменателе нет множителя p. При n ≥ p он появляется, и формула молча делит на ноль.

Зачем это в работе

В Python обратный встроен: pow(a, -1, m) с версии 3.8; на тренажёре она тоже есть. Если обратного нет, функция завершается ошибкой, а не возвращает мусор.

Ключ RSA. Открытая часть ключа - число e, секретная - d, обратное к e по секретному модулю. Вся генерация секретного ключа - один вызов расширенного Евклида; глава про RSA это покажет.

Комбинаторика по модулю: число сочетаний считают как произведение числителя на обратные к множителям знаменателя. Так решается беда из урока про остатки - «делить по модулю нельзя».

Уравнения в целых числах. «Можно ли набрать сумму 100 монетами по 6 и по 9» - вопрос о том, делится ли 100 на НОД(6, 9) = 3. Не делится - и перебирать незачем.

Теперь сам

1. Найди обратный к 5 по модулю 17 расширенным алгоритмом: заполни таблицу, как в механизме.
2. Есть ли обратный у 4 по модулю 10? У 3 по модулю 10?
3. Реши 3 · x ≡ 2 (mod 7), пользуясь таблицей обратных по модулю 7.
4. Сколько решений по модулю 12 у сравнения 8 · x ≡ 4 (mod 12)?