数論変換
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/10 05:38 UTC 版)
「離散フーリエ変換 (一般)」の記事における「数論変換」の解説
数論変換（number-theoretic transform, NTT、あるいは数論的変換）は、環を F = Z / p Z {\displaystyle F={\mathbb {Z} }/p{\mathbb {Z} }} に限定した場合の離散フーリエ変換である。pが素数ならば F {\displaystyle F} は有限体であり、単位元の原始n乗根は n が p − 1 {\displaystyle p-1} を割り切るとき、つまり、ある正の整数 ξ を用いて p = ξ n + 1 {\displaystyle p=\xi n+1} と書けるときには、必ず存在する。特に、単位元の原始(p-1)乗根が ω {\displaystyle \omega } であれば、原始n乗根は α = ω ξ {\displaystyle \alpha =\omega ^{\xi }} で得られる. 具体例） p = 5 {\displaystyle p=5} 、 n = 4 {\displaystyle n=4} 、 α = 2 {\displaystyle \alpha =2} の場合、 2 1 = 2 ( mod 5 ) 2 2 = 4 ( mod 5 ) 2 3 = 3 ( mod 5 ) 2 4 = 1 ( mod 5 ) {\displaystyle {\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}} [ F ( 0 ) F ( 1 ) F ( 2 ) F ( 3 ) ] = [ 1 1 1 1 1 2 4 3 1 4 1 4 1 3 4 2 ] [ f ( 0 ) f ( 1 ) f ( 2 ) f ( 3 ) ] {\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}} 数論変換は、法mが素数でない場合の環 Z / m Z {\displaystyle \mathbb {Z} /m\mathbb {Z} } においても、位数がnである主要根が存在するならば、意味がある。ショーンハーゲ・ストラッセン法で用いられるフェルマー数変換（m = 2k+1）や、メルセンヌ数変換（m = 2k − 1）のような特殊な数論変換は、法として合成数を用いている。
※この「数論変換」の解説は、「離散フーリエ変換 (一般)」の解説の一部です。
「数論変換」を含む「離散フーリエ変換 (一般)」の記事については、「離散フーリエ変換 (一般)」の概要を参照ください。
- 数論変換のページへのリンク
