大きな整数の掛け算にはFFTを使うとよいのだそうだ。多項式の掛け算を考えればよい。 f(x) = a0 + a1x + ... + amxm g(x) = b0 + b1x + ... + bnxn 各項の係数は、畳込みで計算できる。畳込みはフーリエ変換すると単なる掛け算に変わる。これをまた逆変換す…