Бы́строе умноже́ние многочле́нов, класс алгоритмов вычисления произведения двух многочленов степеней, меньших $n,$ с комплексными коэффициентами, требующих для своего выполнения не более $O(n\,\log_2n)$ арифметических операций.

Быстрое умножение двух комплексных многочленов степеней, меньших $n,$ иначе говоря, свёртку двух последовательностей комплексных чисел длины $n,$ можно выполнить путём сведения свёртки к выполнению двух дискретных преобразований Фурье (ДПФ) размера $2n$ и одного преобразования, обратного к ДПФ размера $2n.$ Выполнение каждого из этих трёх преобразований с помощью быстрого преобразования Фурье позволит затратить на выполнение свёртки не более $O(n\,\log_2n)$ арифметических операций.

Сведение свёртки последовательностей коэффициентов двух многочленов степени, меньшей $n,$ к вычислению произведений значений этих многочленов в $2n$ точках выполняется следующим образом. Пусть $a_0+a_1t^1+a_2t^2+\ldots+a_{n-1}t^{n-1}$ и $b_0+b_1t^1+b_2t^2+\ldots+b_{n-1}t^{n-1}$ – два многочлена степени $n-1$ и $c_0+c_1t^1+c_2t^2+\ldots+c_{2n-2}t^{2n–2}$ – их произведение. Дополним каждый из этих трёх многочленов нулевыми членами до степени $2n-1.$ Полученные многочлены степени $2n-1$ назовём $A(t),$ $B(t)$ и $С(t).$ Ясно, что многочлен $C(t)$ является произведением многочленов $A(t)$ и $B(t).$ Обозначим через $w$ корень из единицы степени $2n$ с аргументом $-2\pi/(2n).$ Вычислим с помощью двух БПФ размера $2n$ значения многочленов $A(t)$ и $B(t)$ в $2n$ точках $w^0, w^1, w^2, w^3, \ldots, w^{2n-1}.$ Значения многочлена $C(t)$ в этих $2n$ точках можно вычислить, выполнив $2n$ умножений: $С(w^0)=A(w^0)\cdot B(w^0),$ $С(w^1)=A(w^1)\cdot B(w^1),$ $С(w^2)=A(w^2)\cdot B(w^2),$ $\ldots ,$ $С(w^{2n-1})=A(w^{2n-1})\cdot B(w^{2n-1}).$ Многочлен степени, не превосходящей $2n-1,$ принимающий заданные значения в $2n$ различных точках, единственен. Поэтому коэффициенты многочлена $C(t)$ могут быть найдены с помощью обратного ДПФ размера $2n,$ применённого к найденному выше набору его значений в точках $w^0, w^1, w^2, w^3, \ldots, w^{2n-1}.$ Затраты на выполнение двух прямых БПФ размера $2n,$ последующее вычисление $2n$ произведений и обратное ДПФ размера $2n$ составят $2O(2n\,\log_2n) + 2n + O(2n\,\log_22n)$ арифметических операций над комплексными числами, что эквивалентно $O(n\,\log_2n).$ Тем самым свёртка двух последовательностей длины $n$ может быть выполнена за $O(n\,\log_2n)$ арифметических операций.

Быстрое умножение требуется для многочленов не только с комплексными коэффициентами. В частности, в современных информационных системах активно используется арифметика конечных полей и колец многочленов над конечными полями. В конечном поле, вообще говоря, может не быть первообразных корней из единицы нужной степени, поэтому требуется расширение до колец, в которых определено ДПФ достаточно большого размера $n.$