Математика для программиста Абстрактная алгебра: группы, кольца, поля и моноиды в коде
0%

Абстрактная алгебра: группы, кольца, поля и моноиды в коде

28 мин 5893 слов
#математика#абстрактная алгебра#группы#конечные поля#моноиды

Абстрактная алгебра: группы, кольца, поля и моноиды в коде

Абстрактная алгебра — единственный раздел математики, который программист использует каждый день, даже не зная его названия. Когда вы пишете reduce, вы пользуетесь моноидом. Когда СУБД выполняет SUM(...) в восемь потоков и склеивает частичные суммы — она полагается на ассоциативность. Когда AES шифрует байт — он умножает элементы конечного поля из 256 элементов. Когда Ceph восстанавливает данные с трёх выживших дисков из пяти — он решает линейную систему над GF(256).

Идея абстрактной алгебры радикально простая: вместо того чтобы изучать конкретные объекты, мы изучаем правила, которым подчиняются операции над ними. Доказали теорему про «любое множество с ассоциативной операцией и нейтральным элементом» — и она мгновенно верна для чисел, строк, списков, множеств, матриц, функций, git-коммитов, счётчиков в распределённой системе и планов запроса. Это не эстетика: это переиспользование доказательств вместо переиспользования кода.

Эта статья опирается на Теорию множеств (что такое множество и функция) и на Логику и доказательства (как читать «для любого a существует b»). Знание линейной алгебры не обязательно, но полезно — векторное пространство определяется именно над полем.

Зачем это программисту: четыре сцены

Сцена 1. Ваш reduce даёт разные ответы. Тесты падают раз в двадцать прогонов. Причина — операция комбинирования не ассоциативна (классика: усреднение, вычитание, сложение float). При однопоточном проходе порядок фиксирован, при параллельном — нет. Алгебра ровно про это: «какие законы должна выполнять операция, чтобы порядок не влиял».

Сцена 2. Инкрементальные вычисления. Хочется пересчитывать агрегат при добавлении события, не пробегая всю историю. Это возможно ровно тогда, когда агрегат — моноид: f(данные + новое) = f(данные) * f(новое). Не моноид — придётся хранить всю историю (или сдаться и считать приблизительно).

Сцена 3. Криптография. Diffie–Hellman, RSA, ECDSA, AES — всё это заявления о группах и полях. Без языка «порядок элемента», «циклическая группа», «конечное поле» криптографию невозможно даже прочитать, не то что оценить корректность реализации.

Сцена 4. Конфликты в распределённой системе. Два узла независимо изменили состояние. Слияние без координации возможно тогда, когда операция слияния коммутативна, ассоциативна и идемпотентна — это полурешётка, и на ней стоят все CRDT.

Каждая сцена — про один и тот же вопрос: какие законы выполняет моя операция. Начнём строить лестницу законов снизу.

Лестница структур: одно множество, одна операция

Определение (бинарная операция). Бинарная операция на множестве S — это функция *: S × S -> S. Ключевое требование уже здесь: результат обязан лежать в S (замкнутость). деление не является бинарной операцией на Z (2/3 не целое), а вычитание — является.

Дальше добавляем аксиомы по одной:

Замкнутость:        для всех a, b из S:  a * b лежит в S
Ассоциативность:    (a * b) * c = a * (b * c)
Нейтральный (e):    e * a = a * e = a
Обратный:           для каждого a есть a' с  a * a' = a' * a = e
Коммутативность:    a * b = b * a

Названия структур получаются накоплением этих аксиом:

Структура Замкн. Ассоц. Нейтр. Обрат. Комм. Пример
Магма + (Z, -) — вычитание
Полугруппа + + непустые строки с ++; (Z, max)
Моноид + + + строки с ++ и ""; (N, +, 0)
Группа + + + + S_n (перестановки), GL(n, R)
Абелева группа + + + + + (Z, +, 0), (Z/n, +, 0)

Вложенная иерархия алгебраических структур

Правило чтения картинки: чем сильнее аксиомы, тем больше теорем достаётся бесплатно, но тем меньше объектов подходит. Это тот же trade-off, что между Iterable и RandomAccess в коде: узкий интерфейс — много реализаций и мало гарантий.

Моноид: самая полезная структура для инженера

Определение. Моноид — это тройка (M, *, e), где *: M × M -> M ассоциативна и e — нейтральный элемент: e * a = a * e = a для всех a.

Интуиция «на пальцах»: моноид — это всё, что можно склеивать в любом порядке скобок, и есть «пустышка», которая ничего не меняет. Строки и пустая строка. Списки и пустой список. Числа и ноль. Множества и пустое множество. Функции A -> A и identity. Матрицы n×n и единичная матрица.

Ассоциативность — это разрешение на параллелизм

Ассоциативность означает, что выражение a1 * a2 * ... * an имеет единственное значение независимо от расстановки скобок (строгое доказательство — индукцией по n, обобщённый закон ассоциативности). Практический вывод:

последовательно:  ((((a1*a2)*a3)*a4)*a5)   — O(n) шагов, глубина n
деревом:          ((a1*a2)*(a3*a4))*a5     — O(n) работы, глубина log n

