Изменения

Для того чтобы получить произведение двух многочленов за время, меньшее чем <tex>O(n^2)</tex>, необходимо сначала посчитать <tex>DFT</tex> обоих многочленов. Так как при умножении двух многочленов их значения просто перемножаются в каждой точке. Следовательно, если <tex>DFT</tex> {{---}} это вектор значений многочлена, то мы можем получить значение произведения двух многочленов, просто перемножив их ДПФ. Значит, чтобы получить коэффициенты полученного многочлена, применим обратное ДПФ.

<tex>

A \times B = InvDFT(DFT(A) \times DTF(B)).

</tex>

Так как ДПФ многолчена {{---}} это вектор его значений, значит, перемножение двух ДПФ требует только <tex>O(n)</tex> операций. Осталось только вычислять ДПФ и обратное ДПФ за время <tex>O(n)</tex>. Для этого используем [[Быстрое преобразование Фурье| быстрое преобразование Фурье]].