Криптография и теория информации

Сравнения по модулю

Алгебра и теория чисел Открыть в лаборатории →

Сравнения по модулю — «арифметика остатков», придуманная Гауссом (1801). Вся асимметричная криптография — RSA, Диффи–Хеллман, Эль-Гамаль — это вычисления в остатках: быстрое возведение в степень, теоремы Ферма и Эйлера, китайская теорема об остатках.

Определение и свойства

Определение

Целые a и b сравнимы по модулю m > 0, если m | (a − b), то есть они дают одинаковые остатки при делении на m. Записывают a ≡ b (mod m).

Сравнение — отношение эквивалентности, и с ним можно обращаться почти как с равенством. Если a ≡ b и c ≡ d (mod m), то

  • a + c ≡ b + d, a − c ≡ b − d, ac ≡ bd (mod m);
  • a^k ≡ b^k (mod m) для любого натурального k.

Доказательство для умножения: ac − bd = a(c − d) + d(a − b) — сумма кратных m.

Делить можно не всегда

2·3 ≡ 2·8 (mod 10), но 3 ≢ 8 (mod 10). Сокращать на c можно, только если НОД(c, m) = 1 — тогда у c есть обратный элемент по модулю m.

Быстрое возведение в степень

Чтобы вычислить a^k mod m, не нужно k − 1 умножение. Запишем k в двоичной системе, будем последовательно возводить a в квадрат (a, a^2, a^4, a^8, … по модулю m) и перемножать те квадраты, которым соответствуют единицы. Получается не больше 2·log₂ k умножений, а промежуточные числа не превышают m².

Пример: 3^13 mod 7

13 = 1101₂ = 8 + 4 + 1. Квадраты: 3^1 = 3, 3^2 = 9 ≡ 2, 3^4 ≡ 2^2 = 4, 3^8 ≡ 4^2 = 16 ≡ 2. Итого 3^13 ≡ 3^8·3^4·3^1 ≡ 2·4·3 = 24 ≡ 3 (mod 7).

Для 2048-битного показателя — около 4000 умножений вместо 2^2048. Без этого алгоритма RSA и Эль-Гамаль были бы невозможны.

Теоремы Ферма и Эйлера

Теорема Эйлера

Если НОД(a, m) = 1, то

a^φ(m) ≡ 1 (mod m),

где φ(m) — функция Эйлера. Частный случай для простого m = p — малая теорема Ферма: a^(p−1) ≡ 1 (mod p) при p ∤ a.

Доказательство. Пусть r_1, …, r_φ — приведённая система вычетов по модулю m. Числа a·r_1, …, a·r_φ тоже взаимно просты с m и попарно несравнимы (на a можно сокращать), то есть это та же система в другом порядке. Перемножив, получаем a^φ·∏r_i ≡ ∏r_i, и после сокращения на обратимое ∏r_i — a^φ ≡ 1.

Следствие — понижение показателя: a^k ≡ a^(k mod φ(m)) (mod m). Например, 3^100 mod 7: φ(7) = 6, 100 mod 6 = 4, 3^4 = 81 ≡ 4. Отсюда же — корректность RSA: (M^e)^d = M^(1 + kφ(n)) ≡ M (mod n).

Китайская теорема об остатках

Теорема

Если модули m_1, …, m_k попарно взаимно просты, система x ≡ a_i (mod m_i) имеет единственное решение по модулю M = m_1·…·m_k:

x = Σ a_i·M_i·y_i mod M, M_i = M/m_i, y_i = M_i⁻¹ mod m_i

Слагаемое a_i·M_i·y_i сравнимо с a_i по модулю m_i и с нулём по всем остальным модулям — поэтому сумма удовлетворяет всем сравнениям сразу. Единственность: разность двух решений делится на все m_i, а значит, и на M.

Задача Сунь-цзы (III–V век)

Число при делении на 3 даёт остаток 2, на 5 — 3, на 7 — 2. M = 105; M_1 = 35, 35⁻¹ ≡ 2⁻¹ ≡ 2 (mod 3); M_2 = 21, 21⁻¹ ≡ 1 (mod 5); M_3 = 15, 15⁻¹ ≡ 1 (mod 7). x = 2·35·2 + 3·21·1 + 2·15·1 = 233 ≡ 23 (mod 105).

Китайская теорема позволяет заменить вычисления с огромным модулем несколькими вычислениями с маленькими. Так ускоряют расшифрование RSA (примерно в 4 раза) — вычисляя степень отдельно по модулям p и q.

Квадратичные сравнения

Число a, не делящееся на простое нечётное p, называется квадратичным вычетом, если сравнение x² ≡ a (mod p) разрешимо, и невычетом — иначе. Вычетов и невычетов поровну — по (p − 1)/2.

Критерий Эйлера
a^((p−1)/2) ≡ 1 (mod p) ⇔ a — квадратичный вычет; ≡ −1 ⇔ невычет

Если p ≡ 3 (mod 4), корень находится явно: x = ±a^((p+1)/4) mod p. Действительно, x² = a^((p+1)/2) = a·a^((p−1)/2) ≡ a. Пример: x² ≡ 2 (mod 7): 2^3 = 8 ≡ 1 — вычет, x = 2^2 = 4, корни 4 и 3.

Признаки делимости

Признаки делимости — следствия сравнений для степеней 10. Так как 10 ≡ 1 (mod 9), число сравнимо с суммой своих цифр по модулю 9 (и 3). Так как 10 ≡ −1 (mod 11), число сравнимо со знакочередующейся суммой цифр по модулю 11. Для любого делителя m остаток числа равен сумме цифр, умноженных на остатки 10^i mod m.

В лаборатории

Пять примеров: быстрое a^k mod m, теоремы Эйлера и Ферма, китайская теорема, квадратичные сравнения и признаки делимости. Открыть →

Вопросы для самопроверки

  1. Найдите последнюю цифру числа 7^222.
    ОтветЭто 7^222 mod 10; φ(10) = 4, 222 mod 4 = 2, 7^2 = 49 — последняя цифра 9.
  2. Решите систему x ≡ 1 (mod 4), x ≡ 2 (mod 9).
    Ответx ≡ 29 (mod 36): 29 = 7·4 + 1 = 3·9 + 2.
  3. Является ли 3 квадратичным вычетом по модулю 11?
    Ответ3^5 = 243 = 22·11 + 1 ≡ 1 — да; корни ±3^3 = ±27 ≡ ±5: 5^2 = 25 ≡ 3.