Алгоритм Шёнхаге - Штрассена

[s4kkkk]

Перемножение чисел можно свести к перемножению соответствующих многочленов (соответствующих в том смысле, что каждый разряд исходных чисел будет соответствующим коэффициентом этих многочленов), за исключением того, что нужно будет провести перенос через разряды выходного многочлена (ибо коэффициенты результирующего многочлена могут быть $\geq 10$). С другой стороны, многочлены можно перемножить и поточечно. То есть, буквально взять какие-нибудь точки (главное одинаковые), посчитать значение первого и второго многочлена в этих точках, перемножить эти значения, и таким образом получить значения результирующего многочлена произведения.
Если вы посмотрите на формулу ДПФ:

$$ F_k = \sum_{n=0}^{N-1} {f_n e^{\frac{-2 \pi i k n}{N} }} $$

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