Преобразование Фурье над конечными полями

Преобразование Фурье над конечными полями (также известное как дискретное преобразование Фурье в конечных полях, DFT на конечных полях, теоретико-числовое преобразование — ТЧП, NTT) — это алгебраический аналог классического дискретного преобразования Фурье, в котором арифметика комплексных чисел заменяется арифметикой конечного поля (поля Галуа). Данное преобразование широко применяется в теории кодирования, криптографии, обработке сигналов и компьютерной алгебре благодаря возможности быстрых вычислений без ошибок округления.

Определение

Пусть \( \mathbb{F}_q \) — конечное поле порядка \( q = p^m \), где \( p \) — простое число. Пусть \( \omega \in \mathbb{F}_q \) — примитивный корень степени \( n \) из единицы, то есть \( \omega^n = 1 \) и \( \omega^k \neq 1 \) для всех \( 1 \leq k < n \). Необходимым условием существования такого \( \omega \) является то, что \( n \) делит \( q-1 \) (порядок мультипликативной группы поля). Преобразование Фурье над конечным полем для вектора \( \mathbf{a} = (a_0, a_1, \ldots, a_{n-1}) \in \mathbb{F}_q^n \) определяется как вектор \( \mathbf{A} = (A_0, A_1, \ldots, A_{n-1}) \), где

\[ A_k = \sum_{j=0}^{n-1} a_j \, \omega^{jk}, \quad k = 0, 1, \ldots, n-1. \]

Обратное преобразование задаётся формулой

\[ a_j = \frac{1}{n} \sum_{k=0}^{n-1} A_k \, \omega^{-jk}, \]

где \( 1/n \) — элемент, обратный к \( n \) по модулю \( q \) (поскольку характеристика поля не делит \( n \), \( n \neq 0 \) в \( \mathbb{F}_q \)).

Свойства

Основные свойства аналогичны свойствам классического дискретного преобразования Фурье, но с заменой поля комплексных чисел на конечное поле:

• Линейность: преобразование является линейным отображением \( \mathbb{F}_q^n \to \mathbb{F}_q^n \).
• Самосопряжённость (с точностью до масштабирования): двойное применение преобразования даёт \( A \mapsto n \cdot a \), где \( a = (a_0, a_1, \ldots, a_{n-1}) \).
• Свёртка: для циклической свёртки двух векторов выполняется свойство: преобразование свёртки равно поэлементному произведению преобразований.
• Обратимость: если \( n \) не делится на характеристику поля, то преобразование обратимо.

Виды и обобщения

Теоретико-числовое преобразование (ТЧП, NTT)

Частный случай, когда поле \( \mathbb{F}_q \) — простое поле \( \mathbb{F}_p \), где \( p \) — простое число. ТЧП широко применяется в криптографии, в частности в постквантовых криптосистемах на решётках (например, Kyber, Dilithium). Выбор подходящего простого числа \( p \) (например, \( p = 2^{64} - 2^{32} + 1 \) или \( p = 2^{256} - 2^{224} + 2^{192} - 2^{96} + 1 \)) позволяет реализовать быстрые вычисления с использованием модульного умножения.

Преобразование Фурье в полях характеристики 2

В полях \( \mathbb{F}_{2^m} \) (характеристика 2) существуют ограничения: примитивный корень степени \( n \) из единицы существует, только если \( n \) нечётно и делит \( 2^m - 1 \). Такие поля используются в теории кодирования (например, в кодах Рида — Соломона и БЧХ-кодах) и в криптографии (например, в симметричных шифрах на основе SP-сетей).

Преобразование Фурье на конечных кольцах

Существуют обобщения на конечные кольца (например, кольца вычетов по модулю \( 2^k \)), однако они не всегда обладают полными свойствами преобразования из-за отсутствия обратных элементов. В ряде приложений (ДПФ на целых числах) применяется арифметика в кольце \( \mathbb{Z}/m\mathbb{Z} \).

История

Идея использования конечных полей для преобразования Фурье восходит к работам конца XIX — начала XX века, однако систематическое исследование началось в середине XX века в связи с развитием теории кодирования. В 1960-х годах Ирвинг Рид и Густав Соломон применили преобразование Фурье над конечными полями для построения кодов, исправляющих ошибки. В 1970-х годах Джеймс Поллард и другие исследователи разработали теоретико-числовое преобразование как аналог быстрого преобразования Фурье (БПФ) в конечных полях. В 2010-х годах ТЧП стало ключевым компонентом в постквантовой криптографии.

