dxdt.ru: занимательный интернет-журнал

В продолжение недавней записки про числа в ML-KEM. Один из ключевых параметров ML-KEM, одинаковый для всех наборов, это число (модуль) 3329. Почему выбрано именно 3329? Был ли выбор “случайным” (а иногда используют проверяемые методы для выбора параметров) или это число подобрано специально?

Число 3329, обозначаемое q, в ML-KEM выбрано строго специально. И вот из каких соображений. Весь практический вычислительный смысл ML-KEM (Kyber) в преобразовании (NTT), позволяющем быстро производить арифметические операции с полиномами. Чтобы быстрые операции NTT стали возможны в ML-KEM, число q должно быть простым, а (q-1) должно делиться на 256. (Более “общо” – делиться должно на степень двойки.) 256 – это другой параметр ML-KEM, его значение продиктовано разрядностью операций (256 бит).

То есть, 3329 – простое, (3329 – 1)/256 == 13. Если эти требования не выполняются, быстрый NTT работать должным образом не будет, поскольку это не настолько универсальный алгоритм, умножать полиномы “в лоб” – очень медленно, и другие быстрые алгоритмы – тоже оказываются медленными по сравнению с NTT. Неподалёку от 3329 не так много чисел, обладающих описанными свойствами: 257, 769, 3329, 7681, 7937. При этом, нужно выбрать число поменьше (важна экономия каждого бита), но чтобы не слишком выросла вероятность получения неверного результата при работе криптосистемы. Для 257 и 769 вероятность ошибки заметно больше. Поэтому авторы алгоритма выбрали 3329.

Адрес записки: https://dxdt.ru/2025/02/16/15043/