ABSTRACT
Abstract. In this paper, we present results that can be used to obtain all the possible generators for a number theoretic transform (NTT) defined in a finite integer ring and its polynomial extensions. A generalization of the well-known Euler’s theorem is derived which can be used to determine all the generators of a given NTT once the generators in the underlying finite field are identified. Based on this extension, we also describe a procedure to compute cyclotomic factorization in these rings. This factorization and Chinese remainder theorem lead to computationally efficient algorithms for computing cyclic convolution of two sequences defined in finite integer and complex integer rings.
