Number Theoric Transform

概要

• RNS
• NTTは DFT の有限体への一般化
• 畳込みは大きな数や長い多項式の乗算に便利
• NTTはKaratsuba法より漸近的に高速.

Complex DFT

1. 入力は長さ $n$ の非負ベクトル $X$
2. 1の原始n乗根 $\omega =e^{\frac{2\pi i}{n}}$
3. 出力 $Y(k)$ は $X(0){\omega }^{0k}+X(1){\omega }^{1k}\cdots X(n-1){\omega }^{(n-1)k}$ となる
4. 逆変換は $X(k)n=Y(0){\omega }^{-0k}\cdots Y(n-1){\omega }^{-(n-1)k}$ で復元

Procedure for the NTT

1. 入力は非負ベクトル (サイズ $n$)
2. どの要素よりもおおきい $M$ を最小モジュラスとする
3. $N:=kn+1$ な 素数 $N$ をモジュラス ($N\ge M$) を選ぶ(ディリクレの定理により存在する)
4. $N$ 素数より乗法群 ${\mathbb{Z}}_N$ は位数 $N-1=kn$, 最低でも一つの生成元 $g$ があり $N-1$番目の原始根.
5. $\omega \equiv g^k(modN)$ を定義すると ${\omega }^n=g^{kn}=g^{N-1}\equiv 1(modN)$, $\omega$ は1の原始$n$乗根

::: info
別に $N$ は素数じゃなくてもいい $GF(2^8)$ とか
:::

例

1. $X=(6,0,10,7,2)$

2. $M=11$ とする

3. $k=2$ のとき $N=kn+1=11$, $N$ は素数で $N\ge M=11$

4. ${\mathbb{Z}}_{11}$ の根を探す.
   $N-1=2\times 5$ より
   $a=6$ のとき, $a^5\equiv 10\not\equiv 1mod11$ かつ $a^2\equiv 3\not\equiv 1mod11$ なので $g=6$

5. $\omega =g^k=6^2\equiv 3(mod11)$ 5番目の根

6. $Y$ を計算
   
   $Y=(8,0,6,2,10)$
   逆元 $n^{-1}=5^{-1}\equiv 9$ をかけると
   $(8,0,6,2,10)\times 9\equiv (6,0,10,7,2)$

畳込みの例

$X=(4,1,4,2,1,3,5,6)$
$Y=(6,1,8,0,3,3,9,8)$
$n=8$

1. $M=9^2\ast 8+1=649$
   (一桁($<10$)の掛け算が8個なのでmax:648)
2. $k=84$, $N=84\times 8+1=643$, $N$ 素数.
3. 8乗根をもとめたい,
   $643-1=2\ast 3\ast 107$ より??? $a=326$ とすると $a^8\equiv 1$ && $a^4\not\equiv 1$ なので $\omega =326$.
4. NTT変換
   $X^{\prime }=\mathrm{NTT}(\mathrm{X})=(26,338,228,115,2,457,437,448)$
   $Y^{\prime }=\mathrm{NTT}(\mathrm{Y})=(38,594,224,157,14,201,433,406)$.
5. 積は$mod649$ でpointer-wise multiplication
   $Z^{\prime }=X^{\prime }{Y}^{\prime }=(315,218,597,557,28,329,108,178)$
6. 逆NTT変換をして多項式の積を得る
   $Z=\mathrm{INTT}({\mathrm{Z}}^{\prime })=(123,120,106,92,139,144,140,124)$

参考文献

• https://www.nayuki.io/page/number-theoretic-transform-integer-dft