Теоретико-числовое преобразование

Когда Chrome начиная со 131-й версии открывает страницу по HTTPS, он договаривается о ключе не только эллиптической кривой, но и схемой ML-KEM — её стандартизовали в 2024 году как защиту от будущих квантовых компьютеров. Внутри ML-KEM без конца умножаются многочлены степени 255 с коэффициентами по модулю 3329. Столбиком одно такое умножение — 65 536 произведений. ML-KEM делает его за 3584: это быстрое преобразование Фурье, только вместо комплексных корней из единицы — остатки. Число 17 по модулю 3329 — корень из единицы степени 256: 17²⁵⁶ даёт при делении на 3329 остаток 1. И никаких округлений.

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

Идея

Быстрое преобразование Фурье держится на одном свойстве: есть число ω, у которого ωⁿ = 1, а меньшие степени не равны 1, и половина его степеней — это степени ω². Комплексное e^2πi/n подходит, но с ним приходят числа с плавающей точкой. Остатки по модулю простого p образуют такое же поле: их можно складывать, умножать и делить на ненулевое. Если n делит p − 1, в нём есть корень из единицы степени n.

Возьмём простое p = c · 2^k + 1 и первообразный корень g: тогда ω = g^c — корень из единицы степени 2^k, и всё быстрое преобразование Фурье переносится дословно, только каждое действие — по модулю p. Свёртка получается точной по модулю p, а если настоящие коэффициенты меньше p — просто точной.

Из этого следует обратное преобразование: применить то же самое с ω⁻¹ и разделить на n. Значение под суммой — 1, только когда индексы совпадают, и n, а иначе 0. А дальше всё как у комплексного БПФ: значения произведения многочленов — произведения значений, поэтому свёртка — это преобразование, поточечное умножение и обратное преобразование.

Неполное преобразование в ML-KEM

В ML-KEM многочлены живут по модулю x²⁵⁶ + 1, а не x²⁵⁶ − 1: свёртка «с минусом», когда вылезающее за край слагаемое возвращается со знаком минус. Для неё нужен корень из −1 подходящей степени: ψ с ψ²⁵⁶ = −1, то есть корень степени 512. Но 3329 − 1 = 3328 = 13 · 2⁸, и корня степени 512 нет. Поэтому стандарт останавливается на слой раньше: семь слоёв разбивают x²⁵⁶ + 1 на 128 множителей x² − γ_i, и в середине перемножаются 128 многочленов первой степени по модулю своих x² − γ_i.

Код

Первая часть листинга — алгоритмы 9–12 стандарта FIPS 203 буквально: таблица ζ^BitRev7(k), прямое и обратное преобразования и умножение пар по модулю x² − γ. Таблица совпадает со стандартом с первых чисел: 1, 1729, 2580, 3289. Двадцать случайных произведений сверяются со столбиком. Вторая часть — точное умножение двух чисел по 20 000 цифр через модуль 998 244 353 = 119 · 2²³ + 1.

Где числам с плавающей точкой не хватает точности

Комплексное БПФ тоже умножает длинные числа, но его коэффициенты — числа с плавающей точкой, и их приходится округлять до целых. Чем длиннее числа и чем больше цифр укладывается в один коэффициент, тем дальше результат от целого, — а когда коэффициенты превышают 2⁵³, у них в формате double вовсе нет дробной части, и ошибка становится невидимой. Ниже — два случайных числа, перемноженные обоими способами и сверенные с BigInt браузера.

Сто тысяч цифр по пять в коэффициенте БПФ ещё перемножает верно: дальше всего от целого — 0,03. По шесть — отклонение доходит до половины, и округление уже ошибается. По семь коэффициенты больше 2⁵³: отклонение «ноль», а ответ неверный. NTT по одной цифре в коэффициенте держит их меньше 81 · n: для чисел до четырёх миллионов цифр это меньше модуля, а длина преобразования укладывается в 2²³, — ошибиться негде. Для коэффициентов больше модуля берут два-три модуля и собирают ответ китайской теоремой об остатках.

Сколько это стоит

Столбик растёт как квадрат, NTT — как n log n. На тысяче коэффициентов NTT на Python быстрее почти вчетверо, на Go при шестнадцати тысячах — в сорок раз. По сравнению с комплексным БПФ каждая бабочка дороже: умножение по модулю — это умножение и деление, — поэтому в библиотеках модульное умножение делают по Монтгомери или Барретту, без деления, как и в реализациях ML-KEM.

Где легко ошибиться

• Не тот модуль. Длина преобразования должна делить p − 1. У 998 244 353 это до 2²³ — около восьми миллионов; у 10⁹ + 7 степень двойки в p − 1 всего 2¹, и быстрого преобразования по нему не построить.
• Переполнение в умножении. Произведение двух остатков 998 244 353 — до 10¹⁸: в 64 бита помещается, а в 53 бита double в JavaScript — нет. В сцене множитель режется на две половины по 15 бит.
• Ответ по модулю, а не число. NTT даёт коэффициенты по модулю p. Если настоящие коэффициенты больше p, их не восстановить без второго модуля.
• Забытое деление на n в обратном преобразовании: ответ отличается в n раз — по модулю, то есть выглядит как случайные числа.
• Свёртка с плюсом вместо минуса. В ML-KEM вылезающее за x²⁵⁵ возвращается со знаком минус; обычное циклическое NTT здесь даст другой многочлен.

Где работает

Постквантовая криптография: ML-KEM (FIPS 203) — обмен ключами, ML-DSA (FIPS 204) — подписи; в TLS гибрид X25519MLKEM768 включён по умолчанию в Chrome со 131-й версии и в Go 1.24. Длинная арифметика: модуль decimal в Python переходит на теоретико-числовое преобразование для длинных коэффициентов. Олимпиадные задачи на свёртки и производящие функции по модулю 998 244 353.

История

Джон Поллард в 1971 году описал быстрое преобразование Фурье над конечным полем. В том же году Арнольд Шёнхаге и Фолькер Штрассен построили на преобразованиях по модулю алгоритм умножения целых чисел за O(n log n log log n), и он полвека оставался ориентиром. Схема Kyber, из которой вырос ML-KEM, выбрана в конкурсе постквантовых алгоритмов NIST; стандарт FIPS 203 опубликован в августе 2024 года.

Задачи

Много произведений многочленов ML-KEM: один множитель общий, и его преобразование считается один раз.