zbMATH — the first resource for mathematics

Generalized Fermat-Mersenne number theoretic transform. (English) Zbl 0808.65146
Let $$\mathbb{Z}_ p$$ be the ring of integers $$\{0,1, \dots, p - 1\}$$. The number theoretic transform of $$\{x(n)\}_{n = 0}^{N - 1}$$ for $$x(n) \in \mathbb{Z}_ p$$ is defined as $$X(k) = \sum_{n = 0}^{N - 1} x(n) \alpha^{nk}$$, $$k = 0,1, \dots,N - 1$$ where $$\alpha^ N \equiv 1 \pmod{p}$$ while $$\alpha^ k \not\equiv 1\pmod{p}$$ for all $$k < N$$. For practical applications, the numbers $$N, p$$ and $$\alpha$$ should have certain properties. Among others, Fermat $$(p = 2^{2^ n} + 1)$$ and Mersenne $$(p = 2^ n - 1)$$ numbers have been proposed for the modulo $$p$$. In this paper, generalized Fermat-Mersenne numbers of the form $$p = G(q,k,n) = (q^{kn} - 1)/(q^ n - 1)$$ are considered. For example $$G(2, k,1)$$ is a Mersenne and $$G(2,2,2^ j)$$ is a Fermat number. Conditions for such a $$p$$ to be prime and an algorithm for computing in $$\mathbb{Z}_ p$$ and for computing the root of unity $$\alpha$$ are given.
Several special cases which lead to the desirable properties for practical applicability are discussed in more detail.
MSC:
 65T50 Numerical methods for discrete and fast Fourier transforms 94A12 Signal theory (characterization, reconstruction, filtering, etc.) 11A63 Radix representation; digital problems 11A51 Factorization; primality
Full Text: