Я знаком с преобразованием Фурье и вычислением матрицы ДПФ и БПФ для быстрого умножения целых чисел. Однако я впервые работаю с НТТ применительно к полиномиальным кольцам вида $\mathbb{Z}_q[x]/x^{n} + 1$.
Скажем, для малых q = 5 и $n$=2. Мои элементы состоят из всех многочленов степени не выше $n-1$ с коэффициентами в $\mathbb{Z}_{q}$. Вся арифметика коэффициентов производится в $\mathbb{Z}_{q}$.
Теперь, чтобы получить $n$-й первообразный корень из единицы $w$: я могу выразить q = Nк + 1 = 22 + 1. Я могу принять N=2 за размер выборки NTT и k=2. Я допускаю r = 2 (это первообразный корень из q). Я могу вычислить w как $w = r^k \pmod{q}= 4 \pmod{5} = 4$
и подтвердите $w^{k} \эквив 1 \pmod{q}$. $4^{2} = 16 \pmod{q} = 1$
Первый вопрос: этот метод получения $w$ правильно?
Моя матрица 2 на 2 будет иметь следующую форму:
\begin{матрица}
1 и 1\
1 и ш
\end{матрица}
Теперь, чтобы рассмотреть более высокие степени w, скажем, мы работаем с большим кольцом и имеем матрицу 3 на 3. Пусть NTT_матрица =
\begin{матрица}
1 и 1 и 1 \
1 & ш & ш ^ 2 \
1 и ш ^ 2 и ш ^ 3 \
\end{матрица}
Второй вопрос: чтобы вычислить обратную матрицу, пусть NTT_inv_matrix =
\begin{матрица}
1 и 1 и 1 \
1 & ш & ш ^ {- 2} \
1 & w^{-2} & w^{-3} \
\end{матрица}
умножается на $N^{-1}$.
Чтобы вычислить отрицательные степени $w$, я могу просто взять мультипликативную обратную
соответствующий элемент в прямой матрице и умножить их на $N^{-1}$ (мультипликативная величина, обратная размеру выборки $N$)?
Так, например, скажем, у меня есть эта запись в прямой матрице: $w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4$ Соответствующий элемент в обратной матрице будет $w^-3$. Чтобы вычислить это, то же самое, что и $(ш^{3})^{-1}\pmod{5}$?
в этом случае мультипликативная обратная, MI, из $w^3\pmod{5}$ также будет 4, так как $4*4 \экв 1 \pmod{5}$. И MI(N) по модулю 5 равен 3, так как $3*2 \экв 1 \pmod{5}$. Итак, чтобы вычислить $w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2$?
Третий вопрос:
Таким образом, после заполнения обеих матриц я могу умножать многочлены a(x) и b(x), взяв их кортежи коэффициентов. Для каждого многочлена я поступаю следующим образом:
Если a(x) = x + 3 = (a1=1, a0=3), то его кортеж — это просто v = (1, 3). Я могу применить преобразование через умножение матрицы на вектор v*NTT_matrix = v. То же самое для b(x), скажем, я получаю v2. Тогда v3 = v`*v2 и, наконец, answer = NTT_inv_matrix(v3). Правильный?
Четвертый вопрос: это должно дать мне тот же ответ, что и умножение a(x)b(x) на стандартный формула свертки правильный ?
Пятый вопрос, чтобы определить такое кольцо $\mathbb{Z}_q[x]/x^{n} + 1$, требуется, чтобы $q$ быть простым, чтобы обеспечить мультипликативную инверсию для всех элементов, кроме 0, а также $х^{п} + 1$ должен быть неприводимым в $\pmod{q}$, правильный?
