改めて調べてみたら、Toom3はO(N^1.5)くらいだった
O(NlogN)はSchönhage–Strassenだったか