Произведения в ML-KEM
В ML-KEM многочлены живут в кольце Z3329[x] / (x²⁵⁶ + 1): коэффициенты — остатки от деления на 3329, а x²⁵⁶ заменяется на −1. Дан многочлен a и много вторых множителей b1, …, bq. Найдите каждое произведение c = a · bi в этом кольце.
Чтобы вход был коротким, bi задан двумя числами s и t: его коэффициент при xj — это (s · j² + t · j + s + t) mod 3329, j = 0 … 255. А чтобы выход был коротким, вместо 256 коэффициентов c0, …, c255 (каждый от 0 до 3328) выведите Σ (j + 1) · cj mod (10⁹ + 7).
Вход
В первой строке — 256 коэффициентов a, от свободного члена, каждый от 0 до 3328. Во второй — q (1 ≤ q ≤ 5000). Дальше q строк: s и t (0 ≤ s, t < 3329).
Выход
Для каждого множителя — контрольная сумма произведения в отдельной строке.
Примеры
Пример 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 1
53631721 5595393
Пример 2
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3
56233561
Ограничения
- Время · Python
- 18500 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Столбиком одно произведение — 65 536 умножений, а их пять тысяч. Многочлен a во всех произведениях один и тот же: какую работу с ним можно сделать один раз?
2Подсказка 2
17 по модулю 3329 — корень из единицы степени 256, и 17¹²⁸ ≡ −1. Значит, x²⁵⁶ + 1 = x²⁵⁶ − 17¹²⁸ раскладывается на множители, и умножение по модулю каждого множителя дешёвое.
3Идея
Неполное теоретико-числовое преобразование ML-KEM: семь слоёв бабочек переводят многочлен в 128 остатков по модулю x² − γi, там произведения считаются парами коэффициентов, а обратное преобразование собирает ответ. Преобразование a делается один раз, для каждого bi — прямое преобразование, 128 маленьких произведений и обратное.
4Разбор
Таблицы ζk = 17BitRev7(k) и γk = 172·BitRev7(k)+1 по модулю 3329 строятся один раз. Прямое преобразование — длины 128, 64, …, 2, бабочка t = ζ · f[j + len], f[j] ± t; обратное — те же бабочки в обратном порядке и умножение на 3303 = 128⁻¹. В середине (a0 + a1x)(b0 + b1x) = a0b0 + a1b1γ + (a0b1 + a1b0)x.
4+Решение
5Сложность
На одно произведение — 896 умножений в прямом преобразовании, 640 в середине и 1152 в обратном, вместо 65 536.
6Типичные ошибки
- Столбиком. Это
wrong.py: на примерах успевает, а пять тысяч множителей — это больше трёхсот миллионов умножений. - Обычная циклическая свёртка. Если забыть, что x²⁵⁶ = −1, и складывать вылезающее за край с плюсом, получится произведение в другом кольце. Седьмой тест умножает на x²⁵⁵, и знак там решает всё.
- Полное преобразование. Восьмого слоя нет: для него нужен корень степени 512, а 3328 = 13 · 2⁸ на 512 не делится.
- Отрицательные остатки. В Go и C разность (f[j] − t) % 3329 бывает отрицательной — добавьте 3329.