In a paper 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}, 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:

1. 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?
2. 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.

Thank you all for your interest in the topic and I look forward to helpful comments. Thank you very much!

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:

1. 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?
2. 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.

In a paper 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,...,N-1$$ Where $m$ is a composite number and $$NN^{-1} = 1 \pmod{m}, 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:

1. 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?
2. 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.

Thank you all for your interest in the topic and I look forward to helpful comments. Thank you very much!

In a paper 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}, 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:

1. 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?
2. 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.

Thank you all for your interest in the topic and I look forward to helpful comments. Thank you very much!