Изменения
Нет описания правки
'''Обратное дискретное преобразование Фурье''' (англ. ''Inverse DFT'') для вектора значений многочлена <tex>A(\omega_n)</tex> <tex>(y_0, y_1, \ldots , y_{n-1})</tex> {{---}} это вектор коэффициентов этого многочлена <tex>(a_0, a_1, \ldots , a_{n-1})</tex>:
<center>
<tex>
InvDFT(y_0, y_1, \ldots , y_{n-1}) = (a_0, a_1, \ldots , a_{n-1}).
</tex>
</center>
}}
<center>
<tex>
(\omega_n)^n = 1 (\ \mod p),
</tex>
<tex>
(\omega_n)^k \ne (1 \ \mod p), 1 \leqslant k < n.
</tex>
</center>
Как и с комплексными корнями, остальные <tex>n-1</tex> корней <tex>n</tex>-ой степени из единицы по модулю <tex>p</tex> можно получить как степени примитивного корня <tex>\omega_n</tex>
== Утверждения ==
{{
== См. также ==
*[[Быстрое преобразование Фурье]]
*[https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%B5%D0%BE%D0%B1%D1%80%D0%B0%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D1%83%D1%80%D1%8C%D0%B5 Википедия {{---}} Дискретное преобразование Фурье]
*[http://e-maxx.ru/algo/fft_multiply MAXimal::algo::Быстрое преобразование Фурье за O (N log N)]
[[Категория: Дискретная математика и алгоритмы]]
