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

Моноиды

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

Моноид — одна из простейших алгебраических структур: множество с ассоциативной операцией и нейтральным элементом. Моноидами являются строки со склейкой, числа со сложением или умножением, матрицы — и именно моноидная структура объясняет, почему работают кодирование сообщений, быстрое возведение в степень и параллельные вычисления.

Определения

Определение

Моноид — тройка (M, ∘, e): множество M, бинарная операция ∘ : M × M → M и элемент e ∈ M, такие что

  • ассоциативность: (a ∘ b) ∘ c = a ∘ (b ∘ c) для всех a, b, c ∈ M;
  • нейтральный элемент: e ∘ a = a ∘ e = a для всех a ∈ M.
СтруктураТребованияПример
Полугруппаассоциативностьположительные целые числа со сложением (нуля нет)
Моноид+ нейтральный элементстроки со склейкой; (ℕ ∪ {0}, +, 0)
Группа+ обратный к каждому элементу(ℤ, +, 0); битовые векторы с XOR
Коммутативный моноид+ a ∘ b = b ∘ a(ℤₙ, ·, 1); но не строки и не матрицы

Не всякая операция ассоциативна: вычитание — нет, (5 − 3) − 1 ≠ 5 − (3 − 1); возведение в степень — тоже нет, (2^3)^2 = 64, а 2^(3^2) = 512.

Основные свойства

Единственность нейтрального элемента

В моноиде нейтральный элемент единственный.

Доказательство. Если e и e' оба нейтральны, то e = e ∘ e' = e' (первое равенство — потому что e' нейтрален, второе — потому что нейтрален e).

Обобщённая ассоциативность

Значение произведения a_1 ∘ a_2 ∘ … ∘ a_n не зависит от расстановки скобок. Пустое произведение естественно считать равным e.

Поэтому имеет смысл свёртка списка элементов: e ∘ a_1 ∘ a_2 ∘ … ∘ a_n. Скобки можно расставить как удобно — например, разбить список на части, свернуть каждую отдельно (параллельно, на разных компьютерах) и свернуть результаты. На этом устроены MapReduce и параллельные вычисления сумм, произведений и конкатенаций.

Обратимые элементы образуют группу

Элемент a обратим, если существует b с a ∘ b = b ∘ a = e. Обратный элемент единственный, произведение обратимых элементов обратимо: (a ∘ b)⁻¹ = b⁻¹ ∘ a⁻¹.

Например, в моноиде (ℤₙ, ·, 1) обратимы ровно вычеты, взаимно простые с n, — они образуют группу ℤₙ* из φ(n) элементов (см. «Вычеты»). Именно в этой группе работает шифр Эль-Гамаля.

Пять примеров из лаборатории

МоноидОперацияНейтральныйКоммутативенГруппа
Строки над алфавитомсклейкапустая строканетнет
Целые неотрицательные числа+0данет (нет −1)
ℤₙумножение mod n1данет (0 необратим)
Битовые векторы длины kXOR00…0дада: a⁻¹ = a
Матрицы 2×2умножениеEнетнет (вырожденные)

Гомоморфизмы и кодирование

Определение

Отображение h : M → N между моноидами — гомоморфизм, если h(a ∘ b) = h(a) ∘ h(b) и h(e_M) = e_N.

  • Длина строки — гомоморфизм из моноида строк в (ℕ ∪ {0}, +, 0): |uv| = |u| + |v|.
  • Кодирование сообщения посимвольным кодом (Хаффмана, Шеннона–Фано) — гомоморфизм моноида строк над алфавитом сообщения в моноид двоичных строк: код склейки — склейка кодов. Однозначная декодируемость означает, что этот гомоморфизм инъективен, а префиксные коды — удобный способ это гарантировать.
  • Возведение в степень по модулю k ↦ g^k mod p — гомоморфизм из (ℤ, +) в (ℤₚ*, ·): g^(k+l) = g^k·g^l. Обращение этого гомоморфизма — задача дискретного логарифма.

Быстрое возведение в степень в любом моноиде

Степень a^n = a ∘ a ∘ … ∘ a по ассоциативности можно вычислять «удвоением»: a^(2m) = a^m ∘ a^m, a^(2m+1) = a^(2m) ∘ a. Нужно O(log n) операций вместо n − 1. Один и тот же алгоритм работает для чисел по модулю (RSA, Эль-Гамаль), для матриц и для строк.

Пример: числа Фибоначчи
[[1, 1], [1, 0]]^n = [[F_(n+1), F_n], [F_n, F_(n−1)]]

Поэтому F_n вычисляется за O(log n) умножений матриц 2×2.

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

Введите элементы через запятую — лаборатория свернёт их в выбранном моноиде, проверит аксиомы на этих элементах и для ℤₙ построит таблицу Кэли. Открыть моноиды →

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

  1. Является ли множество чётных чисел с умножением моноидом?
    ОтветНет: операция ассоциативна и замкнута (полугруппа), но 1 — нейтральный элемент — не чётное.
  2. Какие элементы обратимы в (ℤ_12, ·, 1)?
    Ответ1, 5, 7, 11 — взаимно простые с 12; каждый из них обратен сам себе.
  3. Докажите, что операция a ∘ b = max(a, b) на неотрицательных числах задаёт моноид.
    Ответmax(max(a, b), c) = max(a, max(b, c)) — наибольшее из трёх; нейтральный элемент — 0.