Schönhage-Strassen Algorithm

Purpose: Multiply two $n$-bit integers in $O(n\log n\log \log n)$ using an FFT over the ring $\mathbb{Z}/(2^k+1)\mathbb{Z}$, where the “roots of unity” are powers of 2 — so every twiddle multiplication is a shift. Schönhage and Strassen, 1971.

The Idea

An ordinary FFT over the complex numbers loses precision, and over a prime field it needs modular multiplications. Schönhage-Strassen picks a ring where the transform costs almost nothing:

In $R=\mathbb{Z}/(2^k+1)\mathbb{Z}$, the element $2$ has order $2k$, because $2^k\equiv -1$. So $2$ is a $2k$-th root of unity, and multiplying by a power of it is a cyclic shift — no multiplication at all.

Algorithm

1. Split each $n$-bit operand into $2^{\ell }$ blocks of $m$ bits each.
2. Choose $k$ so that $2^k+1$ can hold the largest possible coefficient of the product without wraparound, and so that a $2^{\ell }$-th root of unity (a power of 2) exists in the ring.
3. Run the FFT in $R$. All twiddle multiplications are shifts: $O(n\log n)$ bit operations for the whole transform.
4. Multiply pointwise — this needs $2^{\ell }$ multiplications of $k$-bit numbers, done by recursing into Schönhage-Strassen.
5. Inverse transform, then carry-propagate to recombine.

$T(n)=O(\sqrt{n})\cdot T(O(\sqrt{n}))+O(n\log n)\Rightarrow T(n)=O(n\log n\log \log n).$

The $\log \log n$ is the recursion depth: block sizes shrink roughly as a square root each level.

The multiplication complexity story

Year	Result	Time
antiquity	schoolbook	$O(n^2)$
1960	Karatsuba	$O(n^{1.585})$
1963	Toom-Cook	$O(n^{1+\epsilon })$
1971	Schönhage-Strassen	$O(n\log n\log \log n)$
2007	Fürer	$O(n\log n{2}^{O({\log }^{\ast }n)})$
2019	Harvey-van der Hoeven	$O(n\log n)$ — conjectured optimal

The 2019 result finally achieved the $O(n\log n)$ that Schönhage and Strassen conjectured in the same 1971 paper. It is entirely theoretical: the algorithm only beats Schönhage-Strassen for numbers with more than about $2^{1729^{12}}$ bits.

In practice

GMP uses Schönhage-Strassen above roughly 30 000-100 000 bits. Below that, Toom-Cook variants win. This makes it the only one of the sub-quadratic asymptotic improvements that is both used in production and asymptotically strong — Fürer and Harvey-van der Hoeven are galactic algorithms.

Why competitive programmers should still care

Not to implement it, but for the idea: choose an algebraic setting where the expensive operation becomes cheap. The specific instance — a ring where roots of unity are powers of 2, so transforms are shifts — reappears whenever you need convolution without floating point. It is the same instinct behind choosing an NTT-friendly prime like $998244353$, whose $2$-adic structure gives cheap roots of unity.

Variants / Use Cases

• NTT — the contest-scale equivalent of this idea
• Big Integer Multiplication — the topic page
• Fürer’s algorithm — the next step up
• Toom-Cook — the method used below the crossover