Обобщение Быстрого преобразование Фурье

[loldop]

Доброй ночи, форумчане!
Помогите разобраться с БПФ, точнее с его приложением в умножении Шёнхаге — Штрассена.

1) Представляем $157: x^2+5x+7$
$171: x^2+7x+1$, где $x=10$.
2) Перемножаем многочлены $x^2+5x+7$ и $x^2+7x+1$ с помощью быстрого преобразования Фурье.
3) Получаем $x^4+12x^3+43x^2+54x+7$.
4) Делая переносы через разряды, получаем $2x^4+6x^3+8x^2+4x+7$, то есть 26847.

Вопрос: как выполнить это умножение в соответствующих полях
-- комплексных чисел $\mathbb{C}$
-- вычетов по модулю $\mathbb{Z}_p$?

и еще вопрос:
как обобщить БПФ на $\mathbb{Z}_p$?

[loldop]

Up!