Generating an element of a specific order if I know the prime factors of $N$

Question

Let $N$ be an integer and suppose we know the prime factorization of $N$. Will there then be a way of finding an element of a desired order in the multiplicative group of integers modulo $N$?

Let's say we input $k$ and we want to find an element $a$ of order $k$ in the multiplicative group of integers modulo $N$. Will that be possible if we know the prime factorization of $N$? Currently, I am not sure how that can be done. We can surely compute $\phi(N)$, factorize it, and raise a given element to all the factors of $\phi(N)$ to determine the order but I am not sure how we can find an element, given its order. Any input would be helpul

Answer 1

If we know how to compute the primitive root modulo $n$, this problem can also be solved. Recall that $g$ is a primitive root modulo $n$ if and only if $g$ is a generator of the multiplicative group of integers modulo $n$.

So let $N=p_1^{r_1}\ldots p_s^{r_s}$ where $p_{1},p_{2},\ldots ,p_{r}$ are the distinct primes dividing $N$ and let $k$ be an integer greater than $1$. Let $\mathbb{Z}_N^*$ be the multiplicative group of integers modulo $N$. We know $|\mathbb{Z}_N^*|=\phi(N)=p_1^{r_1-1}\ldots p_s^{r_s-1}(p_1-1)\ldots(p_s-1)$, where $\phi$ is Euler's totient function. Let us also assume that $k$ divides $\phi(N)$, otherwise there is no element of order $k$ in the group $\mathbb{Z}_N^*$.

1. We can assume that $k$ is a prime power. Indeed, if $k=mn$, $\operatorname{gcd}(m, n) = 1$, and $a,b\in\mathbb{Z}_N^*$ have orders of $m$ and $n$, respectively, then $|ab|=mn$.

2. Let $q$ be a prime and $k=q^t$.
   If $k$ does not divide $p_i^{r_i-1}(p_i-1)$ for every $i$, then there is no element of order $k$ in the group $\mathbb{Z}_N^*$.

3. Let $k$ divide $p_i^{r_i-1}(p_i-1)$ and $p_i$ be a odd prime. Let $g$ be a primitive root modulo $p_i^{r_i}$. Let us take $$ b=g^{p_i^{r_i-1}(p_i-1)/k}. $$ It is clear that $$ b^k\equiv1\pmod{p_i^{r_i}},\hbox{ and } b^l\not\equiv1\pmod{p_i^{r_i}} \hbox{ for all }1\leq l<k. $$ By the Chinese remainder theorem there exists an integer $a$ that $$ a\equiv b\pmod{p_i^{r_i}} \hbox{ and } a\equiv1\pmod{p_j^{r_j}} \hbox{ if }j\neq i. $$ We have $a^k\equiv b^k\equiv1\pmod{N}$ and $a^l\not\equiv1\pmod{N}$ for each $0<l<k$.

4. Let $p_1=2$, $k=2^t$ divide $2^{r_1-1}$, and $k$ does not divide $p_i^{r_i-1}(p_i-1)$ for every $i>1$. If $t=r_1-1$, then there are no solutions. If $t=r_1-2$, then $b=3$ has order $2^t$ in the group $\mathbb{Z}_{2^{r_1}}^*$. The other cases are now obvious.