TL;DR Вам нужны NTT для точной арифметики в крипто-приложениях.
БПФ — это просто алгоритм для оценки традиционного ДПФ, для векторов с комплексными значениями (обратите внимание, что действительные и целые числа являются подмножествами комплексного поля, поэтому это применимо и к ним) векторов $(f_0,\dots,f_{N-1})$ длины $N$ которое определено над комплексным полем $\mathbb{C}$ используя комплексный корень из единицы порядка $N.$
Здесь у нас есть
$$
F(\lambda)=\sum_{k=0}^{N-1} f_k e^{2 \pi i \lambda k/N}=
\sum_{k=0}^{N-1} f_k \xi_N^{\lambda k}, \quad
\xi_N:=e^{2 \pi i /N}, \lambda=0,1,\ldots,N-1
$$
Такой сложный корень единства существует для всех $N$, однако БПФ более эффективен, если $N$ является составным, максимальная эффективность достигается для $N=2^м,$ для некоторого целого числа $ млн $
Проблемы с ДПФ: В криптографии мы работаем с конечными объектами и действительно можем получить полную точность, которая на практике неприменима в комплексной области, поскольку аргумент комплексного корня из единицы иррационален, а точная арифметика вообще невозможна.
Теперь НТТ, независимо от того, основаны ли они на конечном поле или целых корнях из единицы по модулю определенных колец, дайте нам полную точность (сложные ДПФ не могут этого сделать и не могут использоваться для криптографии) и оцениваются в собственном кольце, которое используется в криптографии. Они все еще являются ДПФ. И для определенных длин могут иметь эффективные реализации.
Выбор НТТ:
Предположим, что входной вектор представляет собой последовательность $N$ неотрицательные целые числа.
В общем случае нужно выбрать модуль $ млн $ такой, что $1â¤N<M$ и каждое входное значение находится в диапазоне $[0,М).$ Если мы говорим о внедрении криптографии, мы уже знаем модуль.
Выберите некоторое целое число $к¥1$ и определить $N'=kN+1$ как рабочий модуль. Нам нужно $N'¥M,$ и для простоты возьмем $N'$ быть простым числом. Теорема Дирихле гарантирует, что при данных $N$ и $ млн, $ можешь выбрать $к$ сделать $N'$ премьер.
Так как $N'$ является простым, мультипликативная группа $\mathbb{Z}_{N'}$ имеет размер $Ï(N')=N'â1=kN$ а также генератор $г,$ который также является примитивным (N' 1)-й корень из единицы.
Позволять $\omegaâ¡g^k \pmod N'.$ затем $\омега$ является примитивным $N$корень из единицы, необходимый для получения ДПФ длины $N,$ Итак, это NNT:
$$
F(\lambda)=\sum_{k=0}^{N-1} f_k \omega^{\lambda k},\quad \lambda \in \mathbb{Z}_N.
$$
Можно применить редукции Монтгомери (или менее эффективные редукции Барретта) для ускорения модульной арифметики в NTT.
