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.
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: DOI