Во-первых - пусть A = B*C(в смысле полиномов) и мы посчитали FFT(B), FFT(C). Все значения в этих массивах меньше модуля. Потом мы должны скалярно перемножить (FFT(B), FFT(C)) и применить обратное FFT. Но когда мы перемножим - не все элементы этого массива уже будут меньше модуля - что с этим делать? просто брать их по тому же модулю и считать обратное? Если я так делаю, у меня начинает все неправильно работать(из-за таких переполнений), числа длиной около тысячи знаков умножаются правильно только при базе 10 или 100, что очень печально.

Во-вторых - пусть после FFT у нас получилось: FFT(A) = (1, 3), FFT(B) = (4, 0). После того как мы скалярно перемножим, у нас получится (4, 0), и после обратного FFT мы получим тот же B. Такое бывает(может я не понял чего-то в теории), и если да - что делать?

И последнее - модуль в статье на e-maxx подходит для случая, когда в векторе не более 2^20 элементов. Вряд ли мне понадобится больше - но вопрос - а где-то есть готовые последовательности типа "модуль - образующий элемент" ?. На oeis - только для небольших чисел, можно конечно прочитать и познать еще один алгоритм - но очень уж лень :)

Кстати - мне кажется, или на e-maxx единственная статья про целочисленное БПФ в интернете? Если есть еще что почитать(на русском или английском), очень буду рад ссылкам.

upd: еще на всякий случай код