정수론적 변환 (Number Theoretic Transform, NTT) 은 고속 푸리에 변환 을 복소수가 아닌 정수 위에서 하는 연산입니다.
주기가 $T$인 정수열 $\{a_{n}\}$을 다음과 같은 정수열 $\{A_{n}\}$으로 바꾸는 연산입니다.
소수 $p = d \times 2^s + 1$, $p$의 원시근 $w$, $g = w^{\frac{p - 1}{T}}$라 할 때, NTT 연산을 다음과 같이 정의합니다.
정수론적 변환 (Number Theoretic Transform, NTT) $$ A_{n} = \left(\sum_{k = 0}^{T - 1} a_{k} g^{kn}\right)\mod{p} $$이산 푸리에 변환의 정의를 다시 보겠습니다.
$$ A_{n} = \sum_{k = 0}^{T - 1} a_{k} e^{i \frac{- 2 \pi k n}{T}} $$고속 푸리에 변환에서 분할 정복을 할 때, 복소수의 여러 성질 중 다음 네 가지 성질 $$ \begin{align} e^{i \frac{- 2 \pi \left(k + \frac{T}{2}\right) n}{T}} & = -e^{i \frac{- 2 \pi k n}{T}} \\ {\left(e^{i \frac{- 2 \pi k n}{T}}\right)}^{2} & = e^{i \frac{- 2 \pi k n}{T / 2}} \\ {\left(e^{i \frac{- 2 \pi k n}{T}}\right)}^{T} & = 1 \\ e^{i \frac{- 2 \pi k}{T}} & \not= 1 \left(0 < k < T \right) \end{align} $$ 임을 이용해서 분할 정복을 할 수 있었습니다.
페르마의 소정리 (Fermat’s little Theorem)$a$가 4번째 성질을 만족시키려면 위수 가 $p - 1$이면 된다는걸 알 수 있습니다. 따라서 $a$는 $p$의 원시근 이어야 합니다.
소수 $p$와 자연수 $a$가 서로소 이면 $a^{p - 1} \equiv 1 \pmod{p}$ 이다.
정수론적 변환 (Number Theoretic Transform, NTT) $$ A_{n} = \left(\sum_{k = 0}^{T - 1} a_{k} g^{kn}\right)\mod{p} $$이산 푸리에 역변환처럼 정의해도 되는지 보겠습니다.
정수론적 역변환 (Inverse Number Theoretic Transform, INTT) $$ \begin{align} a_{n} & = \frac{1}{T} \sum_{k = 0}^{T - 1} A_{k} g^{-kn} \mod{p} \\ & = T^{-1} \sum_{k = 0}^{T - 1} A_{k} {\left(g^{-1}\right)}^{kn} \mod{p} \end{align} $$$a^{-1} \mod p$는 법 $p$에서의 $a$의 모듈러 곱셈 역원 입니다.
$\{A_{n}\}$의 정의인 $A_{n} = \left(\sum\limits_{k = 0}^{T - 1} a_{k} g^{kn}\right)\mod{p}$에서 $\sum\limits_{k = 0}^{T - 1} A_{k} g^{-kn} \mod{p}$ 를 계산해보면 된다.
어떤 수열 $\alpha_{n}$을 $\alpha_{n} = \sum\limits_{k = 0}^{T - 1} A_{k} g^{-kn} \mod{p}$ 이라 하자.
$$
\begin{align}
\alpha_{n} & = \sum_{k = 0}^{T - 1} A_{k} g^{-kn} \mod{p} \\
& = \sum_{k = 0}^{T - 1} g^{-kn} A_{k} \mod{p} \\
& = \sum_{k = 0}^{T - 1} g^{-kn} \left( \sum_{m = 0}^{T - 1} a_{m} g^{mk} \right) \mod{p} \\
& = \sum_{k = 0}^{T - 1} \left( \sum_{m = 0}^{T - 1} a_{m} g^{-nk} g^{mk} \right) \mod{p} \\
& = \sum_{k = 0}^{T - 1} \left( \sum_{m = 0}^{T - 1} a_{m} g^{(m - n)k} \right) \mod{p} \\
& = \sum_{k = 0}^{T - 1} \sum_{m = 0}^{T - 1} a_{m} g^{(m - n)k} \mod{p} \\
& = \sum_{m = 0}^{T - 1} \sum_{k = 0}^{T - 1} a_{m} g^{(m - n)k} \mod{p} \\
& = \sum_{m = 0}^{T - 1} \left( \sum_{k = 0}^{T - 1} a_{m} g^{(m - n)k} \right) \mod{p} \\
& = \sum_{m = 0}^{T - 1} \left( a_{m} \times \sum_{k = 0}^{T - 1} g^{(m - n)k} \right) \mod{p}
\end{align}
$$
이제 $\sum\limits_{m = 0}^{T - 1} \left( a_{m} \times \left( \sum\limits_{k = 0}^{T - 1} g^{(m - 1) k} \right) \right) \mod{p}$의 연산만 해주면 된다.
편의상 $g^{m - n} \mod{p} = G$라 하자. $G \not= 1$이라면 $\sum\limits_{k = 0}^{T - 1} g^{(m - n)k} \equiv \sum\limits_{k = 0}^{T - 1} G^{k} \equiv \frac{G^{T} - 1}{G - 1} \pmod{p}$이고, $G^{T} \equiv g^{(m - n) T} \equiv w^{\frac{p - 1}{T} (m - n) T} \equiv w^{(p - 1) (m - n)} \equiv 1^{m - n} \equiv 1 \pmod{p}$이므로, $G^{T} - 1 \equiv 0 \pmod{p} $이다.
$G = 1$인 경우는 $m = n$인 경우이므로, $m = n$일 때는 $\sum\limits_{k = 0}^{T - 1} g^{(m - n)k} \equiv \sum\limits_{k = 0}^{T - 1} 1^{k} \equiv \sum\limits_{k = 0}^{T - 1} 1 \equiv T \pmod{p}$이다.
$\sum\limits_{k = 0}^{T - 1} g^{(m - n)k}$ 을 통째로 $g_{m}$이라는 수열로 보면,
$$
g_{n}=
\begin{cases}
T & m = n \\
0 & m \not= n
\end{cases}
$$
이므로, $\sum\limits_{m = 0}^{T - 1} \left( a_{m} \times \sum\limits_{k = 0}^{T - 1} g^{(m - n)k} \right) \mod{p} = \sum\limits_{m = 0}^{T - 1} \left( a_{m} \times g_{m} \right) \mod{p}$에서, $g_{m}$의 성질로 인해
$$
a_{m} \times g_{m}=
\begin{cases}
Ta_{n} & m = n \\
0 & m \not= n
\end{cases}
$$
이므로, $\sum\limits_{m = 0}^{T - 1} \left( a_{m} \times g_{m} \right) \mod{p} = T a_{n} \mod{p}$ 이다.
따라서, $T a_{n} \mod{p} = \alpha_{n} \mod{p} = \sum\limits_{k = 0}^{T - 1} A_{k} g^{-kn} \mod{p}$에서 $a_{n} = \frac{1}{T} \sum\limits_{k = 0}^{T - 1} A_{k} g^{-kn} \mod{p}$ 이다.
이산 푸리에 변환의 합성곱 (Convolution) $$ c_{n} = \sum_{k = 0}^{T - 1} a_{k} b_{n - k} $$ 이면 $$ C_{n} = A_{n} B_{n} $$ 이다.수열 $\{b_{n}\}$의 주기가 $T$이므로, $c_{n}$의 정의중 $b_{n - k}$에서 $n - k$가 음수일 때는 $b_{0} = b_{T}$, $b_{-1} = b_{T - 1}$...로 생각하면 됩니다. ($b_{(n - k) \pmod{T}}$) NTT에서도 이와 똑같이 정의할 수 있습니다.
NTT에서의 합성곱 (Convolution) $$ c_{n} = \sum_{k = 0}^{T - 1} a_{k} b_{n - k} $$ 이면 $$ C_{n} = A_{n} B_{n} $$ 이다.NTT에서의 정당성도 한번 짚고 가겠습니다.
$$
\begin{align}
C_{n} & = \sum_{k = 0}^{T - 1} c_{k} g^{kn} \mod{p} \tag{1} \\
& = \sum_{k = 0}^{T - 1} \left(\sum_{m = 0}^{T - 1} a_{m} b_{k - m}\right) g^{kn} \mod{p} \tag{2} \\
& = \sum_{k = 0}^{T - 1} \sum_{m = 0}^{T - 1} a_{m} b_{k - m} g^{(k - m)n} g^{mn} \mod{p} \tag{3} \\
& = \sum_{m = 0}^{T - 1} \sum_{k = 0}^{T - 1} a_{m} b_{k - m} g^{(k - m)n} g^{mn} \mod{p} \tag{4} \\
& = \sum_{m = 0}^{T - 1} a_{m} g^{mn} \sum_{k = 0}^{T - 1} b_{k - m} g^{(k - m)n} \mod{p} \tag{5}\\
& = \sum_{m = 0}^{T - 1} a_{m} g^{mn} B_{n} \mod{p} \tag{6}\\
& = B_{n} \sum_{m = 0}^{T - 1} a_{m} g^{mn} \mod{p} \tag{7}\\
& = A_{n} B_{n} \mod{p} \tag{8}
\end{align}
$$
$(1)$번식 증명 : NTT의 정의
$g^{tn} = f(t)$ 라 하면, $f(t + T) \mod{p} = f(t) \mod{p}$ 라는 것을 알 수 있다.
$(1) \to (2)$ 증명 : 수열 $\{c_{n}\}$의 정의
$(2) \to (3)$ 증명 : 지수법칙 사용, $g^{kn} = g^{(k - m)n} g^{mn}$
$(3) \to (4)$ 증명 : 합 순서 변경
$(4) \to (5)$ 증명 : $k$와 관계 없는 항인 $a_{m} g^{mn}$ 항을 옮겨줌
$(6) \to (7)$ 증명 : $m$과 관계 없는 항인 $B_{n}$ 항을 옮겨줌
$(7) \to (8)$ 증명 : NTT의 정의에 의해 $A_{n} = \sum\limits_{m = 0}^{T - 1} a_{m} g^{mn} \mod{p}$
$(5) \to (6)$ 증명
또, $\{b_{n}\}$은 주기가 $T$이므로, $b_{n + T} = b_{n}$이다.
따라서, $b_{n} f(n) = \mathbb{B}_{n}$ 이라 하면, $\mathbb{B}_{n + T} \mod{p} = \mathbb{B}_{n} \mod{p}$이다.
$\sum\limits_{k = 0}^{T - 1} b_{k - m} g^{(k - m)} \mod{p}$ 에서 $K = k - m$으로 치환하면 $\sum\limits_{k = -m}^{T - 1 - m} b_{K} g^{Kn} \mod{p} = \sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} \mod{p}$임을 알 수 있다.
$\mathbb{B}_{n} \mod{p}$의 주기성에서 $\mathbb{B}_{-m} \mod{p} = \mathbb{B}_{-m + T} \mod{p}$임을 알 수 있다.
따라서 $\sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} \mod{p} = \sum\limits_{k = -m + 1}^{T - m} \mathbb{B}_{K} \mod{p}$이고, 마찬가지로 $\sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} \mod{p} = \sum\limits_{k = -m + 1}^{T - m} \mathbb{B}_{K} \mod{p} = \sum\limits_{k = -m + 2}^{T - m + 1} \mathbb{B}_{K} \mod{p} = \cdots$ 이므로, $\sum\limits_{k = -m}^{T - 1 - m} \mathbb{B}_{K} \mod{p} = \sum\limits_{k = 0}^{T - 1} \mathbb{B}_{K} \mod{p}$ 임을 알 수 있다.
$\mathbb{B}_{K}$의 정의에서 $\sum\limits_{k = 0}^{T - 1} \mathbb{B}_{K} \mod{p} = \sum\limits_{k = 0}^{T - 1} b_{K} g^{Kn} \mod{p}$이고, NTT의 정의에 의해 $B_{n} \mod{p} = \sum\limits_{k = 0}^{T - 1} b_{K} g^{Kn} \mod{p}$이다.
두 수열 $\{a_{n}\}$, $\{b_{n}\}$의 길이가 각각 $T_{a}$, $T_{b}$이다.
$2^{L - 1} \leq T_{a} + T_{b} - 1 < 2^{L}$인 자연수 $L$에 대하여 $T_{ab} = 2^{L}$이라 정의한다.
$L \leq s$인 자연수 $s$에 대해 $d \times 2^s + 1$꼴의 소수를 찾아 $p = d \times 2^s + 1$이라 하고, $w$는 $p$의 원시근이라 한다.
$g = w^{\frac{p - 1}{T_{ab}}}$라 하자.
두 수열 $\left\{a^{'}_{n}\right\}$, $\left\{b^{'}_{n}\right\}$를
$$
a^{'}_{n} =
\begin{cases}
a_{n} & 0 \leq n < T_{a} \\
0 & T_{a} \leq n < T_{ab}
\end{cases}
\\
b^{'}_{n} =
\begin{cases}
b_{n} & 0 \leq n < T_{b} \\
0 & T_{b} \leq n < T_{ab}
\end{cases}
$$
이라 정의한다.
$$
\begin{align}
A^{'}_{n} &= f_{a^{'}}\left(g^{n}\right) \\
B^{'}_{n} &= f_{b^{'}}\left(g^{n}\right) \\
C^{'}_{n} &= A^{'}_{n} B^{'}_{n} \\
c^{'}_{n} &= \frac{1}{T_{ab}} \sum\limits_{k = 0}^{T_{ab} - 1} C^{'}_{k} g^{k n} \mod{p}
\end{align}
$$
이라 한다.
NTT를 활용한 다항식 곱셈
다항식 $f_{c^{'}}(x) = \sum\limits_{k = 0}^{T_{ab} - 1} c^{'}_{k} x^{k} \mod{p}$에 대하여, $$ f_{c^{'}}(x) = f_{a}(x) f_{b}(x) \mod{p} $$ 이다.
다항식 $f_{c^{'}}(x)$는 $0 \leq n < T_{ab}$인 $T_{ab}$개의 자연수 $n$에 대하여 점
$$
\left(g^{kn} \mod{p}, f_{c^{'}}\left(g^{kn}\right) \mod{p} \right) = \left(g^{kn} \mod{p}, f_{a^{'}}\left(g^{kn}\right) f_{b^{'}}\left(g^{kn}\right) \mod{p} \right)
$$
를 지난다. ($f_{c^{'}}(x)$의 NTT 결과가 $C^{'}$이므로)
$f_{a^{'}}(x) = \sum\limits_{k = 0}^{T_{ab} - 1} a^{'}_{k} x^{k} = \sum\limits_{k = 0}^{T_{a} - 1} a_{k} x^{k} + \sum\limits_{k = T_{a}}^{T_{ab} - 1} 0 x^{k}$ 에서 $f_{a^{'}}(x) = f_{a}(x)$이고, 마찬가지로 $f_{b^{'}}(x) = f_{b}(x)$ 이다.
다항식 $f_{a}(x) f_{b}(x)$도 $0 \leq n < T_{ab}$인 $T_{ab}$개의 점
$$
\left(g^{kn} \mod{p}, f_{a^{'}}\left(g^{kn}\right) f_{b^{'}}\left(g^{kn}\right) \mod{p} \right)
$$
를 지나고, 서로 다른 점 $T_{ab}$개를 지나는 $T_{ab} - 1$차 이하의 다항식은 유한체 $\mathbb{Z}/p\mathbb{Z}$에서 유일하므로, $f_{c^{'}}(x) = f_{a}(x) f_{b}(x)$이다.
| $d$ | $s$ | $w$ | $p$ | $w^d \mod{p}$ | $w^{-1} \mod{p}$ | $w^{-d} \mod{p}$ |
|---|---|---|---|---|---|---|
| $1$ | $16$ | $3$ | $65537$ | $3$ | $21846$ | $21846$ |
| $9$ | $17$ | $19$ | $1179649$ | $612074$ | $310434$ | $1093705$ |
| $3$ | $18$ | $11$ | $786433$ | $1331$ | $71494$ | $104582$ |
| $11$ | $19$ | $3$ | $5767169$ | $177147$ | $1922390$ | $5087924$ |
| $7$ | $20$ | $3$ | $7340033$ | $2187$ | $2446678$ | $4665133$ |
| $11$ | $21$ | $3$ | $23068673$ | $177147$ | $7689558$ | $17187657$ |
| $25$ | $22$ | $3$ | $104857601$ | $39193363$ | $34952534$ | $96987805$ |
| $45$ | $23$ | $7$ | $377487361$ | $48510621$ | $53926766$ | $225915792$ |
| $45$ | $24$ | $11$ | $754974721$ | $739831874$ | $617706590$ | $337633511$ |
| $5$ | $25$ | $3$ | $167772161$ | $243$ | $55924054$ | $114609789$ |
| $7$ | $26$ | $3$ | $469762049$ | $2187$ | $156587350$ | $410692747$ |
| $15$ | $27$ | $31$ | $2013265921$ | $440564289$ | $64944062$ | $1713844692$ |
| $13$ | $28$ | $3$ | $3489660929$ | $1594323$ | $1163220310$ | $2734066009$ |
| $23$ | $29$ | $5$ | $12348030977$ | $4021541578$ | $4939212391$ | $5290438504$ |
| $3$ | $30$ | $5$ | $3221225473$ | $125$ | $1932735284$ | $2267742733$ |
| $35$ | $31$ | $3$ | $75161927681$ | $7938142057$ | $25053975894$ | $46246304432$ |
| $43$ | $32$ | $3$ | $184683593729$ | $141405485920$ | $61561197910$ | $183418192969$ |
| $9$ | $33$ | $7$ | $77309411329$ | $40353607$ | $22088403237$ | $29404248714$ |
| $75$ | $34$ | $11$ | $1288490188801$ | $1068548069718$ | $585677358546$ | $801409537127$ |
| $59$ | $35$ | $3$ | $2027224563713$ | $1609812002788$ | $675741521238$ | $378806922473$ |
| $3$ | $36$ | $29$ | $206158430209$ | $24389$ | $191940607436$ | $96566235053$ |
| $15$ | $37$ | $7$ | $2061584302081$ | $624392905781$ | $589024086309$ | $1425448486409$ |
| $15$ | $38$ | $7$ | $4123168604161$ | $624392905782$ | $2356096345235$ | $2412372849595$ |
| $5$ | $39$ | $3$ | $2748779069441$ | $243$ | $916259689814$ | $1504475786978$ |
| $27$ | $40$ | $5$ | $29686813949953$ | $21526276223809$ | $17812088369972$ | $18006105348939$ |
| $3$ | $41$ | $5$ | $6597069766657$ | $125$ | $2638827906663$ | $4327677766927$ |
| $9$ | $42$ | $5$ | $39582418599937$ | $1953125$ | $15832967439975$ | $4301541126489$ |
| $9$ | $43$ | $5$ | $79164837199873$ | $1953125$ | $47498902319924$ | $6933593367512$ |
| $15$ | $44$ | $7$ | $263882790666241$ | $4747561509943$ | $150790166094995$ | $239736939256064$ |
| $35$ | $45$ | $3$ | $1231453023109121$ | $773424174634867$ | $410484341036374$ | $208286993116953$ |
| $19$ | $46$ | $3$ | $1337006139375617$ | $1162261467$ | $445668713125206$ | $336753105592489$ |
| $27$ | $47$ | $5$ | $3799912185593857$ | $2752713159868405$ | $1519964874237543$ | $269794701738915$ |
| $15$ | $48$ | $19$ | $4222124650659841$ | $2588910752669904$ | $888868347507335$ | $1485469947503615$ |
| $23$ | $49$ | $3$ | $12947848928690177$ | $94143178827$ | $4315949642896726$ | $4460024686959799$ |
| $7$ | $50$ | $11$ | $7881299347898369$ | $19487171$ | $2865927035599407$ | $5559776568448599$ |
| $17$ | $51$ | $3$ | $38280596832649217$ | $129140163$ | $12760198944216406$ | $2832039383871320$ |
| $7$ | $52$ | $3$ | $31525197391593473$ | $2187$ | $10508399130531158$ | $19950102053024859$ |
| $51$ | $53$ | $5$ | $459367161991790593$ | $80192803784321279$ | $275620297195074356$ | $307418753427180931$ |
| $49$ | $54$ | $5$ | $882705526964617217$ | $714226840388367097$ | $353082210785846887$ | $508847234508336333$ |
| $5$ | $55$ | $11$ | $180143985094819841$ | $161051$ | $49130177753132684$ | $85639728600348284$ |
| $27$ | $56$ | $5$ | $1945555039024054273$ | $1613915479851665306$ | $1167333023414432564$ | $683686979196907739$ |
| $29$ | $57$ | $3$ | $4179340454199820289$ | $68630377364883$ | $1393113484733273430$ | $182099332568824125$ |
| $99$ | $58$ | $5$ | $28534807239019462657$ | $6555687501740266902$ | $11413922895607785063$ | $5914918732875247220$ |
| $27$ | $59$ | $5$ | $15564440312192434177$ | $7450580596923828125$ | $6225776124876973671$ | $12567674493006399635$ |
| $31$ | $60$ | $3$ | $35740566642812256257$ | $617673396283947$ | $11913522214270752086$ | $33189111067701702701$ |
| $53$ | $61$ | $3$ | $122209679488325779457$ | $57242754621320239781$ | $40736559829441926486$ | $96774613726331518268$ |
| $105$ | $62$ | $17$ | $484227031934875729921$ | $109604375319535751935$ | $398775202769897659935$ | $146863698306593179364$ |
| $9$ | $63$ | $11$ | $83010348331692982273$ | $2357947691$ | $22639185908643540620$ | $16222047528773592307$ |