Быстрое умножение многочленов

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

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

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

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