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

Школьный алгоритм умножения «в столбик» $n$-значных десятичных или двоичных чисел требует (как минимум) умножить каждую цифру первого сомножителя на каждую цифру второго сомножителя, т. е. требует проведения не менее $n^2$ операций умножения и сложения однозначных чисел. В 1956 г. А. Н. Колмогоров высказал гипотезу, что любой метод умножения $n$-значных двоичных чисел требует проведения $O(n^2)$ битовых операций. В 1960 г. А. А. Карацуба, в то время аспирант механико-математического факультета МГУ, участник семинара А. Н. Колмогорова по математическим вопросам кибернетики, опроверг эту гипотезу, предложив новый метод умножения двух $n$-значных двоичных чисел, известный теперь как алгоритм Карацубы и выполнимый за $O( n^{\log_23})$ битовых операций. С получения этого сенсационного результата началась 60-летняя серия работ отечественных и зарубежных математиков по изучению и ускорению алгоритмов умножения многозначных чисел, инициированная Колмогоровым.

Важный вклад в развитие этой тематики в 1963 г. внёс студент 4-го курса механико-математического факультета МГУ А. Тоом. Он предложил новые подходы к задаче ускорения алгоритма умножения многозначных чисел и разработал зависящее от параметра $k\ge2$ семейство алгоритмов растущей эффективности: Тоом-2, Тоом-3, Тоом-4, ... . В работе (Тоом. 1963) доказано, что для выполнения алгоритма Тоом-$k$ требуется провести не более $O(n^{E_k})$ битовых операций, где показатель экспоненты $E_k$ равен $\log_2(2k-1)/\log_2(k).$

Самый простой алгоритм Тоом-2 фактически является вариацией алгоритма Карацубы и выполняется за $O(n^{\log_23} )=O(n^{1,58...})$ битовых операций. Алгоритм Тоом-3, переизложенный в диссертации С. Кука (1967), выполняется за $O(n^{\log_25/log_23}) = O(n^{1,46...}).$ С момента публикации Кука семейство алгоритмов Тоома получило название алгоритм Тоома – Кука. С ростом $k$ показатель степени $E_k$ стремится к $1,$ поэтому можно сказать, что Тоом построил алгоритм, который для любого $\varepsilon > 0$ выполняется за $O(n^{1+\varepsilon})$ битовых операций.

Новый подход к алгоритмам умножения многозначных чисел, предложенный в работе А. Тоома 1963 г.

Тоом предложил свести умножение $n$-значных двоичных чисел к умножению многочленов, а именно для каждого $k \ge 3$ свести умножение $n$-значных двоичных чисел к умножению многочленов степени, меньшей $k.$ При этом умножение двух многочленов-сомножителей степеней, меньших $k,$ Тоом предложил проводить не покоэффициентно, а более сложным путём:

• выбрать какой-нибудь набор из $2k-1$ точек, например набор целых точек $0, 1, -1, 2, -2, k-1, 1-k;$

• вычислить значения многочленов-сомножителей в выбранных точках;

• перемножить вычисленные значения многочленов-сомножителей в выбранных точках, найдя тем самым значения многочлена-произведения в $2k-1$ точках;

• c помощью интерполяционного полинома Лагранжа однозначно восстановить коэффициенты многочлена-произведения по известным значениям этого многочлена в $2k-1$ целых точках, что возможно, т. к. степень многочлена меньше $2k-1.$

Этот подход Тоома 1963 г. используется во всех последующих алгоритмах умножения многозначных чисел. В работе Тоома явно показано, что выбор набора из $2k-1$ точек, в которых вычисляются значения многочленов, достаточно произволен. Тоом выбирал набор целых точек, а коэффициенты многочлена-произведения вычислял с помощью операций с рациональными числами, которые в конечном счёте давали целые коэффициенты.

Применения быстрого преобразования Фурье в алгоритмах умножения многозначных чисел

После появления в 1965 г. работы Дж. Кули и Дж. Тьюки по быстрому преобразованию Фурье (БПФ), математики разных стран стали модифицировать подход Тоома, выбирая в качестве набора точек набор первообразных корней из единицы некоторой степени в поле комплексных чисел, конечном поле или кольце с единицей и используя на этапах вычисления значений многочленов-сомножителей в выбранных точках и этапе интерполяции классические или теоретико-числовые БПФ.

Согласно работе О. Б. Лупанова (Лупанов. 2008), российский математик Н. С. Бахвалов в конце 1960-х гг. построил алгоритм умножения $n$-значных двоичных чисел, требующий для своего выполнения $O(n\,\log_2n\,(\log_2n)^3)$ битовых операций. Этот результат не был опубликован.

В 1971 г. А. Шёнхаге и Ф. Штрассен предложили алгоритм умножения $n$-значных двоичных чисел (Schönhage. 1971), выполнимый за $O(n\,\log_2n\,\log_2(\log_2n))$ битовых операций. Этот алгоритм использует теоретико-числовое быстрое преобразование Фурье в кольце вычетов по модулю чисел вида $2^{2^n}+1$ (числа Ферма). Наконец, в 2021 г. опубликован алгоритм быстрого умножения $n$-значных двоичных чисел, выполнимый за $O(n\,\log_2n)$ битовых операций (Harvey. 2021). Алгоритм использует многомерное быстрое преобразование Фурье. Эта публикация подвела итог 60-летней серии работ отечественных и зарубежных математиков по изучению и ускорению алгоритмов умножения многозначных чисел, инициированных Колмогоровым в 1956 г.

До сих пор неизвестно, можно ли выполнить умножение $n$-значных двоичных чисел быстрее, чем за $O(n\,\log_2n)$ битовых операций.