Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2006). Vol. B, ch. 1.3, p. 53   | 1 | 2 |

Section N a power of an odd prime

G. Bricognea

aMRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France N a power of an odd prime

| top | pdf |

This idea was extended by Winograd (1976[link], 1978[link]) to the treatment of prime powers [N = p^{\nu}], using the cyclic structure of the multiplicative group of units [U(p^{\nu})]. The latter consists of all those elements of [{\bb Z} / p^{\nu} {\bb Z}] which are not divisible by p, and thus has [q_{\nu} = p^{\nu - 1} (p - 1)] elements. It is cyclic, and there exist primitive roots g modulo [p^{\nu}] such that [U(p^{\nu}) = \{1, g, g^{2}, g^{3}, \ldots, g^{q_{\nu} - 1}\}.] The [p^{\nu - 1}] elements divisible by p, which are divisors of zero, have to be treated separately just as 0 had to be treated separately for [N = p].

When [k^{*} \not\in U(p^{\nu})], then [k^{*} = pk_{1}^{*}] with [k_{1}^{*} \in {\bb Z} / p^{\nu - 1} {\bb Z}]. The results [X^{*} (pk_{1}^{*})] are p-decimated, hence can be obtained via the [p^{\nu - 1}]-point DFT of the [p^{\nu - 1}]-periodized data Y: [X^{*} (pk_{1}^{*}) = \bar{F} (p^{\nu - 1}) [{\bf Y}] (k_{1}^{*})] with [Y(k_{1}) = {\textstyle\sum\limits_{k_{2} \in {\bb Z} / p {\bb Z}}} X(k_{1} + p^{\nu - 1} k_{2}).]

When [k^{*} \in U(p^{\nu})], then we may write [X^{*} (k^{*}) = X_{0}^{*} (k^{*}) + X_{1}^{*} (k^{*}),] where [{\bf X}_{0}^{*}] contains the contributions from [k\; \notin\; U(p^{\nu})] and [{\bf X}_{1}^{*}] those from [k \in U(p^{\nu})]. By a converse of the previous calculation, [{\bf X}_{0}^{*}] arises from p-decimated data Z, hence is the [p^{\nu - 1}]-periodization of the [p^{\nu - 1}]-point DFT of these data: [X_{0}^{*} (p^{\nu - 1} k_{1}^{*} + k_{2}^{*}) = \bar{F} (p^{\nu - 1}) [{\bf Z}] (k_{2}^{*})] with [Z(k_{2}) = X(pk_{2}), \qquad k_{2} \in {\bb Z} / p^{\nu - 1} {\bb Z}] (the [p^{\nu - 1}]-periodicity follows implicity from the fact that the transform on the right-hand side is independent of [k_{1}^{*} \in {\bb Z} / p {\bb Z}]).

Finally, the contribution [X_{1}^{*}] from all [k \in U(p^{\nu})] may be calculated by reindexing by the powers of a primitive root g modulo [p^{\nu}], i.e. by writing [X_{1}^{*} (g^{m^{*}}) = {\textstyle\sum\limits_{m = 0}^{q_{\nu} - 1}} X(g^{m}) e(g^{(m^{*} + m) / p^{\nu}})] then carrying out the multiplication by the skew-circulant matrix core as a convolution.

Thus the DFT of size [p^{\nu}] may be reduced to two DFTs of size [p^{\nu - 1}] (dealing, respectively, with p-decimated results and p-decimated data) and a convolution of size [q_{\nu} = p^{\nu - 1} (p - 1)]. The latter may be `diagonalized' into a multiplication by purely real or purely imaginary numbers (because [g^{(q_{\nu} / 2)} = -1]) by two DFTs, whose factoring in turn leads to DFTs of size [p^{\nu - 1}] and [p - 1]. This method, applied recursively, allows the complete decomposition of the DFT on [p^{\nu}] points into arbitrarily small DFTs.


Winograd, S. (1976). On computing the discrete Fourier transform. Proc. Natl Acad. Sci. USA, 73, 1005–1006.
Winograd, S. (1978). On computing the discrete Fourier transform. Math. Comput. 32, 175–199.

to end of page
to top of page