Sunt familiarizat cu Transformarea Fourier și cu calculul matricei DFT și FFT pentru multiplicarea rapidă a numerelor întregi. Cu toate acestea, aceasta este prima dată când lucrez cu NTT aplicat la inele polinomiale de formă $\mathbb{Z}_q[x]/x^{n} + 1$.
Să spunem pentru q=5 mic și $n$=2. Elementele mele constă cel mult din toate polinoamele de grad $n-1$ cu coeficienți în $\mathbb{Z}_{q}$. Toată aritmetica coeficienților se face în $\mathbb{Z}_{q}$.
Acum pentru a obține $n$-a rădăcină primitivă a unității $w$: Pot exprima q = Nk + 1 = 22 + 1. Pot lăsa N=2 dimensiunea eșantionului NTT și k=2. Am lăsat r = 2 (fie o rădăcină primitivă a lui q). Pot să calculez ca $w = r^k \pmod{q}= 4 \pmod{5} = 4$
si confirma $w^{k} \equiv 1 \pmod{q}$. $4^{2} = 16 \pmod{q} = 1$
Prima întrebare: această metodă de a obține $w$ este corect?
Matricea mea 2 cu 2 ar avea următoarea formă:
\begin{matrice}
1 & 1\
1 & w
\end{matrice}
Acum, pentru a lua în considerare puteri mai mari ale lui w, să presupunem că lucrăm cu un inel mai mare și că avem o matrice de 3 pe 3. Fie NTT_matrix =
\begin{matrice}
1 & 1 & 1 \
1 & w & w^2 \
1 și w^2 și w^3 \
\end{matrice}
A doua întrebare: pentru a calcula matricea inversă, fie NTT_inv_matrix =
\begin{matrice}
1 & 1 & 1 \
1 & w & w^{-2} \
1 și w^{-2} și w^{-3} \
\end{matrice}
înmulțit cu $N^{-1}$.
Pentru a calcula puterile negative ale $w$, pot lua doar inversul multiplicativ al
elementul corespunzător din matricea directă și înmulțiți-le cu $N^{-1}$ (inversul multiplicativ al mărimii eșantionului $N$)?
Deci, de exemplu, să spunem că am această intrare în matricea înainte: $w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4$ Elementul corespunzător din matricea înapoi ar fi $w^-3$. Pentru a-l calcula, este la fel ca $(w^{3})^{-1}\pmod{5}$?
în acest caz inversul multiplicativ, MI, al $w^3\pmod{5}$ ar fi tot 4 din moment ce $4*4 \equiv 1 \pmod{5}$. Și MI(N) în mod 5 este 3 din moment ce $3*2 \equiv 1 \pmod{5}$. Deci, pentru a calcula $w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2$?
A treia intrebare:
Deci, după ce populez ambele matrice, pot înmulți polinoamele a(x) și b(x) luând tuplurile lor coeficiente. Pentru fiecare polinom, procedez astfel:
Dacă a(x) = x + 3 = (a1=1, a0=3), deci tuplul său este doar v = (1, 3). Pot aplica transformarea prin multiplicarea matrice-vector v*NTT_matrix = v. Același lucru pentru b(x) să spunem că obțin v2. Apoi v3 = v`*v2 și în final, răspuns = NTT_inv_matrix(v3). Corect?
A patra întrebare: Acest lucru ar trebui să-mi dea același răspuns ca și înmulțirea a(x)b(x) cu standardul formula de convoluție corect ?
A cincea întrebare, pentru a defini un astfel de inel $\mathbb{Z}_q[x]/x^{n} + 1$, se cere ca $q$ fi prim pentru a asigura o inversă multiplicativă pentru toate elementele cu excepția lui 0 și, de asemenea $x^{n} + 1$ trebuie să fie ireductibil în $\pmod{q}$, corect?
