In the paper Porkodi and Arumuganathan - Public key cryptosystem based on number theoretic transforms I found the following statement on the second page regarding the Inverse Number Theoretic Transformation (INTT), there the INTT is defined as follows:
$$h_l = N^{-1} \sum_{k=0}^{N-1} H_k g^{-lk} \pmod{m},\; l=0,\ldots,N-1$$ where $m$ is a composite number and $$NN^{-1} = 1 \pmod{m},\quad g^N = 1 \pmod{m}$$ and $$ \sum_{k=0}^{N-1} g^{uk} = 0 \pmod{m}. $$ Equivalently, $$ \gcd(g^u - 1, m) = 1 $$ for every $u$ such that $N/u$ is a prime.
I am now interested in:
- To know what exactly the condition $\gcd(g^u - 1, m) = 1$ says. For this I have a guess: Assuming $g$ is a primitive root modulo $m$ with order $N$, then $\gcd(g^u - 1, m) = 1$ ensures that $g^u \not\equiv 1 \pmod{m}$, can we say so?
- How to get the idea that $N/u$ is a prime number and why that is important in this context. I am just interested in how one comes up with this last condition ($\gcd(g^u - 1, m) = 1$ for every $u$ such that $N/u$ is a prime) in the definition.
I look forward to helpful comments.
