Подытожим по пунктам основные результаты путешествия в страну ЧП Ферма. И так,

0) ЧП Ферма очень похоже на обычное ДП Фурье комплексных данных и поэтому большинство БА ДПФ, которые напрямую используют комплексную арифметику, годятся и для ЧП Ферма, кроме тех, которые разделяют комплексные вычисления на вещественную и мнимую части (т.е. кроме таких, как эффектный БА ДПФ Уэнга-Капорина, ДКП и пр.).

1) ДП — это преобразование одного набора чисел в другой

2) Самые оптимальные БА для ДП Фурье (такие, как алгоритмы Винограда для коротких свёрток, БА Уэнга-Капорина для ДПФ, ТА Григоряна для 2мДПФ) построены с общей идеей — заранее просуммировать какие-то компоненты векторов входных данных, а уже потом из этих промежуточных сумм формировать выходные результаты. Поэтому такие теоретически неулучшаемые БА имеют сложную для понимания структуру (т.е. она не ясна и требует много времени для понимания).

Напротив, БА ДПФ, которые используют только часть свойств ДПФ — периодичность или симметрию характеров (т.е. базисных функций преобразования, равных степеням КОРНЕЙ из 1), избыточность комплексного ДПФ при вещественных входных данных и пр., например, такие как БПФ Кули-Тьюки при N=2v , алгоритм ДПФ Герцеля, ПСА ДПФ-m, ГА ДПФ-m и другие, имеют понятную (прозрачную для изучения) структуру, хотя число операций (вещественного) умножения у них заметно больше, чем у самых оптимальных БА.

БА, которые сводят ДПФ к многомерному ДПФ-m или ЦС-m в матричных моделях тоже выглядят громоздко, (тоже и при представлении ДПФ через ПП), т.е. их структурная сложность на много выше, чем у простого БПФ Кули-Тьюки при   N=2v . Поэтому платой за стремление уменьшить число умножений и сложений в БА ДПФ и ЦС является значительное возрастание структурной сложности этих БА.

3) Из всех модулярных преобразований, пожалуй, только числовые преобразования по модулю чисел Ферма оказались похожими на комплексное ДПФ и наиболее просты для вычислений на современных компьютерах с двоичной арифметикой и длиной регистра равной степени 2. А сам Ферма, как добрый волшебник, следит за теми, кто путешествует по его стране и спасает их в самых трудных ситуациях.

4) Ряд чисел Ферма

Поэтому в алгоритмах, например, по модулю числа Ферма F2 достаточно использовать только 4-х битовые регистры (типа SHORTCARD/SHORTINT, укороченные до 4-х бит), хотя в специальном случае для представления длины преобразования T=F2-1=16 уже нужно 5 битов, тоже и для величины КОРНЯ из 1 root=16 при T=2. Эти частные случаи можно учесть отдельно от прочих и не использовать для хранения T и root всегда 5 битов памяти (т.е. не использовать стандартный 8-битовый тип данных SHORTCARD/SHORTINT).

В алгоритмах по модулю числа Ферма F3 достаточно использовать только 8-ми битовые регистры (типа SHORTCARD/SHORTINT), хотя в специальном случае для представления длины преобразования T=F3-1=256 уже нужно 9 битов, тоже и для величины КОРНЯ из 1 root=256 при T=2. Эти частные случаи можно учесть отдельно от прочих и не использовать для хранения T и root всегда 9 битов памяти (т.е. не использовать стандартный 16-битовый тип данных CARDINAL/INTEGER).

В алгоритмах по модулю числа Ферма F4 достаточно использовать только 16-ти битовые регистры (типа CARDINAL/INTEGER), хотя в специальном случае для представления длины преобразования T=F4-1=65536 уже нужно 17 битов, тоже и для величины КОРНЯ из 1 root=65536 при T=2. Эти частные случаи можно учесть отдельно от прочих и не использовать для хранения T и root всегда 17 битов памяти (т.е. не использовать стандартный 32-битовый тип данных LONGCARD/LONGINT).

В алгоритмах по модулю числа Ферма F5 достаточно использовать только 32-х битовые регистры (типа LONGCARD/LONGINT), хотя в специальном случае для представления длины преобразования T=F5-1=232 уже нужно 33 бита, тоже и для величины КОРНЯ из 1 root=232 при T=2. Эти частные случаи можно учесть отдельно от прочих и не использовать для хранения T и root всегда 33 бита памяти и т.д.

5) При использовании ЧП Ферма результат всегда должен находится в ПСАНВ± по модулю числа Ферма   Fn = 22n + 1 = 2b + 1 .

При использовании ТЧП Гаусса результат всегда должен находится в ПСАНВ± по модулю ЦКЧ Гаусса   μ .

6) При использовании ЧП Ферма на динамический диапазон входа и выхода накладываются ограничения (связанные с тем, что результат операции в модулярной ариметике должен совпадать с результатом в обычной арифметике).

Для сигналов не из кольца ЦКЧ Гаусса диапазоны значений входа и результата относятся как

7) Удачный выбор модуля в кольце ЦКЧ Гаусса в виде такого ЦКЧ   μ ,   у которого норма равна числу Ферма   Fn , позволяет легко (без умножений и делений) переходить из кольца ЦКЧ Гаусса в целочисленное кольцо (или поле) по модулю числа Ферма, т.е. проводить вычисления ЦС и ДП сигналов (даже комплексных) без умножений (через ЧПФ) с последующим возвратом результатов обратно в кольцо ЦКЧ Гаусса.

При этом наблюдается интересное соотношение между диапазонами значений входных данных, результата ЦС или ДП и, собственно, величиной модуля преобразования

8) Ограничения на длину преобразования (ЦС, ЧПФ) в модулярной арифметике и зависимость этой длины от размера модуля (т.е. арифметического регистра компьютера) можно ослабить, используя многомерные модели для представления одномерной ЦС и ЧПФ (т.е. через ЦС-m и ЧПФ-m).

9) Все ДП (ДПФ, ТЧП, ПП) имеют общее свойство — это свойство ЦС и их базовые функции (характеры) являются КОРНЯМИ из 1 порядка (степени)   N . Тоже и для ДП Ганкеля-Теплица и др. Хотя существуют и такие ДП, которые не обладают свойством ЦС (т.е. не изоморфны ЦС).

10) На пути ускорения БА ДПФ (ЧПФ) есть перспективная схема вычисления одномерных ЧПФ через многомерные ЧПФ-m, используя теоретически оптимальный двумерный ТА Григоряна с размерами   N = 2v = N1х N2 = 4Mх 8L . Такое сочетание размеров (прямоугольная матрица) покрывает все длины N=2v , при которых умножения на базовые элементы, равные степени 2, можно заменить на быстрые сдвиги целых и при этом используется единая общая конструкция алгоритма для всех длин преобразования   N = 2v   с минимальным числом операций.

11) БА ДП Фурье существуют для любой длины вектора N, т.е.
- для простого (неразложимого) N,
- разложимого на взаимно-простые множители,
- разложимого на любые множители,
- представимого в виде N=2v, N=rv и прочее.
Схемы (модели) вычисления ДПФ при этом могут быть разными по своей структурной сложности и по вычислительной сложности (в смысле числа умножений и сложений). Тоже самое относится и к ЧП Ферма.