【NTT（数論変換）入門（１）】DFT（離散フーリエ変換）編

格子暗号の（高速化）の理解のためにはNTTが避けて通れない。何番煎じかと思われるかもしれないが、フーリエ変換系は多くの人が躓くポイントかと思うので（私も十分理解していないが）、わかりやすくまとめられると良いなと思う。 はじめに（全体像） まずNTTとは何かを述べる。簡単に言うとNTTはDFTの一般化である。DFTは複素（関）数を複素（関）数へ写す全単射写像であり、要は複素数の表現方法を変換するエンコード処理だとみなしてよいと思う。全単射なので逆写像IDFTが存在し、これはエンコードした複素数を元に戻すデコード処理と考えることができる。 なぜこのような変換が重要なのかというと、変換後のほうが複素数に対する演算を楽に行うことができるからだ。暗号的にはモンゴメリ乗算みたいなものである。工学的には、時間領域より周波数領域が扱いやすいとかという言い方になるが、数論的には値を指数表現することで乗算を加