International
Tables for Crystallography Volume B Reciprocal space Edited by U. Shmueli © International Union of Crystallography 2010 
International Tables for Crystallography (2010). Vol. B, ch. 1.3, p. 56

This idea was extended by Winograd (1976, 1978) to the treatment of prime powers , using the cyclic structure of the multiplicative group of units . The latter consists of all those elements of which are not divisible by p, and thus has elements. It is cyclic, and there exist primitive roots g modulo such thatThe elements divisible by p, which are divisors of zero, have to be treated separately just as 0 had to be treated separately for .
When , then with . The results are pdecimated, hence can be obtained via the point DFT of the periodized data Y:with
When , then we may writewhere contains the contributions from and those from . By a converse of the previous calculation, arises from pdecimated data Z, hence is the periodization of the point DFT of these data:with(the periodicity follows implicity from the fact that the transform on the righthand side is independent of ).
Finally, the contribution from all may be calculated by reindexing by the powers of a primitive root g modulo , i.e. by writingthen carrying out the multiplication by the skewcirculant matrix core as a convolution.
Thus the DFT of size may be reduced to two DFTs of size (dealing, respectively, with pdecimated results and pdecimated data) and a convolution of size . The latter may be `diagonalized' into a multiplication by purely real or purely imaginary numbers (because ) by two DFTs, whose factoring in turn leads to DFTs of size and . This method, applied recursively, allows the complete decomposition of the DFT on points into arbitrarily small DFTs.
References
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.