Работа та же, а глубина падает с n до log n — значит, свёртку можно разложить по потокам, ядрам GPU или узлам кластера. Именно это делает reduce в MapReduce/Spark, std::reduce в C++17 (в отличие от std::accumulate, который обязан идти слева направо) и параллельная агрегация в PostgreSQL.

Обратите внимание: для параллельной свёртки достаточно ассоциативности, коммутативность не нужна — порядок элементов сохраняется, меняется только группировка. Коммутативность нужна отдельно, когда порядок прихода данных не гарантирован (объединение результатов от узлов, которые ответили в произвольном порядке).

from functools import reduce
from concurrent.futures import ThreadPoolExecutor
from typing import Callable, TypeVar, Iterable

T = TypeVar("T")

def fold(op: Callable[[T, T], T], unit: T, xs: Iterable[T]) -> T:
    """Последовательная свёртка моноида: O(n) времени, O(1) доп. памяти."""
    return reduce(op, xs, unit)

def par_fold(op: Callable[[T, T], T], unit: T, xs: list[T], workers: int = 4) -> T:
    """Параллельная свёртка. Корректна ТОЛЬКО если op ассоциативна.
    Время: O(n/p + log p), доп. память: O(p)."""
    if not xs:
        return unit
    chunk = max(1, len(xs) // workers)
    parts = [xs[i:i + chunk] for i in range(0, len(xs), chunk)]
    with ThreadPoolExecutor(workers) as pool:
        partial = list(pool.map(lambda p: fold(op, unit, p), parts))
    return fold(op, unit, partial)  # склейка частичных результатов

# Моноид (str, +, "") — ассоциативен, но НЕ коммутативен: порядок частей важен.
data = [f"[{i}]" for i in range(12)]
assert fold(str.__add__, "", data) == par_fold(str.__add__, "", data)

# (int, +, 0) — коммутативный моноид
assert par_fold(int.__add__, 0, list(range(1000))) == 499500

Составные моноиды: то, ради чего всё затевалось

Моноиды композируются, и это главный практический приём: если A и B — моноиды, то A × B — моноид покомпонентно. Значит, сложные агрегаты собираются из простых без доказательств заново.

Классический пример — среднее. «Среднее» само по себе не моноид (нельзя усреднить два средних, не зная весов), но пара (сумма, количество) — моноид, а среднее берётся в самом конце.

from dataclasses import dataclass

@dataclass(frozen=True)
class Stats:
    """Моноид статистики: покомпонентная композиция четырёх моноидов —
    (+,0), (+,0), (min,+inf), (max,-inf)."""
    count: int = 0
    total: float = 0.0
    lo: float = float("inf")
    hi: float = float("-inf")

    @staticmethod
    def unit() -> "Stats":
        return Stats()

    @staticmethod
    def of(x: float) -> "Stats":
        return Stats(1, x, x, x)

    def __mul__(self, other: "Stats") -> "Stats":
        return Stats(
            self.count + other.count,
            self.total + other.total,
            min(self.lo, other.lo),
            max(self.hi, other.hi),
        )

    @property
    def mean(self) -> float:
        return self.total / self.count if self.count else float("nan")

xs = [3.0, 1.0, 4.0, 1.0, 5.0, 9.0, 2.0, 6.0]
s = fold(Stats.__mul__, Stats.unit(), [Stats.of(x) for x in xs])
print(s.count, s.total, s.lo, s.hi, round(s.mean, 3))  # 8 31.0 1.0 9.0 3.875

Тот же приём в проде: HyperLogLog (моноид по объединению регистров), Count-Min Sketch (моноид по сложению матриц), t-digest, гистограммы Prometheus, bloom filter (моноид по побитовому ИЛИ). Все они популярны именно потому, что моноиды: их можно считать на шардах и сливать без пересчёта.

Как это выражается в системе типов

В Haskell это Semigroup/Monoid из base (see Data.Monoid), в Scala — cats.Monoid (документация Typelevel Cats), в TypeScript — fp-ts. В языках без тайпклассов (Go, C#, Python) моноид живёт как соглашение: интерфейс с Combine и Empty плюс property-based тесты на законы. Подробнее о том, как эти интерфейсы устроены категорно, — в статье Теория категорий в программировании.

Законы нужно тестировать, а не декларировать. Компилятор не проверит ассоциативность:

from hypothesis import given, strategies as st

@given(st.text(), st.text(), st.text())
def test_string_monoid_assoc(a, b, c):
    assert (a + b) + c == a + (b + c)

@given(st.text())
def test_string_monoid_identity(a):
    assert "" + a == a and a + "" == a

@given(st.floats(allow_nan=False, allow_infinity=False),
       st.floats(allow_nan=False, allow_infinity=False),
       st.floats(allow_nan=False, allow_infinity=False))
def test_float_add_is_not_associative(a, b, c):
    # Этот тест ПАДАЕТ — и это правильно: float-сложение не ассоциативно.
    assert (a + b) + c == a + (b + c)

Последний тест — не педантизм. (1e16 + 1.0) - 1e16 = 0.0, а 1e16 + (1.0 - 1e16) = 1.0. Подробный разбор — в статье Численные методы; практический вывод: параллельная сумма float даёт другой (часто более точный!) ответ, и требовать побитового совпадения с однопоточной версией нельзя.

Группа: моноид, в котором всё обратимо

Определение. Группа — это моноид (G, *, e), в котором у каждого a есть обратный a': a * a' = a' * a = e. Если дополнительно a * b = b * a — группа абелева (коммутативная).

Интуиция: группа — это множество обратимых преобразований. Повороты кубика Рубика, перестановки списка, сдвиги по модулю, обратимые матрицы, симметрии молекулы, undo/redo-операции. Ключевое слово — «можно откатить».

Что следует сразу из аксиом (и это надо уметь выводить руками)

Единственность нейтрального. Пусть e и f — оба нейтральные. Тогда e = e * f (потому что f нейтральный) = f (потому что e нейтральный). Значит e = f.

Единственность обратного. Пусть b и c — оба обратные к a. Тогда:

b = b * e = b * (a * c) = (b * a) * c = e * c = c

Обратите внимание: ассоциативность использована в третьем переходе и без неё доказательство рушится. Именно поэтому «обратный элемент» осмысленен только начиная с полугруппы.

Закон сокращения. Из a * x = a * y следует x = y (домножьте слева на a'). Следствие: в таблице Кэли конечной группы каждый элемент встречается в каждой строке и каждом столбце ровно один раз — это латинский квадрат. Полезный тест на реализацию.

(a * b)' = b' * a' — обратный к композиции переворачивает порядок. Ровно поэтому в графике (R · T)^{-1} = T^{-1} · R^{-1}, а не наоборот.

Некоммутативность — не экзотика, а норма

Самая частая ошибка новичка — считать, что группы «как числа». Большинство интересных групп неабелевы. Канонический пример — D4, группа симметрий квадрата: 4 поворота и 4 отражения, всего 8 элементов.

Некоммутативность в группе симметрий квадрата D4

Отражение, затем поворот — не то же самое, что поворот, затем отражение. То же самое верно для матриц, для кватернионов вращения, для последовательности миграций БД и для порядка middleware в HTTP-пайплайне. Некоммутативность — причина, по которой «поменять две строчки местами» в 3D-коде ломает сцену.

Симметрическая группа руками

S_n — группа всех биекций множества {0..n-1} относительно композиции. |S_n| = n!. Любая конечная группа вкладывается в некоторый S_n (теорема Кэли) — то есть группы это и есть симметрии, других не бывает.

from itertools import permutations

def compose(p, q):
    """(p ∘ q)(i) = p(q(i)) — сначала q, потом p."""
    return tuple(p[q[i]] for i in range(len(q)))

def inverse(p):
    inv = [0] * len(p)
    for i, v in enumerate(p):
        inv[v] = i
    return tuple(inv)

n = 3
e = tuple(range(n))
S3 = list(permutations(range(n)))

# Проверяем аксиомы группы перебором: O(|G|^3) для ассоциативности.
assert all(compose(a, e) == a == compose(e, a) for a in S3)
assert all(compose(a, inverse(a)) == e for a in S3)
assert all(compose(compose(a, b), c) == compose(a, compose(b, c))
           for a in S3 for b in S3 for c in S3)

# Неабелева: находим контрпример
bad = [(a, b) for a in S3 for b in S3 if compose(a, b) != compose(b, a)]
print(len(S3), "элементов,", len(bad), "некоммутирующих пар")  # 6 элементов, 18 пар

Порядок элемента, циклические группы и теорема Лагранжа

Определение (порядок элемента). Порядок a — наименьшее k > 0 с a^k = e (в конечной группе всегда существует). Порядок группы — это |G|.

Определение (подгруппа). H ⊆ G — подгруппа, если H сама группа относительно той же операции (замкнута, содержит e, замкнута относительно обратных).

Теорема Лагранжа. Если G конечна и H — подгруппа, то |H| делит |G|.

Идея доказательства: смежные классы aH = {a*h : h из H} разбивают G на непересекающиеся куски одинакового размера |H|. Значит |G| = [G:H] · |H|.

Следствия, которые буквально работают в криптографии:

1. Порядок любого элемента делит |G|.
2. a^|G| = e для любого a из G.
3. (Эйлер)  a^φ(n) ≡ 1 (mod n),  если gcd(a, n) = 1        — здесь G = U(n), |G| = φ(n)
4. (Ферма)  a^(p-1) ≡ 1 (mod p), если p простое, p не делит a
5. Группа простого порядка обязательно циклическая и не имеет нетривиальных подгрупп.

Пункт 3 — это ровно то, на чём стоит корректность RSA: расшифровка возвращает исходное сообщение, потому что m^(ed) = m^(1 + k·φ(n)) = m · (m^φ(n))^k = m.

from math import gcd
from sympy import totient  # или считайте φ вручную

def order(a: int, n: int) -> int:
    """Порядок a в мультипликативной группе U(n). Требует gcd(a, n) = 1."""
    assert gcd(a, n) == 1
    x, k = a % n, 1
    while x != 1:
        x, k = x * a % n, k + 1
    return k

U12 = [a for a in range(12) if gcd(a, 12) == 1]
print(U12)                              # [1, 5, 7, 11] — φ(12) = 4
print({a: order(a, 12) for a in U12})   # {1: 1, 5: 2, 7: 2, 11: 2}

Разберём этот вывод, он поучителен. U(12) — абелева группа из 4 элементов, но не циклическая: ни один элемент не имеет порядка 4, все нетривиальные элементы имеют порядок 2. Это группа Клейна Z/2 × Z/2. А вот U(7):

print({a: order(a, 7) for a in range(1, 7)})
# {1: 1, 2: 3, 3: 6, 4: 3, 5: 6, 6: 2}

Здесь есть элементы порядка 6 = |U(7)|: тройка и пятёрка — образующие, U(7) циклическая. Общий факт: U(p) циклична для любого простого p, и её образующая называется первообразным корнем. Именно первообразный корень выбирают параметром g в Diffie–Hellman.

Заметьте, что все порядки в обоих примерах делят порядок группы (4 и 6 соответственно) — Лагранж в действии.

Быстрое возведение в степень работает в любом моноиде (обратные не нужны) за O(log k) операций:

def monoid_pow(op, unit, a, k: int):
    """a^k в любом моноиде за O(log k) операций. Время O(log k), память O(1)."""
    result, base = unit, a
    while k > 0:
        if k & 1:
            result = op(result, base)
        base = op(base, base)
        k >>= 1
    return result

# работает и для чисел по модулю, и для матриц (Фибоначчи за O(log n)),
# и для перестановок, и для конкатенации строк
mat_mul = lambda A, B: tuple(tuple(sum(A[i][k]*B[k][j] for k in range(2)) for j in range(2)) for i in range(2))
I2 = ((1, 0), (0, 1))
F = ((1, 1), (1, 0))
print(monoid_pow(mat_mul, I2, F, 10)[0][1])  # 55 = F(10)

Это один из самых доходных практических выводов всей статьи: любой алгоритм «применить операцию k раз» ускоряется до O(log k), если операция ассоциативна. Матричные степени, степени в кольце вычетов, транзитивное замыкание, линейные рекурренты.

Гомоморфизмы: структурно-совместимые отображения

Определение. Отображение f: G -> H между группами — гомоморфизм, если f(a * b) = f(a) · f(b) для всех a, b. Биективный гомоморфизм — изоморфизм (структуры «одинаковы с точностью до переименования»).

Интуиция: гомоморфизм — это «сжатие с сохранением структуры», ровно то, что делает хорошая хеш-функция или проекция. Примеры:

exp: (R, +, 0) -> (R>0, ×, 1),      exp(a+b) = exp(a)·exp(b)      — изоморфизм
det: (GL(n,R), ×) -> (R\{0}, ×),    det(AB) = det(A)·det(B)
mod: (Z, +) -> (Z/n, +),            (a+b) mod n = (a mod n + b mod n) mod n
len: (списки, ++) -> (N, +),        len(xs ++ ys) = len(xs) + len(ys)   — моноидный гомоморфизм

Последний пример — практический шаблон: если ваша агрегация является гомоморфизмом моноидов, её можно считать инкрементально и распределённо. len, sum, count, max, bloom-фильтр от объединения множеств — гомоморфизмы. median — нет, поэтому все распределённые перцентили приближённые.

Ядро. ker f = {a из G : f(a) = e_H}. Ядро всегда нормальная подгруппа, и f инъективен тогда и только тогда, когда ker f = {e}. Для хеш-функции ядро — это множество сообщений, хешируемых в ноль; для линейного отображения — нуль-пространство (см. матрицы и линейные отображения).

Фактор-группа. G / ker f изоморфна образу f — первая теорема об изоморфизме. Конкретно: Z / nZ ≅ Z/n. Вся модульная арифметика — это фактор-группа целых чисел по подгруппе кратных n. Когда вы пишете hash % buckets, вы буквально работаете в фактор-группе.

Как проверить, что ваша структура — то, чем вы её считаете

Кольца: когда операций две

Определение. Кольцо (R, +, ×, 0, 1) — это множество, где:

(R, +, 0)   — абелева группа        (есть вычитание)
(R, ×, 1)   — моноид                (умножение ассоциативно, есть единица)
дистрибутивность:  a×(b+c) = a×b + a×c   и   (b+c)×a = b×a + c×a

Умножение не обязано быть коммутативным и не обязано быть обратимым. Примеры:

  • Z — коммутативное кольцо; обратимы только 1 и -1.
  • Z/n — кольцо вычетов; конечное, и в нём начинаются странности.
  • R[x] — многочлены; основа CRC, кодов Рида–Соломона, полиномиальных коммитментов.
  • Матрицы n×n — некоммутативное кольцо; есть делители нуля.
  • Функции X -> R с поточечными операциями.

Делители нуля. В Z/12: 3 × 4 = 12 = 0, хотя ни 3, ни 4 не нули. Такие элементы — делители нуля, и они ломают привычную логику: из a×b = 0 больше не следует a = 0 или b = 0; из a×x = a×y не следует x = y. Кольцо без делителей нуля называется областью целостности.

Практическое следствие: переполнение int32 — это арифметика в Z/2^32, кольце с чудовищным количеством делителей нуля. Поэтому x * 2 == y * 2 вовсе не означает x == y для 32-битных чисел, а компиляторы законно оптимизируют знаковое переполнение как UB, потому что для знаковых типов стандарт C/C++ не обещает арифметику кольца вычетов вовсе.

# Кольцо Z/12: находим все делители нуля
n = 12
zd = [a for a in range(1, n) if any(a * b % n == 0 for b in range(1, n))]
print(zd)  # [2, 3, 4, 6, 8, 9, 10] — обратимы только 1, 5, 7, 11

Поля: кольца, где можно делить

Определение. Поле — коммутативное кольцо, в котором 0 ≠ 1 и каждый ненулевой элемент обратим по умножению. Эквивалентно: (F, +, 0) — абелева группа, (F \ {0}, ×, 1) — абелева группа, плюс дистрибутивность.

Примеры полей: Q, R, C, F_p = Z/p для простого p, GF(p^k) — конечные поля. Не поля: Z (нет обратных), Z/4, матрицы, кватернионы (умножение некоммутативно — это тело, а не поле).

Теорема. Z/n — поле тогда и только тогда, когда n простое.

Разбор в обе стороны, это ровно тот случай, где доказательство короче интуиции:

  • Если n = a·b составное (1 < a, b < n): тогда a·b ≡ 0, значит a — делитель нуля. Если бы у a был обратный a', то b = (a'·a)·b = a'·(a·b) = a'·0 = 0 — противоречие. Значит a необратим, и поля нет.
  • Если p простое и a ≢ 0: тогда gcd(a, p) = 1, и по соотношению Безу существуют u, v с u·a + v·p = 1, то есть u·a ≡ 1 (mod p). Обратный найден, причём конструктивно — расширенным алгоритмом Евклида за O(log p).
def egcd(a: int, b: int) -> tuple[int, int, int]:
    """Расширенный Евклид: возвращает (g, u, v) с u*a + v*b = g = gcd(a,b).
    Время O(log min(a,b)), память O(1)."""
    old_r, r = a, b
    old_u, u = 1, 0
    old_v, v = 0, 1
    while r != 0:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_u, u = u, old_u - q * u
        old_v, v = v, old_v - q * v
    return old_r, old_u, old_v

def inv_mod(a: int, m: int) -> int:
    g, u, _ = egcd(a % m, m)
    if g != 1:
        raise ValueError(f"{a} необратим по модулю {m}")
    return u % m

print(inv_mod(3, 7))     # 5, потому что 3*5 = 15 ≡ 1 (mod 7)
print([inv_mod(a, 7) for a in range(1, 7)])  # [1, 4, 5, 2, 3, 6]
# inv_mod(3, 12) -> ValueError: 3 необратим по модулю 12

Конечные поля GF(p^k) и почему AES считает по модулю многочлена

Конечное поле существует ровно для порядков p^k (p простое) и единственно с точностью до изоморфизма — фундаментальный факт, доказанный Галуа. При k > 1 это не Z/(p^k) (там есть делители нуля), а кольцо многочленов над F_p, факторизованное по неприводимому многочлену степени k.

GF(2^8) — 256 элементов, каждый байт. Элемент 0x57 — это многочлен x^6 + x^4 + x^2 + x + 1 (единичные биты = коэффициенты). Сложение — XOR (потому что коэффициенты по модулю 2). Умножение — умножение многочленов с приведением по модулю неприводимого многочлена AES:

m(x) = x^8 + x^4 + x^3 + x + 1   =   0x11B

def gf_mul(a: int, b: int) -> int:
    """Умножение в GF(2^8) поля AES (Rijndael), модуль 0x11B.
    Метод «русского крестьянина»: O(8) операций, без таблиц."""
    p = 0
    for _ in range(8):
        if b & 1:
            p ^= a                 # сложение в поле = XOR
        carry = a & 0x80
        a = (a << 1) & 0xFF        # умножение на x
        if carry:
            a ^= 0x1B              # приведение по m(x); старший бит уже отброшен
        b >>= 1
    return p

assert gf_mul(0x57, 0x83) == 0xC1   # канонический пример из FIPS-197
assert gf_mul(0x57, 0x13) == 0xFE

# Проверим аксиомы поля перебором — 256 элементов, это дёшево
assert all(gf_mul(a, 1) == a for a in range(256))
assert all(gf_mul(a, b) == gf_mul(b, a) for a in range(256) for b in range(256))
# каждый ненулевой элемент обратим:
inv = {a: next(b for b in range(1, 256) if gf_mul(a, b) == 1) for a in range(1, 256)}
assert len(inv) == 255
print(hex(inv[0x53]))  # 0xca

Зачем AES это нужно: MixColumns — умножение вектора байт на фиксированную матрицу над GF(2^8), а S-box строится как взятие мультипликативного обратного в GF(2^8) с последующим аффинным преобразованием. Обратимость шифра держится ровно на том, что это поле и что матрица над ним обратима. Спецификация: NIST FIPS 197, раздел 4.

Рид–Соломон и erasure-кодирование: поле как страховка от потери диска

Над полем работает линейная алгебра: матрицы обратимы, системы решаются, любые k линейно независимых уравнений однозначно определяют k неизвестных. Отсюда — коды Рида–Соломона.

Идея: k блоков данных считаем коэффициентами многочлена степени k-1 над GF(256); вычисляем его в n > k различных точках; храним n значений на n дисках. Любые k значений задают систему с матрицей Вандермонда, которая над полем всегда обратима (различные узлы ⇒ ненулевой определитель) — значит, n - k дисков могут умереть, и данные восстановимы.

RS(10, 4): 10 блоков данных + 4 блока чётности = 14 дисков.
Переживает потерю ЛЮБЫХ 4 дисков. Накладные расходы 40% вместо 200% у трёхкратной репликации.

Так устроены erasure-профили в Ceph, HDFS EC, Backblaze Vaults, QR-коды и CD/DVD. Отличный разбор с кодом — пост Backblaze про Reed-Solomon; теория — Lidl & Niederreiter, «Introduction to Finite Fields and Their Applications».

CRC — это остаток в кольце многочленов

CRC32 не «хеш» в криптографическом смысле, а сообщение(x) mod g(x) в F_2[x]. Отсюда все его свойства: линейность (CRC(a XOR b) = CRC(a) XOR CRC(b)), гарантированное обнаружение любой одиночной серии ошибок длиной меньше степени g, и — критично — полная непригодность как MAC: зная CRC, атакующий вычисляет изменение данных, оставляющее CRC прежним, решая линейное уравнение. Это ровно та ошибка, которая убила WEP.

Полукольца: кольца без вычитания, и почему они везде в алгоритмах

Определение. Полукольцо — как кольцо, но (R, +, 0) только коммутативный моноид (вычитания нет). Формально: (R, +, 0) — коммутативный моноид, (R, ×, 1) — моноид, умножение дистрибутивно, и 0 × a = a × 0 = 0.

Звучит как ослабление ради ослабления — но именно это открывает потрясающий трюк: один алгоритм, много семантик.

Полукольцо «+» «×» 0 1 Что считает произведение матриц
Обычное + · 0 1 число путей длины k
Булево или и false true достижимость (транзитивное замыкание)
Тропическое (min-plus) min + +inf 0 кратчайший путь
Max-plus max + -inf 0 критический путь / longest path
Viterbi (max-prod) max · 0 1 наиболее вероятная последовательность
Log-semiring logaddexp + -inf 0 суммирование вероятностей в лог-шкале

Флойд–Уоршелл — это в точности возведение матрицы смежности в степень n в тропическом полукольце; алгоритм Уоршелла для транзитивного замыкания — то же самое в булевом. Одна реализация, разные типы:

import numpy as np

def semiring_matmul(A, B, plus, times, zero):
    """«Умножение» матриц над произвольным полукольцом. O(n^3) времени, O(n^2) памяти."""
    n, m, p = len(A), len(B), len(B[0])
    C = [[zero] * p for _ in range(n)]
    for i in range(n):
        for j in range(p):
            acc = zero
            for k in range(m):
                acc = plus(acc, times(A[i][k], B[k][j]))
            C[i][j] = acc
    return C

INF = float("inf")
W = [[0, 3, INF, 7],
     [8, 0, 2, INF],
     [5, INF, 0, 1],
     [2, INF, INF, 0]]

# Тропическое полукольцо: (min, +). W^n = матрица кратчайших расстояний.
D = W
for _ in range(2):  # достаточно log2(n) возведений в квадрат
    D = semiring_matmul(D, D, min, lambda a, b: a + b, INF)
print(D[0])  # [0, 3, 5, 6] — кратчайшие пути из вершины 0

Подробнее про графовые алгоритмы — в статье Теория графов. На той же идее построен стандарт GraphBLAS (графовые алгоритмы как разреженная линейная алгебра над полукольцами) и оптимизаторы запросов, которые считают агрегаты в полукольцевой семантике.

Ещё одно место, где полукольца буквально в проде: анализ потоков данных в компиляторах. Решётка значений + монотонные передаточные функции + операция встречи (meet) — это ограниченная полурешётка, и завершаемость итеративного алгоритма доказывается через конечность высоты решётки. См. классику: Nielson, Nielson & Hankin, «Principles of Program Analysis».

Где алгебра всплывает в реальном коде: краткий каталог

Криптография с открытым ключом. Diffie–Hellman — это заявление о циклической группе: обе стороны вычисляют один и тот же элемент, потому что (g^a)^b = g^(ab) = (g^b)^a. Безопасность — предположение о сложности дискретного логарифма в этой конкретной группе.

Важная деталь, которую пропускают: безопасность зависит от выбора группы. В (Z/p)* дискретный логарифм решается решетом числового поля за субэкспоненциальное время, поэтому нужны 2048–3072 бита. В группе точек эллиптической кривой лучшая известная атака — O(sqrt(q)) (rho Полларда), поэтому хватает 256 бит. Одна и та же алгебраическая конструкция, разные группы, разница в размере ключа на порядок. См. RFC 7748 (Curve25519) и Handbook of Applied Cryptography, главы 2–3 — свободно доступен.

Ещё деталь: проверка порядка подгруппы. Если реализация не проверяет, что полученная точка/элемент лежит в подгруппе нужного простого порядка, атакующий подсовывает элемент маленького порядка и по остаткам восстанавливает секрет (small subgroup confinement attack). Это буквально теорема Лагранжа, использованная против вас.

CRDT и распределённое состояние. Слияние реплик без координации возможно, если операция слияния образует ограниченную полурешётку: ассоциативна, коммутативна, идемпотентна. Тогда результат не зависит ни от порядка, ни от повторов сообщений — а значит, at-least-once доставки достаточно.

from collections import defaultdict

class GCounter:
    """Grow-only счётчик: коммутативный идемпотентный моноид (полурешётка)
    по покомпонентному max. Слияние: O(число реплик)."""
    def __init__(self):
        self.counts = defaultdict(int)

    def inc(self, replica: str, by: int = 1):
        self.counts[replica] += by

    def merge(self, other: "GCounter") -> "GCounter":
        out = GCounter()
        for k in set(self.counts) | set(other.counts):
            out.counts[k] = max(self.counts[k], other.counts[k])
        return out

    def value(self) -> int:
        return sum(self.counts.values())

a, b = GCounter(), GCounter()
a.inc("n1", 3); b.inc("n2", 5); b.inc("n1", 1)
# слияние в любом порядке, любое число раз — один результат
assert a.merge(b).value() == b.merge(a).value() == a.merge(b).merge(b).value() == 8

Каноническая работа — Shapiro, Preguiça, Baquero, Zawirski, «A comprehensive study of Convergent and Commutative Replicated Data Types» (INRIA RR-7506, 2011). На этом стоят Riak, Redis CRDT, Automerge, Yjs.

Базы данных. Параллельная агрегация в PostgreSQL требует от пользовательского агрегата функции COMBINEFUNC, склеивающей частичные состояния — то есть требует, чтобы состояние было коммутативным моноидом (документация CREATE AGGREGATE). Материализованные представления с инкрементальным обновлением возможны для моноидных агрегатов (SUM, COUNT, MIN при вставках) и невозможны для немоноидных (MEDIAN, PERCENTILE, DISTINCT COUNT точно). Ровно та же граница определяет, что можно посчитать в оконном фрейме за O(1) на сдвиг.

Merkle-деревья и git. Хеш поддерева — это свёртка хешей детей. Дерево работает как индекс над «почти моноидом»: комбинирование ассоциативно только при фиксированной форме дерева, поэтому формат дерева — часть протокола. Git-объекты, Bitcoin-блоки, IPFS, sparse Merkle trees в блокчейнах, дедупликация в резервных копиях — все они полагаются на эту структуру.

Машинное обучение. Softmax-нормализация в лог-полукольце (logsumexp) — стандартная численная практика. Attention с онлайн-нормализацией во FlashAttention корректна именно потому, что «softmax-состояние» (max, sum_exp) — моноид, который можно сливать по блокам. Групповая свёртка (group-equivariant CNN, Cohen & Welling) строит слои, эквивариантные к действию группы симметрий — прямое использование теории представлений.

Типы и языки. Semigroup/Monoid в Haskell, cats.Monoid в Scala, моноидные аннотации в системах эффектов. Хорошее введение с уклоном в практику — Brent Yorgey, «Monoids: Theme and Variations» (Haskell Symposium 2012). Связь с категориями — в статьях Основы теории категорий и Теория категорий в программировании.

Типичные заблуждения

«Float-сложение — моноид». Нет: не ассоциативно из-за округления. (1e16 + 1) - 1e16 = 0, 1e16 + (1 - 1e16) = 1. Нейтральный элемент тоже с оговорками: 0.0 + (-0.0) даёт 0.0, а NaN ломает всё. Практика: параллельные суммы float допустимы, но требовать битовой воспроизводимости нельзя — либо фиксируйте порядок, либо используйте компенсированное суммирование (Кэхэн), либо считайте в целых/decimal.

«Для параллельной свёртки нужна коммутативность». Нет, достаточно ассоциативности: reduce меняет группировку, а не порядок. Коммутативность нужна отдельно, когда порядок прихода данных недетерминирован (сбор результатов по мере готовности).

«Z/n — всегда поле». Только для простого n. В Z/12 элемент 3 необратим. Отсюда: делить по модулю составного числа нельзя, a/b mod n не определено в общем случае.

«Вычитание — моноид». (8 - 3) - 2 = 3, 8 - (3 - 2) = 7. Не ассоциативно, значит даже не полугруппа. То же самое с делением ((8/4)/2 = 1, 8/(4/2) = 4), возведением в степень и «средним двух средних» (avg(avg(0,0), 10) = 5, avg(0, avg(0,10)) = 2.5).

«Группа обязана быть коммутативной». Наоборот: неабелевы группы — правило, а не исключение (S_n при n >= 3, матрицы, повороты в 3D, кватернионы).

«Моноид обязан быть коммутативным». Строки с конкатенацией — моноид, но "ab" != "ba". Матричное умножение — моноид, но некоммутативный.

«max без нейтрального — не моноид, значит свёртка невозможна». Это полугруппа, и свёртка непустой последовательности работает прекрасно. Нейтральный можно добавить искусственно: Option[T] с None как нейтральным превращает любую полугруппу в моноид (это стандартный приём «свободное добавление единицы»).

«Дискретный логарифм доказано труден». Нет. Это предположение. Доказательства нижней границы нет ни для DL, ни для факторизации — см. Теорию сложности. Более того, алгоритм Шора решает обе задачи за полиномиальное время на квантовом компьютере, поэтому и идёт переход к постквантовым схемам на решётках.

«Абстракция моноида — это оверинжиниринг». Иногда да. Критерий пользы ниже.

Trade-offs: когда алгебраическая абстракция окупается

Окупается, когда:

  • нужен параллелизм или распределённость — законы дают право менять порядок вычислений;
  • нужна инкрементальность (стриминг, материализованные вьюхи, оконные агрегаты);
  • нужен откат/undo или обратимость — это буквально запрос «дайте мне группу»;
  • один алгоритм должен работать с разной семантикой (полукольца: один Флойд–Уоршелл на пять задач);
  • корректность критична и её надо доказывать (криптография, коды коррекции, консенсус).

Не окупается, когда:

  • операция одна, кода на десять строк, параллелизма не будет — введение интерфейса Monoid<T> добавит слоёв, но ничего не докажет;
  • законы не выполняются, но их «почти» выполнение объявляют достаточным — это худший вариант: вы получаете ложную уверенность и плавающие баги;
  • команда не готова поддерживать property-based тесты — необеспеченный законами интерфейс Monoid бесполезен, он не проверяется компилятором.

Практическая цена. Абстракция в Python/Go стоит вызовов методов и аллокаций; в Haskell/Rust мономорфизация обычно съедает накладные расходы полностью. Измеряйте: обобщённая semiring_matmul выше в 50+ раз медленнее специализированного numpy-кода. Правильный паттерн — абстракция на уровне архитектуры и специализация в горячем цикле.

Мини-практикум: проверьте себя

  1. Операция join(a, b) = a + "," + b. Полугруппа или моноид? (Полугруппа: ассоциативность выполняется — обе расстановки скобок дают "a,b,c". Но моноида нет: нейтрального e не существует, так как join(a, e) всегда длиннее a хотя бы на символ.)
  2. Сколько элементов в U(15)? Циклична ли эта группа? (φ(15) = 8; не циклична — U(15) ≅ Z/2 × Z/4.)
  3. Почему (Z/6, +, ×) — кольцо, но не поле? Найдите все делители нуля. (2, 3, 4.)
  4. Постройте моноид для «последнего непустого значения» (Last). Является ли он коммутативным? Идемпотентным?
  5. Докажите, что в группе из чётного числа элементов обязательно есть элемент порядка 2. (Подсказка: элементы, не равные своему обратному, разбиваются на пары.)
  6. Почему медиана не является гомоморфизмом моноидов и какой моноид её приближает? (t-digest / KLL-скетч.)

Для экспериментов с конечными группами удобны GAP и SageMath — в них уже есть таблицы Кэли, решётки подгрупп и классификация групп малого порядка.

Итог

  • Магма → полугруппа → моноид → группа → абелева группа — лестница аксиом. Каждая ступень даёт новые теоремы и сужает круг объектов.
  • Ассоциативность = право на параллелизм. Нейтральный элемент = право свернуть пустое. Идемпотентность + коммутативность = право сливать реплики без координации.
  • Гомоморфизм — критерий инкрементальности: если агрегат гомоморфен, его считают распределённо; если нет — только приближённо.
  • Кольцо — две операции с дистрибутивностью, деление не гарантировано; поле — деление есть у всех, кроме нуля. Z/n — поле ровно для простого n.
  • Конечные поля GF(p^k) — рабочая лошадка криптографии и кодов коррекции ошибок: AES, Рид–Соломон, erasure-кодирование, разделение секрета Шамира.
  • Полукольца превращают один алгоритм в семейство: Флойд–Уоршелл в тропическом, транзитивное замыкание в булевом, Витерби в max-prod.
  • Законы проверяются тестами, а не декларациями: property-based тесты на ассоциативность и нейтральность — обязательная часть любой моноидной абстракции.

Источники

Что дальше

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

Теория категорий: объекты, морфизмы, функторы, естественные преобразования

Нашли неточность? Выделите фрагмент текста — рядом появится жучок.

Нужен разбор именно вашей ситуации?

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

Доска запросов