Tôi quen thuộc với Biến đổi Fourier và tính toán ma trận DFT và FFT để nhân nhanh các số nguyên. Tuy nhiên, đây là lần đầu tiên tôi làm việc với NTT áp dụng cho vành đa thức có dạng $\mathbb{Z}_q[x]/x^{n} + 1$.
Nói cho q nhỏ = 5 và $n$=2. Các phần tử của tôi bao gồm nhiều nhất là tất cả các đa thức bậc $n-1$ với các hệ số trong $\mathbb{Z}_{q}$. Tất cả số học của các hệ số được thực hiện trong $\mathbb{Z}_{q}$.
Bây giờ để có được $n$-th gốc nguyên thủy của sự thống nhất $w$: Tôi có thể biểu thị q = Nk + 1 = 22 + 1. Tôi có thể đặt kích thước mẫu NTT là N=2 và k=2. Tôi đặt r = 2 (là một căn nguyên thủy của q). tôi có thể tính toán w như $w = r^k \pmod{q}= 4 \pmod{5} = 4$
Và xác nhận $w^{k} \equiv 1 \pmod{q}$. $4^{2} = 16 \pmod{q} = 1$
Câu hỏi đầu tiên: phương pháp này để có được $w$ đúng?
Ma trận 2 nhân 2 của tôi sẽ có dạng này:
\begin{ma trận}
1 & 1\
1 & w
\end{ma trận}
Bây giờ, để xem xét các lũy thừa cao hơn của w, giả sử chúng ta đang làm việc với vành lớn hơn và có ma trận 3 nhân 3. Đặt NTT_matrix =
\begin{ma trận}
1 & 1 & 1 \
1 & w & w^2 \
1 & w^2 & w^3 \
\end{ma trận}
Câu hỏi thứ hai: để tính toán ma trận lùi, Đặt NTT_inv_matrix =
\begin{ma trận}
1 & 1 & 1 \
1 & w & w^{-2} \
1 & w^{-2} & w^{-3} \
\end{ma trận}
nhân với $N^{-1}$.
Để tính lũy thừa âm của $w$, tôi chỉ có thể lấy nghịch đảo nhân của
phần tử tương ứng trong ma trận chuyển tiếp và nhân chúng với $N^{-1}$ (nghịch đảo nhân của kích thước mẫu $N$)?
Vì vậy, ví dụ, giả sử tôi có mục này trong ma trận chuyển tiếp: $w^3 = 4^3 \pmod{5} = 64 \pmod{5} = 4$ Phần tử tương ứng trong ma trận lùi sẽ là $w^-3$. Để tính toán nó, cũng giống như $(w^{3})^{-1}\pmod{5}$?
trong trường hợp này là nghịch đảo nhân, MI, của $w^3\pmod{5}$ cũng sẽ là 4 vì $4*4 \equiv 1 \pmod{5}$. Và MI(N) trong mod 5 là 3 vì $3*2 \equiv 1 \pmod{5}$. Vì vậy, sau đó, để tính toán $w^{-3} = MI(w^{3})*MI(N) = 4 * 3 = 12 \pmod{5} = 2$?
Câu hỏi thứ ba:
Vì vậy, sau khi điền vào cả hai ma trận, tôi có thể nhân các đa thức a(x) và b(x) bằng cách lấy các bộ hệ số của chúng. Đối với mỗi đa thức, tôi tiến hành như sau:
Nếu a(x) = x + 3 = (a1=1, a0=3) thì bộ của nó chỉ là v = (1, 3). Tôi có thể áp dụng phép biến đổi thông qua phép nhân vector-ma trận v*NTT_matrix = v. Tương tự cho b(x) giả sử tôi nhận được v2. Sau đó, v3 = v`*v2 và cuối cùng, answer = NTT_inv_matrix(v3). Chính xác?
Câu hỏi thứ tư: Điều này sẽ cho tôi câu trả lời giống như nhân a(x)b(x) với tiêu chuẩn công thức tích chập Chính xác ?
Câu hỏi thứ năm, để xác định một chiếc nhẫn như vậy $\mathbb{Z}_q[x]/x^{n} + 1$, nó được yêu cầu rằng $q$ là số nguyên tố để đảm bảo nghịch đảo nhân cho tất cả các phần tử trừ 0 và cũng $x^{n} + 1$ phải bất khả quy trong $\pmod{q}$, Chính xác?
