Существует ли самая известная реализация для числового теоретического преобразования на конечном поле 257 (2^8 + 1)?
Я немного новичок, когда дело доходит до реализации БПФ в целом, но я думаю, что у меня есть большинство основных идей. В этом конкретном случае у меня есть реализация теоретико-числового преобразования в конечном поле 257. Это в основном ваш типичный Radix-2 Cooley-Tukey FFT. Что я хотел бы знать, так это: есть ли хорошая альтернатива Cooley-Tukey Radix-2, которая лучше подходит для эффективного выполнения этого конкретного NTT (если ответом является безоговорочное да или условное "да" на что-то, не входящее в сферу действия этот вопрос, мне интересно услышать и то, и другое), или есть какие-то особенности, относящиеся к Mersenne NTT, которые обеспечивают более эффективную реализацию, чем более общий случай?
1 ответ
Я бы сказал, что для диафрагмы БПФ нет ничего лучше, чем Кули-Тьюки.
Это не имеет ничего общего с числами Мерсенна, любое числовое поле с модулем 2^(m*2^n)+1 квалифицируется. I=2^(m*2^(n-1)) это сложная единица, I^2=2^(m*2^n)=-1 mod (2^(m*2^n)+1), а также q=2^(2*m) это примитив 2^nкорень единства.
Для вдохновения для второй точки см. Раздел 1 Schönhage: Асимтотически быстрые алгоритмы для числового умножения..., с полным резюме быстрых умножений