W jakich pierścieniach można szybko wykonywać obliczenia i jak to robić.

NTT, czyli DFT w ciałach

NTT (Number Theoretic Transform) do Dyskretna Transformata Fouriera (DFT) w zastosowaniu do ciał skończonych. Transformata pozwala wykonywać splotu ciągów liczb całkowitych. Jest używana do wymnażania dużych liczb i wielomianów, ponieważ jest asymptotycznie szybsza niż mnożenie Karatsuby (stososwane do mnieszych liczb).

Opis za projektem Nayuki.

DFT

Najpierw przypomnijmy jak działa Dyskretna Transformata Fouriera. Przekształca ona na $n$-wymiarowe wektory liczb zespolonych w następujący sposób.

1. Niech $\omega$ będzie $n$-tym pierwiastkiem pierwotnym z jedynki ($\omega^n=1$ oraz $\omega^k \neq 1$ dla k<n). Zwykle przyjmuje się $\omega = e^{-2\pi i/n}$.

2. Wektor wyjściowy $Y$ jest obliczany na podstawie wektora wejściowego $X w następujący sposób:

\[Y(k) = X(0) \cdot \omega^{0} + X(1) \cdot \omega^{k} + \cdots X(n-1) \cdot \omega^{(n-1) \cdot k}.\]

1. Transformata odwrotna pozwala odzyskać oryginalny wektor $X$ na podstawie $Y$:

\[X(k) = \frac{1}{n} \left( Y(0) \cdot \omega^{-0} + Y(1) \cdot \omega^{-k} + \cdots Y(n-1) \cdot \omega^{-(n-1) \cdot k} \right).\]

Aby wymnożyć wielomiany, wektory ich współczynników przekształca się przy pomocy DFT, a następnie wymnaża wyjściowe wektory po współrzednych. A by uzyskać splot wielomianów, wynikowy wektor przekształcany jest przy pomocy transformaty odwrotnej.

NTT

NTT ciała analogicznie, ale używa pierwiastków pierwotnych z jedynki w ciałach skończonych.

1. Wybierz $M$ nwiększe od $n$ i wszystkich współczynników wektorów wejściwoych.

2. Wyberz liczbę całkowitą $k>1$ i ustal moduł $N = kn+1$, taki że $ N>M$ i $N$ jest liczbą pierwszą. Wiemy z Twierdzenia Dirichleta, że taki moduł istnieje dla pewnego $k$.

3. Dla pierwszego $N$ grupa multiplikatywna $\mathbb{Z}_N^{\star}$ ma $\varphi(N)=N-1=kn$ elementów. Grupa ma conajmniej jeden generator $g$ będący $(N-1)$ pierwiastkiem pierwotnym z 1.

4. Ustalmy $\omega = g^k \pmod{N}$. Wtedy $\omega^n = g^{kn} = g^{\varphi(N)} = 1$ (Twierdzenie Eulera). Ponieważ $g$ jest generatorem to wiemy, że $\omega^i \neq 1$ dla $i<n$. Stąd $\omega$ jest $n$-tym pierwiastkem pierwotnym z jedynki, tak jak chcieliśmy.

5. Resztę robimy dokładnie tak samo jak w DFT.

Jeżeli chcemy mnożeyć wielomiany, trzeba wybrać moduł conajmniej $M=m^2n+1$, aby uniknąć błędów przy redukcjach. Procedura jest opisana dla ciał skończnych, ale może być też stosowana dla pierścieni, pod warunkiem, że istnieje w nim $n$-ty pierwiastek pierwotny z jedynki.

Obliczanie NTT wymaga wielu modularnych redukcji. Warto stosować do tego szybkie algorytmy Montgomery’ego bądź Barretta.

Algorytm Cooleya-Tukeya i przyspieszenie

Algorytm Cooleya-Tukeya pozwala szybko obliczać transformatę DFT dla modułów będących potęgą dwójki. Transformacja używająca tego algorytmu nazywana jest Fast Fourier Transform (FFT).

NTT i cykliczne sploty

Opisana metoda pozwala wykonywać cykliczne sploty, czyli mnożyć wielomiany modulo $(x^n-1)$. W takim pierścieniu ilorazowym $x^ \equiv 1$, co odpowiada cyklicznemu zawinięciu współczynników.

NTT i wielomiany cyklotomiczne

NTT klasycznie liczy sploty cykliczne, a więc mnożenie modulo wielomian $(x^n-1)$. Można jednak wykonywać mnożenie modulo inne wielomiany. Brutalny sposób polega na zwiększeniu modułu, otrzymaniu niezredukowanego wielomianu, a następnie wykonania redukcji modularnej na wyniku. W niektórych przypadkach da się to jednak zrobić szybciej. W szczególności dla wielomianów cyklotomicznych stopnia $N=2^n$, które mają postać $x^{2^{n-1}}+1$, można wykonać szybkawersję transformacji stosując następujący trik.

mnożenie Karatsuby w ciałach

Mnożenie Karatsuby jest asymptotycznie wolniejsze od mnożenia wielomianów przy pomocy NTT. Jednak Bernstein i inni przy implementacji NTRU Prime używając mnożenia Karatsuby otrzymali konkurencyjne złożoności czasowe.