Изменения
→Применение ДПФ
<tex>
\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = (y_0, y_1, \ldots , y_{n-1}) = (A(\omega_{n,0}), A(\omega_{n,1}), \ldots , A(\omega_{n,n-1}))
</tex>
<tex>
<center>
<tex>
A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTFDFT}(B)).
</tex>
</center>
Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n \log n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].
ДПФ также применяют для быстрого умножения двух длинных чисел, которые в свою очередь могут быть представлены в виде полиномов.
== ДПФ в модульной арифметике ==
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый [[Первообразные корни | примитивным]].
Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти [[Примитивные корни | примитивный корень]], то есть:
<center>
<center>
<tex>
y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}
</tex>
</center>
<center>
<tex>
y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},
</tex>
</center>
<center>
<tex>
x_0 = \ \ 1 5 \\
x_1 = \ \ 2 \\
x_2 = \ \ 4 \\
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
[[Категория: Аналитическая теория Алгоритмы и структуры данных]][[Категория: Алгоритмы алгебры и теории чисел]][[Категория: Основные элементы теории чисел]][[Категория: Основные алгоритмы теории чисел]]
