フーリエ変換を使って高速になるのは桁数がある程度以上大きくなってからでしょう。
だからまずフーリエ変換を使わないプログラムを作るべきでは？