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

Метод множення Шенхаге — Штрассена (англ. Schönhage–Strassen algorithm) — алгоритм множення великих цілих чисел, заснований на швидкому перетворенні Фур'є, вимагає $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 десяткових знаків).