数論変換

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /number-theoretical-transform#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /number-theoretical-transform#noredirect を利用してください。
name
数論変換
short description
数論変換とは、特定の素数 $p$ による剰余環 $\mathbb{Z}/p\mathbb{Z}$ の上で行われる離散Fourier変換と同様の変換のこと、あるいはこの変換を高速Fourier変換と同様に $O(n \log n)$ で行うアルゴリズムのことである。