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

Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — алгоритм умножения больших целых чисел, основанный на быстром преобразовании Фурье, требует $O(N\cdot <!--\; \cdot \; -->\log <!--\; \; -->N\cdot <!--\; \cdot \; -->\log <!--\; \; -->\log <!--\; \; -->N$$O(N\cdot \log N\cdot \log \log N$) битовых операций, где $N$$N$ — количество двоичных цифр в произведении.

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

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

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

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

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