Полиномы: основа кодирования и криптографии

Данные с марсохода Curiosity идут 20 минут до Земли и при этом содержат ошибки. Reed-Solomon - полиномиальная интерполяция - восстанавливает каждый бит. QR-код может быть повреждён на 30% и всё равно читаться. Это не магия резервирования - это теорема Лагранжа: полином степени n определяется n+1 точками. Без этого алгоритма: тишина из космоса и нечитаемые коды.

• **Reed-Solomon в QR-кодах**: код L-уровня исправляет до 7% повреждений, H-уровня - до 30%. Это полиномиальная интерполяция над GF(2^8) - конечным полем из 256 элементов
• **NASA Voyager и Deep Space Network**: полиномиальное кодирование позволяет принимать сигналы с расстояния 20+ млрд км при мощности передатчика 22 Вт - меньше лампочки холодильника
• **Polynomial rolling hash (Рабин-Карп)**: метод Горнера для поиска подстрок за O(n) - основа grep и поисковых движков
• **Схема Шамира**: интерполяция Лагранжа позволяет разбить криптографический ключ на k частей так, что любые t из них восстанавливают ключ - аппаратные модули безопасности и мультиподписи

Предварительные знания

• Неравенства и модуль

Арифметика полиномов: кольцо, степень, умножение

Полином степени n - это выражение p(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀, где aₙ != 0. Сложение - почленно: суммируются коэффициенты при одинаковых степенях. Умножение - через дистрибутивность: каждый член первого полинома умножается на каждый член второго. **Полиномы образуют кольцо** - замкнутую структуру: сумма и произведение полиномов - снова полином.

**Степени:** - deg(p·q) = deg(p) + deg(q) - степень произведения - deg(p+q) <= max(deg(p), deg(q)) - степень суммы - Равенство может не достигаться: старшие коэффициенты могут обнулиться **Кольцо полиномов F[x]**: если коэффициенты из поля F (например, из вещественных чисел или из GF(2)), полиномы образуют евклидово кольцо - в нём работает алгоритм Евклида.

**Reed-Solomon - полиномы над GF(2^8)**: QR-код хранит данные как полином над конечным полем. Избыточность кода L-уровня позволяет восстановить до 30% повреждений. Это не резервное копирование - это теорема Лагранжа: полином степени n однозначно определён n+1 точкой. Даже если часть точек потеряна - остальные восстанавливают всё.

Метод Горнера: O(n) вместо O(n^2)

Наивное вычисление p(x) = aₙxⁿ + ... + a₀ требует O(n^2) умножений: каждое xᵏ стоит k умножений. Метод Горнера переписывает полином через вложенные скобки: p(x) = (...((aₙ·x + aₙ₋₁)·x + aₙ₋₂)·x + ... + a₁)·x + a₀. Каждый шаг - одно умножение и одно сложение. Итого O(n). Это не просто оптимизация - это фундамент строкового хеширования.

**Polynomial rolling hash** - это метод Горнера с простым mod. Алгоритм Рабина-Карпа для поиска подстрок: вычислить хеш всех n-символьных окон за O(n) через rolling update. Убрать старший символ, сдвинуть, добавить новый - одна операция умножения. Именно так работает `grep` и полнотекстовый поиск.

Деление полиномов: теорема об остатке и CRC

Деление полиномов аналогично длинному делению натуральных чисел: p(x) = q(x)·d(x) + r(x), где deg(r) < deg(d). **Теорема об остатке**: остаток от деления p(x) на (x - c) равен p(c). Следствие: (x - c) делит p(x) тогда и только тогда, когда c - корень p. Это мгновенный тест делимости без явного деления.

**Теорема о рациональных корнях:** если p(x) = aₙxⁿ + ... + a₀ имеет рациональный корень p/q (несократимую дробь), то p делит a₀ и q делит aₙ. Это сужает перебор кандидатов для факторизации до конечного списка.

**CRC (Cyclic Redundancy Check)** - полиномиальный алгоритм Евклида над GF(2). Данные трактуются как полином, делятся на порождающий полином; остаток - контрольная сумма. Ethernet, USB, ZIP - все используют CRC-32. Это не хеш - это точная детекция любой одиночной пакетной ошибки. Математика та же самая, что в длинном делении на бумаге, только в двоичном поле.

Интерполяция Лагранжа: теорема и космические данные

**Данные с марсохода Curiosity идут до Земли 20 минут и при этом содержат ошибки.** Reed-Solomon - полиномиальная интерполяция - восстанавливает каждый бит. Принцип: через n+1 точку с различными x-координатами проходит ровно один полином степени <= n. Потеряли часть точек - восстановили по оставшимся. Это теорема Лагранжа в действии.

**Предупреждение Рунге:** при большом числе равноудалённых узлов полином Лагранжа может сильно осциллировать у краёв. В численных методах используют **узлы Чебышёва** xₖ = cos((2k+1)π/(2n+2)) - они минимизируют максимальную ошибку. Reed-Solomon обходит эту проблему, работая над конечным полем GF(2^8), где осцилляций не бывает.

**Схема Шамира** - криптографический протокол разделения секрета: ключ кодируется как p(0), участники получают точки полинома. Любые t из n участников восстанавливают ключ через интерполяцию; меньше t - ничего не узнают. Используется в аппаратных модулях безопасности (HSM) и мультиподписных криптокошельках.

Ключевые идеи

• **Метод Горнера** вычисляет полином степени n за O(n) умножений - основа polynomial rolling hash и CRC
• **Теорема об остатке:** остаток от деления p(x) на (x-c) равен p(c) - мгновенный тест делимости без явного деления
• **НОД полиномов** находится алгоритмом Евклида - основа CRC-32 в Ethernet, USB и ZIP
• **Интерполяция Лагранжа:** n+1 точка однозначно определяет полином степени <= n - основа Reed-Solomon и схемы Шамира

Связанные темы

Полиномы - строительный блок для дискретной математики, теории чисел и алгебраических структур:

• Комплексные числа — Корни полиномов над R могут быть комплексными - переход к C
• Кольца и поля — Кольцо полиномов F[x] - центральный пример в абстрактной алгебре
• Теория Галуа — Разрешимость полиномов радикалами описывается группой Галуа

Вопросы для размышления

• Reed-Solomon может исправить до 30% повреждённых символов. Что происходит при 31%? Почему именно этот порог?
• Polynomial hash может давать коллизии. Как выбор base и mod влияет на вероятность коллизии, и почему используют простое число?
• В чём принципиальная разница между интерполяцией (точное прохождение через точки) и аппроксимацией МНК? Когда применяется каждый метод?

Связанные уроки

• alg-03 — Неравенства и модули - предыдущий урок
• alg-05 — Комплексные корни полиномов над R
• alg-12 — Кольцо полиномов F[x] - центр абстрактной алгебры
• ar-28-modular — GF(2^8) - полиномы над конечным полем в Reed-Solomon
• ar-44-crypto-intro — Схема Шамира: секрет = значение полинома в 0
• la-01-vectors-intro