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

[SeerThe]

Добрый вечер!

Первый раз на этом форуме, просьба сильно не ругать оформление и постановку.

Итак, задача - реализовать умножение многочленов над произвольным конечным полем с FFT (Fast Fourier Transition). Собственно, само умножение происходит понятно - для многочленов $A(x), B(x)$, заданных векторами коэффициентов, получаем их преобразования $FFT(A(x)), FFT(B(x))$ - вектора значений в корнях из $1$. Почленно перемножаем преобразования и вычисляем от результата обратное преобразование Фурье (далее - iFFT).

Для понимания алгоритма использовал данную статью: http://www.cs.berkeley.edu/~fateman/282/readings/fftnotes.pdf - по сути, единственное более-менее внятное объяснение метода для случая конечных полей, что я нашел. Прямое преобразование сложностей не вызвало: многочлен $A(x) = a_0 + a_1 x + ... + a_{n-1} x^{n-1}$ представляется как $\begin{pmatrix} A(x_0)\\A(x_1)\\...\\A(x_{n-1})\end{pmatrix} = \begin{pmatrix} x_0^0& x_0^1& ...& x_0^{n-1}\\ x_1^0& x_1^1& ...& x_1^{n-1}\\ ...&...& ...& ...\\ x_{n-1}^0& x_{n-1}^1& ...& x_{n-1}^{n-1}\end{pmatrix} \cdot \begin{pmatrix}a_0\\a_1\\...\\a_{n-1}\end{pmatrix}$, если в качестве $(x_0, ..., x_{n-1})$ выбрать $(w^0, ..., w^{n-1})$, где $w$ - примитивный $n$-ный корень из единицы (т.е. $w^n = 1, w^k \neq 1, \forall k<n$), получим: $\begin{pmatrix} A(w^0)\\A(w^1)\\...\\A(w^{n-1})\end{pmatrix} = \begin{pmatrix} 1& 1& 1& ...& 1\\ 1& w& w^2&...& w^{n-1}\\ ...&...& ...&...& ...\\ 1& w^{n-1}& (w^{n-1})^2&...& (w^{n-1})^{n-1}\end{pmatrix} \cdot \begin{pmatrix}a_0\\a_1\\...\\a_{n-1}\end{pmatrix}$. По определению это и есть преобразование Фурье (все это описано по ссылке чуть более подробно, но суть такая). В статье утверждается, что для обратного преобразования используется аналогичный алгоритм, только вместо элемента $w$ используется $w^{-1}$, и появляется коэффициент $\frac{1}{n}$ - по сути, обратная матрица к исходной: $\frac{1}{n}\begin{pmatrix} 1& 1& 1& ...& 1\\ 1& w^{-1}& w^{-2}&...& w^{-(n-1)}\\ ...&...& ...&...& ...\\ 1& w^{-(n-1)}& (w^{-(n-1)})^2&...& (w^{-(n-1)})^{n-1}\end{pmatrix}$.Таким образом мы подошли к первому вопросу - что такое $\frac{1}{n}$? $n$ - натуральное число, длина вектора коэффициентов входного многочлена. Если вводить $n$ как сумму из $n$ единиц поля, то получим, что, в частности, для $GF(2^4)/(x^4+x+1)$ попытка вычислить $\frac{1}{n}$ приводит к обращению $0$ (при четных $n$)- дело неблагодарное, так как противоречит определению поля.
Далее, уже сам быстрый алгоритм использует дополнение степени многочлена до степени $2$ нулями - казалось бы, все здорово. Но не выйдет ли, что для больших $n$ и, соответственно, дополнений до степени $2$, не найдется примитивного корня единицы?

Заранее спасибо за ответы!

P.S.
Буду рад так же любой литературе по данному вопросу.

[Brukvalub]

А откуда берется уверенность, что БПФ всегда применимо к умножению многочленов над конечным полем? Ведь не над каждым конечным полем можно выполнить обратное преобразование Фурье заранее заданного порядка. Подробно, когда это можно делать и как делать, написано, например, в книге Joachim von zur Gathen, Jürgen Gerhard Modern computer algebra, и в других работах Joachim von zur Gathen. Полезно также ознакомиться с приемом, предложенным для преодоления трудностей Sxhonhage.

[SeerThe]

Brukvalub в сообщении #1123216 писал(а):

А откуда берется уверенность, что БПФ всегда применимо к умножению многочленов над конечным полем? Ведь не над каждым конечным полем можно выполнить обратное преобразование Фурье заранее заданного порядка. Подробно, когда это можно делать и как делать, написано, например, в книге Joachim von zur Gathen, Jürgen Gerhard Modern computer algebra, и в других работах Joachim von zur Gathen. Полезно также ознакомиться с приемом, предложенным для преодоления трудностей Sxhonhage.

Спасибо за ответ и литературу!
Ознакомился с книгой - как я понял, ограничения на применимость появляются из-за возможного отсутствия примитивных корней единицы нужного порядка. Однако остался вопрос касательно $\frac{1}{n}$ - в указанной книге описывается как $n \cdot 1_R$, где $1_R$ - единица поля $R$. Но, насколько я понимаю, при четном значении $n$ получится $0_R$ (для примера поля из первого сообщения темы). А сама суть алгоритма и сводится к тому, что многочлен дополняется нулями до степени $2^k$. Как тогда может работать обратное преобразование? Чувствую, что что-то упускаю, но понять пока не получается.

[RIP]

Для существования примитивного корня из 1 степени n необходимо, чтобы n не делилось на характеристику поля, потому что $x^{pm}-1=\left(x^{m}-1\right)^{p}$.