4.3. Трехмерное преобразование Фурье в поле

_{Рассмотрим ДПФ длины} N=255, ядром которого является примитивный элемент поля _.

(1)

, ,

(2)

Произвольный ненулевой элемент поля ) задается как степень примитивного элемента поля: = ,

Согласно (2)

(3)

, =, ==,

Где приняты обозначения: =, =,=

Более того, в силу попарной взаимной простоты модулей , если i(, ,) и j(, , ), то ij(, , ). Таким образом, формулу (4.1) определяющую ДПФ, можно переписать в виде:

(4)

, =, =

Это сразу подсказывает следующий алгоритм вычисления вектора по вектору . Сначала разбиваем координаты вектора на тройки чисел (прификсированных и ) и к каждой из них применяем 3-точечное преобразование с ядром =; это дает набор из 255 величин

(5)

, =, =.

Затем к этому вектору длины 255 применяется 5-точечное ДПФ с ядром = по правилу: координаты вектора группируются по 5 чисел (по фиксированным и ) и для каждой такой совокупности вычисляется 5-мерный вектор ,

(6)

, =, =.

Наконец, к вектору длины 255 применяется 17-точечное ДПФ с ядром =, приводящее к искомому 255-мерному вектору :

(7)

, =, =.

(8)

(9)

Экспериментально установлено, что переход от одномерной структуры к трехмерной, уменьшает время, требуемое на вычисление ДПФ примерно в 10 раз.

Таким образом, переход от ДПФ длины 255 к ДПФ длин 3, 5 и 17, каждое из которых вычисляется 255 раз в цикле, очень существенно понижает вычислительную сложность алгоритма.

Следующий наш шаг – полностью избавиться от ДПФ внутри циклов, заменив их на БПФ (быстрое преобразование Фурье) длин 3, 5 и 17, которые основаны как на свойствах поля , так и на свойствах алгоритмов быстрого умножения многочленов, заданных над конечным полем.