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.