多項式計算で、「FFTを使う」のは自力で思いつくのは不可能だろう。
多項式環の自己準同型で乗法の計算コストが最小になるのはフーリエ変換なのかは疑問のあるところ。
よりよい変換がある可能性は捨て切れない。
F : R[X] →　R[X] でF(x*y)=F(x)*F(y)が成り立ち、右辺の計算が相当簡単にできる写像。
こんな記事あり。



高速フーリエ変換 - Wikipedia
かつては実入力に対するフーリエ係数は離散ハートリー変換でより効率的に計算できると思われていた。
しかし、その後最適化された離散フーリエ変換アルゴリズムが、離散ハートリー変換アルゴリズムよりも必要とする演算回数を下まわることがわかった。
また、Bruun's FFTアルゴリズムは、はじめこそ実入力に対して有利といわれていたが、今ではそういわれてはいない。



ハートレー変換 - Wikipedia
数学の分野におけるハートレー変換は、フーリエ変換と非常に関係の深い、実数値関数を実数値関数へと写す積分変換である。
1942年、ラルフ・ハートレーによりフーリエ変換の代替的なものとして提唱された。
フーリエ変換と比較して、ハートレー変換には実関数を実関数へと変換し、逆変換がそれ自身となるという長所がある。