Rader's conversion is a one-dimensional index-mapping scheme that turns a
length-*only* for prime-length

An index map simply rearranges the order of the sum operation in the
DFT definition.
Because addition is a commutative operation, the same mathematical result is produced
from any order, as long as all of the same terms are added once and only once. (This is
the condition that defines an index map.)
Unlike the multi-dimensional index maps used in deriving
common factor and prime-factor FFTs,
Rader's conversion uses a one-dimensional index map in a finite group of

**Fact from number theory**

If

#### Example 1

**Another fact from number theory**

For

#### Example 2

So why do we care? Because we can use these facts to turn a DFT into a convolution!

**Rader's Conversion**

Let

#### Example 3

*power*,

Rader's conversion turns a prime-length DFT into a few adds
and a *composite-length*
(

- fast convolution via FFT and IFFT
- index-mapped convolution algorithms and short Winograd convolution alogrithms. (Rather complicated, and trades fewer multiplies for many more adds, which may not be worthwile on most modern processors.) See R.C. Agarwal and J.W. Cooley