Rader's Algorithm

Purpose: Compute a DFT of prime length $p$ in $O(p\log p)$ by re-indexing with a primitive root, turning the transform into a cyclic convolution of length $p-1$.

The Idea

The multiplicative group ${\mathbb{Z}}_p^{\ast }$ is cyclic of order $p-1$. Let $g$ be a primitive root. Then every nonzero index can be written as $g^a$, and the map $a\mapsto g^a$ is a bijection $\{0,\dots ,p-2\}\to \{1,\dots ,p-1\}$.

Re-index the DFT (for $k\ne 0$) by $j=g^a$, $k=g^{-b}$:

$X_{g^{-b}}-x_0={\sum }_{a=0}^{p-2}{x}_{g^a}{\omega }^{g^{a-b}}.$

The exponent depends only on $a-b$, so the right-hand side is a cyclic convolution of length $p-1$ between the sequences $x_{g^a}$ and ${\omega }^{g^c}$.

Since $p-1$ is composite (for $p>3$), that convolution can be computed with a standard FFT — or, if $p-1$ is awkward, by zero-padding to a power of two with Bluestein-style handling.

Algorithm

1. Find a primitive root $g$ modulo $p$.
2. Set $X_0={\sum }_j{x}_j$ separately.
3. Permute the input by $a\mapsto x_{g^a\mathrm{mod}p}$.
4. Cyclically convolve with the precomputed sequence ${\omega }^{g^{-c}\mathrm{mod}p}$.
5. Add $x_0$ to every output and un-permute.

Complexity

• Time: $O(p\log p)$
• Space: $O(p)$
• Precomputation: one primitive root (fast, needs the factorisation of $p-1$) plus the twiddle sequence

Rader vs Bluestein for prime lengths

	Rader	Bluestein
Requires	a primitive root mod $p$	nothing
Convolution length	$p-1$ (exact, cyclic)	$\ge 2p-1$ (padded, linear)
Numerical accuracy	better	chirp factors grow, slightly worse
Generality	prime lengths only	any length
Used by	FFTW for small primes	FFTW for large/awkward primes

Both appear in production FFT libraries: FFTW picks Rader for moderate primes and Bluestein when $p-1$ factors badly.

Where this matters in competitive programming

Rarely, directly. But the underlying move — re-indexing a sum by a primitive root to turn multiplication into addition — is a genuinely reusable idea:

• it is how discrete logarithms convert multiplicative problems into additive ones;
• it is the basis of Pohlig-Hellman;
• it turns “convolution over ${\mathbb{Z}}_p^{\ast }$ under multiplication” into ordinary cyclic convolution, which is occasionally exactly what a counting problem needs.

Variants / Use Cases

• FFT and NTT — the topic page
• Primitive Root — the number theory this depends on
• Good-Thomas — the coprime-factor decomposition, often combined with Rader in mixed-radix FFTs
• Cooley-Tukey — the power-of-two workhorse