FFTを学ぶときに見かけるNTTって一体なんなの

前書き

regiです。この記事ではあくまでもNTT(数論変換)のみを取り上げるため、FFT(高速フーリエ変換)について全く知らない方でもある程度知っている方でも関係なく、ただNTTって何なのかだけざっくり押さえておきたい！と思っている方を対象としています。しかし、備忘録という意味合いが強いため、今のところでは細かい事や実装例等は取り上げていないのでご了承ください。その代わり、私が参考にさせて頂いた他の方のFFTやNTTに関する記事を適宜紹介したいと思っています。また、この記事内で誤った情報、誤字、誤植等を見かけた場合、直ちに訂正するのでTwitterで教えて欲しいです...お願いします🙏(TwitterID -> @Re_code_A)

FFTで用いられる数について

正確に言うと、FFTを行う際に行われるDFT(離散フーリエ変換)で用いられる数であり、 $\zeta _{N}$ という複素数が用いられています。 $N$ は必ず $2$ のべき乗とします。これは $1$ の原始 $N$ 乗根と呼ばれる $N$ 乗して初めて $1$ になる数のことであり、 $\cos \dfrac{2\pi }{N}+i\sin \dfrac{2\pi }{N}$ などが原始 $N$ 乗根に該当します。そもそもなぜこのような数がFFTで用いられているかというと、 $\zeta _{N}$ は重要な性質を持っているからであり、それは以下のようなものです。

$\zeta _{N}^{i}=\zeta _{N}^{i+N}$
$\sum ^{N-1}_{i=0}\zeta _{N}^{i\left( j-k\right)}=$ $\begin{cases}N\ \ \bf if \ \it \ j\equiv k \bf \ \ \ mod \it \ N\\0 \ \ \ \bf otherwise\end{cases}$

なぜこの性質は重要かというと、単純に、FFTはこのような性質を持つ数を用いることで行うことが可能になるからです。

複素数の概要及び上記の性質の証明等はこちらの記事が大変参考になりました。

https://qiita.com/ageprocpp/items/0d63d4ed80de4a35fe79

NTTとは

先ほど、FFTには $\zeta _{N}$ という複素数が用いられると言いましたが、この場合小数が出てくるために誤差を考慮する必要があるため、その点では複素数を扱うのは不便です。また、上記の性質を持つ数を用いることでFFTを行うことが可能になるとも言いましたが、これを言い換えると、この性質さえ持つ数であればFFTで用いる数として代用できるということで、つまり、上記の性質を満たした整数があるとすると、それを用いれば誤差に怯えることなくFFTを行うことができるということです。このような整数は特別な素数を法とすることで設けることができます。NTTとは、その特別な素数を法とした上で上記の性質を満たした整数を用いてFFTを行う手法のことです。

どのような素数や整数を用いるのか具体的に紹介すると、まず特別な素数とはある正の整数 $u,e$ を用いて $u×2^e+1$ と表すことのできる素数(以下 $pとする$ )であり、 $p$ を法とすると、 $2^e$ 乗して初めて $1$ と合同になる整数 $a$ を設けることができます。この $a$ は法 $p$ の下で以下のような性質を持っています。(ただし、 $N\leq 2^{e}$ であることが必要です。)

$a^{i}\equiv a^{i+N}$
$\sum ^{N-1}_{i=0}a^{i\left( j-k\right)}\equiv$ $\begin{cases}N\ \ \bf if \ \it \ j\equiv k \bf \ \ \ mod \it \ N\\0 \ \ \ \bf otherwise\end{cases}$

確かに $a$ はFFTを行うために必要な性質を持っていることが分かります。

証明等はこちらのパワーポイントが大変参考になりました。

https://hcpc-hokudai.github.io/archive/math_fft_002.pdf

少し余談ですが、プログラミングコンテスト等で見かける $998244353$ という謎の素数は、 $119×2^{23}+1$ と、 $e$ の十分大きい $u×2^e+1$ という形にすることができます。そのため、法 $998244353$ の下で解く問題とNTTを用いたFFTは相性が良いです。ちなみにこの場合は $3$ などが $a$ に該当します。