Generating an element of a specific order if I know the prime factors of $N$ 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
 A: 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^*$.

*

*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$.


*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^*$.


*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$.


*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.
