Structural properties of complex residue rings applied to number theoretic Fourier transforms

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 = p^e, p being a prime. C(p^e) contains a multiplicative group, the group Q(p^e) of the invertible elements. Q(p^e) is shown to be the product of a group of order p^2e-2and of a group R(p^e), which is of order (p - 1)²when 4 divides (p - 1), and of order (p²- 1) when 4 is no divisor of (p - 1). It is shown that there exists an isomorphic mapping of . Consequently, the study of the orders of the elements of R(p^e) can be reduced to studying those of Q(p). When 4 is not a divisor of (p - 1), Q(p) and R(p^e) are cyclic groups of order (p²- 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(p^e) are limited to the divisors of (p - 1). When 4 does not divide (p - 1), all elements of R(p^e) satisfy a set of orthogonality relations. This property also holds true for some of the elements of R(p^e) 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 mod of the transform factor where represent the prime power factors of m, must belong to 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(p^e) for a given N.