Быстрая свертка над небольшими конечными полями

Каковы наиболее известные методы циклической свертки длины над небольшим полем, т.е. когда | F | « П ? Меня особенно интересуют поля постоянного размера или даже . Общие утверждения и ссылки об асимптотической эффективности высоко ценятся.$n$$|\mathbb{F}| \ll n$$\mathbb{F} = \mathbb{F}_2$

Фон: Пусть - поле, а . Мы думаем, что векторы имеют координаты, индексированные с помощью .$\mathbb{F}$$n > 0$$u \in \mathbb{F}^n$$\mathbb{Z}_n$

(Циклическая) свертка длина над является преобразование с и вывод , определяемый с индексной арифметикой над Z n .$n$$\mathbb{F}$$u, v \in \mathbb{F}^n$$u * v \in \mathbb{F}^n$

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

Для небольших конечных полей ДПФ не определено, потому что нет примитивного корня из единицы. Можно обойти это, вложив ∗ задачу в большее конечное поле, но не ясно, что это лучший способ продолжить. Даже если мы пойдем по этому пути, было бы неплохо узнать, кто-то уже проработал детали (например, выбирая, какое поле большего размера использовать и какой алгоритм FFT применять).$n$$^*$

Добавлено:

Под «вложением» нашей свертки я подразумеваю одну из двух вещей. Первый вариант: можно перейти к полю расширения, в котором соединены искомые примитивные корни единства, и выполнить там свертку. $^*$

Второй вариант: если наше начальное поле является циклическим, можно перейти к циклическому полю с большей характеристикой - достаточно большой, чтобы, если мы рассмотрим наши векторы как лежащие в F p ′ , никакого «обтекания» не произошло. (Я неформален, но просто подумайте о том, как, для вычисления свертки над F 2 , мы можем просто сделать ту же свертку над Z , а затем взять ответы mod 2.)$\mathbb{F}_{p'}$$\mathbb{F}_{p'}$
$\mathbb{F}_2$$\mathbb{Z}$

Также добавлено:

Многие алгоритмы для БПФ и связанных задач особенно хорошо работают для «хороших» значений (и я хотел бы лучше понять ситуацию с этим). $n$

Но если не пытаться воспользоваться специальными значениями , проблема циклической свертки в основном эквивалентна (посредством простых сокращений, включающих линейное раздувание по n ) обычной орбиты; это в свою очередь эквивалентно умножению многочленов с коэффициентами по F p . $n$$n$$\mathbb{F}_p$

По этой эквивалентности, можно использовать результаты, например, этот документ из фона цур Gathen и Gerhard (на основе работы Cantor), которые используют подход расширения поля , чтобы получить сложность схемы границы . Они не формулируют свои границы особенно четко IMO, но граница хуже, чем n ⋅ log 2 n, даже для F 2 . Можно ли сделать лучше?$\tilde{O}_p(n)$$n \cdot \log^2 n$$\mathbb{F}_2$

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

можно умножить два градусов- п полиномы над произвольным полем F с использованием O ( п войти п ) умножения в F и O ( п войти п войти лог п ) дополнения в F . Первоначально это связано с Schonhage-Strassen (для char. ≠ 2 ) и Schonhage для char. 2. Как я уже говорил, это подразумевает те же оценки для циклической свертки. Поспелов также заявляет: «В настоящее время нам неизвестны какие-либо алгоритмы с верхней границей [вышеупомянутых], которые не основаны на последовательных приложениях DFT ...»$\bullet$$n$$\mathbb{F}$$O(n \log n)$$\mathbb{F}$$O(n \log n \log \log n)$$\mathbb{F}$$\neq 2$

Кантор и Kaltofen обобщил эти результаты, показывающие границы для произвольных алгебр (не только поля).$\bullet$

Если F поддерживает дискретное преобразование Фурье соответствующего порядка, то есть, если F имеет примитивный N-й корень из единицы, где N достаточно велико (я считаю, что N = O ( n ) достаточно), а N - степень 2 или 3 , тогда мы можем сделать полиномиальное умножение с O ( n ) умножениями и O ( n log n ) сложениями. Различные другие улучшения возможны для полей с другими специальными свойствами.$\bullet$$\mathbb{F}$$\mathbb{F}$$N$$N$$N = O(n)$$N$$O(n)$$O(n \log n)$

Кажется правдоподобным, но неизвестным, может ли недавнееулучшениеФьюреромцелочисленного умножения (по-другому подтвержденное Де и др.) Помочь привести к более быстрым алгоритмам умножения полиномов, скажем, по конечным полям. Кто-нибудь может прокомментировать?$\bullet$

Тодд Mateer в диссертации также кажется, отличный ресурс , чтобы понять FFT литературы и приложения для умножения полиномов (спасибо Кувшин!); но вы должны копать больше, чтобы найти то, что вы ищете.