Изменения
→ДПФ в модульной арифметике
== ДПФ в модульной арифметике ==
В основе ДПФ используются комплексные числа, являющиеся корнями <tex>n</tex>-ой степени из единицы. Для эффективного вычисления использовались свойства комплексных корней, которые образуют [[Группа | группу]], то есть степень одного корня всегда является другим корнем. Среди них есть корень, называемый примитивным.
Однако, то же верно и в случае корней <tex>n</tex>-ой степени из единицы в модульной арифметике. Не для любого модуля <tex>p</tex> найдется <tex>n</tex> различных корней, но такие модули все же существуют. Необходимо найти примитивный корень, то есть:
