Structural properties of complex residue rings applied to number theoretic Fourier transforms
M.C. Vanwormhoudt · IEEE Transactions on Acoustics Speech and Signal Processing · 1978
The complex residue ring C(m) modulo m is first defined. Because of the existence of a ring isomorphism known as the Chinese remainder theorem (CRT), the study of C(m) can be limited to the cases where m = pe, p being a prime. C(pe) contains a multiplicative group, the group Q(pe) of the invertible elements. Q(pe) is shown to be the product of a group of order p2e-2and of a group R(pe), which is of order (p - 1)2when 4 divides (p - 1), and of order (p2- 1) when 4 is no divisor of (p - 1). It is shown that there exists an isomorphic mapping ofQ(p) \longleftrightarrow R(p^{e}). Consequently, the study of the orders of the elements of R(pe) can be reduced to studying those of Q(p). When 4 is not a divisor of (p - 1), Q(p) and R(pe) are cyclic groups of order (p2- 1). When 4 divides (p - 1), the elements of C(p) can be isomorphically mapped on Z(p) × Z(p), Z(p) being the set of real residue classes, mod p. In this case, the order of the elements of Q(p) and of R(pe) are limited to the divisors of (p - 1). When 4 does not divide (p - 1), all elements of R(pe) satisfy a set of orthogonality relations. This property also holds true for some of the elements of R(pe) when 4 divides (p - 1). The foregoing results are applied to number theoretic Fourier transforms in C(m). A necessary and sufficient condition is derived for N to be a possible transform length. It is shown that all reductions modp\min{i}\max{e_{i}}of the transform factor wherep\min{i}\max{e_{i}}represent the prime power factors of m, must belong toR(p\min{i}\max{e_{i}}and be of order N. Where Fermat number transforms (FNT) do not lead to transform lengths that are larger in C(m) than in Z(m), Mersenne number transforms result in a very large increase of the allowable values of N. The paper ends with a discussion on how a search procedure in Q(p) or in Z(p) allows to determine all available transform factors in Q(pe) for a given N.