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

Метод умножения Шёнхаге — Штрассена (Шаблон:Lang-en) — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует $O(N\cdot \log N\cdot \log \log N$) битовых операций, где $N$ — количество двоичных цифр в произведении.

Изобретён Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году.

Фактически является методом умножения многочленов от одной переменной, превращается в алгоритм умножения чисел, если эти числа представить как многочлены от основы системы счисления, а после получения результата сделать переносы через разряды. Например, для перемножения 157 и 171 (в десятичной системе счисления) выполняются следующие операции:

• представляется $157$ как $x^2+5x+7$, а $171$ — как $x^2+7x+1$, где $x=10$;
• перемножаются многочлены $x^2+5x+7$ и $x^2+7x+1$ с помощью быстрого преобразования Фурье, результат — $x^4+12x^3+43x^2+54x+7$;
• применяются переносы через разряды: $2x^4+6x^3+8x^2+4x+7$, то есть $26847$.

Также в алгоритме можно умножать по модулю чисел Ферма $2^{2^n}+1$, если применять двоичную систему счисления.

Метод считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был изобретён алгоритм Фюрера с лучшей оценкой сложности. На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка $10^{10000}$—$10^{40000}$ (от 10 000 до 40 000 десятичных знаков).