FFTを使った高速な掛算はここでみかけたよ

   最速の素数判定アルゴリズム 
http://piza2.2ch.net/test/read.cgi/tech/993457354/