Теоре́тико-числово́е дискре́тное преобразова́ние Фурье́, преобразование вектора из $n$ элементов $x=(x_0, x_1, x_2, \ldots, x_{n-1})$ поля или ассоциативного коммутативного кольца с единицей $R$ (далее кольцо с единицей) в другой вектор $y=(y_0, y_1, y_2, \ldots, y_{n-1})$ из $n$ элементов того же поля или кольца по формуле $(1),$ которая зависит от выбора параметра $w_n$ – первообразного корня из единицы степени $n$ в $R$$$\tag{1}\text{ДПФ}_{R,n,w_n}:y_i =\sum_{j=0}^{n-1}{w_n}^{ij} x_j, \quad i = 0, 1, \dots, n-1.$$Определение первообразного корня $w_n$ из $1$ степени $n$ для теоретико-числового $\text{ДПФ}_{R,n,w_n}$ над полем или кольцом с единицей $R$ подобрано так, чтобы обобщался вывод формул для обратного дискретного преобразования Фурье над полем комплексных чисел. А именно, налагаемое в случае поля комплексных чисел условие:

для любого $k = 1, 2, \ldots , n-1$ число $(1-w^k)$ не равно $0,$

в общем случае заменяется на условие:

для любого $k = 1, 2, \ldots , n-1$ число $(1-w^k)$ не является делителем нуля в $R,\quad (2)$

и добавляется условие:

сумма $n$ единиц в $R$ обратима.$\quad (3)$

Явная формула преобразования, обратного к теоретико-числовому дискретному преобразованию Фурье, выводится следующим образом. Если $R$ – коммутативное ассоциативное кольцо с единицей, $w$ – первообразный корень из $1$ степени $n,$ т. е. выполнены условия $(2)$ и $(3),$ то прямым вычислением, аналогичным вычислению для случая комплексных чисел, можно проверить, что произведение матриц преобразований $\text{ДПФ}_{R,n,w}$ и $\text{ДПФ}_{R,n,\bar w},$ где $\bar w= w^{n-1}$ – элемент $R,$ обратный $w,$ является диагональной матрицей, в которой каждый диагональный элемент равен сумме $n$ единиц кольца $R.$ Поэтому обратное преобразование принимает вид $\hat n\,\text{ДПФ}_{R,n,\bar w},$ где $\hat n$ – элемент, обратный сумме $n$ единиц в $R,$ существующий в силу $(3).$

Для данного кольца с единицей или поля $R$ первообразный корень из $1$ степени $n$ существует не для всякого $n.$

Примеры:

а) Легко проверить, что для поля вычетов по модулю $5,$ вычет $2$ является первообразным корнем из $1$ степени $4,$ но не существует кубического первообразного корня из $1.$

б) В факторкольце $R=\Z/8\Z$ вычетов по модулю $8$ вычет $3$ является корнем квадратным из $1,$ но не является первообразным корнем степени $2$ по следующим причинам:

• нарушено условие $(2),$ ибо $1-3$ является делителем нуля в $R;$

• нарушено условие $(3),$ ибо сумма $1+1$ не обратима в $R.$

Далее, для квадратного корня из $1$ $w=3$ в кольце $R$ сумма степеней этого корня $1 + w$ равна вычету $4,$ отличному от нуля в $R.$ Поскольку эта сумма равна недиагональному элементу произведения матриц преобразований $\text{ДПФ}_{R,2,w}$ и $\text{ДПФ}_{R,2,\bar w},$ где $\bar w=w,$ это произведение оказывается недиагональной матрицей.

в) Для поля вычетов по простому модулю $p = 998244353 = 7\cdot17\cdot2^{23}+1$ вычет $31$ является первообразным корнем из $1$ степени $2^{23}.$