エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
離散フーリエ変換と数論変換 (5) 数論変換 (NTT)
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
離散フーリエ変換と数論変換 (5) 数論変換 (NTT)
この連載について離散フーリエ変換 (DFT) および数論変換 (NTT) の原理、そしてそれらのプログラミング... この連載について離散フーリエ変換 (DFT) および数論変換 (NTT) の原理、そしてそれらのプログラミングにおける実装方法について記述します。 各用語の定義の違いを明確にするため、それぞれについての回を分割します。 離散フーリエ変換 (DFT) 数列の畳み込み 高速フーリエ変換 (FFT) ビット反転置換 数論変換 (NTT) (本稿) NTT の高速化 中国剰余定理による値の復元 本文前回までに考察した複素数体$\mathbf{C}$上の離散フーリエ変換 (DFT) では、入力が整数であっても小数の演算が必要でした。 そこで今回は、入力が整数の場合には整数の演算のみで済むよう、何らかの整数の集合上でも前回までの理論が成り立たないかを検討します。 この結果として、数論変換 (number-theoretic transform, NTT) が得られます。 実用性を考慮すると、結論として