3.3.4 Связь между полиномиальными преобразованиями и ДПФ

Из следует, что существование -точечного полиномиального преобразования, обладающего свойством циклической свертки, зависит только существования корня степени из единицы и элемента в поле коэффициентов. Эти условия являются общими для всех -точечных преобразований, обладающих свойством циклической свертки [3.22], -точечное полиномиальное преобразование, имеющее корень Z и определенное по модулю можно рассматривать как ДПФ, определенное в кольце полиномов по модулю

Это свойство аналогично теоретико-числовым преобразованиям, которые можно рассматривать как ДПФ, определенные на кольце целых чисел. Фактически ТЧП являются частными случаями полиномиальных преобразований, в которых Л-битовые элементы должны рассматриваться как полиномы. В наибольшей степени это очевидно для -точечиого полиномиального преобразования, определенного по модулю Такое преобразование вычисляет -точечную циклическую свертку с помощью полиномов по членов. Если входных полиномов определены как элементы по 2 бит, то полиномиальное преобразование сводится к преобразованию последовательности длиной по числам Ферма, с корнем 2 и определенному по модулю

Поскольку полиномиальные преобразования являются ДПФ, определенными на кольцах полиномов, они по существу эквивалентны многомерным ДПФ и поэтому применяются преимущественно для решения многомерных задач. Их главное достоинство по сравнению с ДПФ и ТЧП обусловлено тем, что они систематически используют удобство операций на кольце полиномов для определения простых корней из единицы, что позволяет обойтись без умножений при вычислении преобразования. Для некоторых приложений, таких, как вычисление -точечных сверток, полиномиальные преобразования оптимальны в том смысле, что могут порождать алгоритмы с таким числом общих умножений, которое нельзя больше уменьшить чисто алгебраическими методами.