Применение

Теория кодирования

Преобразование Фурье над конечными полями является основой для кодов Рида — Соломона, БЧХ-кодов, циклических кодов и кодов Гоппы. Например, кодирование Рида — Соломона заключается в вычислении дискретного преобразования Фурье от информационного вектора, а декодирование — в интерполяции в частотной области.

Криптография

• Постквантовая криптография: ТЧП используется в алгоритмах на основе колец (Ring-LWE) для ускорения умножения многочленов. Алгоритмы Kyber и Dilithium, прошедшие стандартизацию NIST, используют ТЧП для эффективных вычислений в кольце \( \mathbb{Z}_q[x]/(x^n+1) \).
• Криптосистемы на решётках: ТЧП позволяет реализовать умножение многочленов с сложностью \( O(n \log n) \) вместо \( O(n^2) \).
• Симметричная криптография: некоторые конструкции хэш-функций и блочных шифров (например, SAFER) используют конечные поля и преобразования Фурье.

Обработка сигналов и цифровая связь

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

Компьютерная алгебра

ТЧП используется для быстрого умножения многочленов и целых чисел (алгоритм Шёнхаге — Штрассена, алгоритм Фюрера). В системах компьютерной алгебры (например, Mathematica, Maple) ТЧП реализован для вычислений в конечных полях.

Алгоритмы быстрого вычисления

Для вычисления преобразования Фурье над конечными полями используются модификации классического быстрого преобразования Фурье (БПФ) — алгоритмы Кули — Тьюки, Гуда — Томаса и другие. В конечных полях возможно применение только тех алгоритмов БПФ, которые не требуют деления на 2 (или на степени двойки) вне поля. Подходящие длины преобразования \( n \) должны быть делителями \( q-1 \). Наибольшее распространение получил алгоритм «бабочка» для степеней двойки, если в поле существует корень степени \( 2^k \).

Для случаев, когда \( n \) не является степенью двойки, применяют смешанные методы (алгоритм Блендима) или преобразование с произвольным основанием (Cooley — Tukey для составных чисел).

Интересные факты

• Теоретико-числовое преобразование может быть реализовано исключительно на целочисленной арифметике без использования вещественных чисел, что гарантирует точность вычислений и подходит для аппаратной реализации.
• Минимальное простое число, подходящее для ТЧП с длиной \( n=2^k \), — это \( p = 2^{64} - 2^{32} + 1 \), известное как «простое число Ноймана» (используется в проекте NTT-SEAL).
• В криптографии на решётках ТЧП применяется для уменьшения размера ключей и времени работы: по сравнению с наивным умножением многочленов, ускорение составляет до 100 раз для длин порядка 1024.
• Теоретико-числовое преобразование используется в алгоритме быстрого умножения больших чисел, реализованном в библиотеке GMP (GNU Multiple Precision Arithmetic Library).

Критика и ограничения

Основные ограничения преобразования Фурье над конечными полями связаны с необходимостью выбора подходящего поля и длины преобразования. Для длин \( n \), не делящих \( q-1 \), преобразование не существует. В ряде приложений (например, при работе с данными, длина которых не совпадает с делителем порядка мультипликативной группы) требуется дополнять данные или использовать расширение поля. Кроме того, ТЧП не подходит для анализа сигналов во временной области, где амплитуды могут быть вещественными числами, не принадлежащими конечному полю.

Источники

• Blahut R. E. «Algebraic Codes for Data Transmission» — Cambridge University Press, 2003.
• Pollard J. M. «The fast Fourier transform in a finite field» — Mathematics of Computation, 1971.
• Crandall R., Pomerance C. «Prime Numbers: A Computational Perspective» — Springer, 2005.
• Bernstein D. J., Buchmann J., Dahmen E. (eds.) «Post-Quantum Cryptography» — Springer, 2009.
• NIST. «FIPS 203 (ML-KEM), FIPS 204 (ML-DSA)» — 2024.
• «Теоретико-числовое преобразование в криптографии» — лекции НИУ ВШЭ, 2021.