Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

NTT(数論変換)を使って2つの多項式の積を求めるプログラム

Python

「『アルゴリズムC 第3巻』の「41 高速フーリエ変換」をPythonで」、「FFTを使って2つの多項式の積を求めるプログラム」に引き続き、NTT(数論変換)を使って2つの多項式の積を求めるプログラムを作ってみました。

2つの多項式の積を求めるプログラム(convolution_ntt.py)

実行結果

p(x) = 1 + x + x^{2} , q(x) = 2 - x + x^{2} のとき、 r(x) = p(x) * q(x)を求めてみます。 実行結果は以下の通りです。当然ですが、FFTを使ったものと同じ結果となっています。

% python convolution_ntt.py
1 1 1
2 -1 1
2
1
2
0
1

参考