Find element of multiplicative group such that its order is $n$

Question

Is there an efficient algorithm that given an integer $n$, it finds any $a$ and $p$ such that $a$ has order $n$ in $(\mathbb Z/p\mathbb Z)^\times$?

$n$ may be moderately large, say ~$10^5$.

If it helps, the specific $n$ I have in mind is $49\times2^{11}=100352$.

Answer 1

Not necessarily efficient, but here is a suggestion:

$n$ must be a divisor of $p-1$, so you have to

• find a multiple of $n$, $kn$ such that $kn+1$ is prime,
• find a primitive element $b$ of the cyclic group $(\mathbf Z/p\mathbf Z)^\times$ and
• take $a=b^k$.

For $n=100\,352$, a probabilistic test says that $3n+1=301\,057$ is prime.

Answer 2

Look for primes $p = k n +1$. The first is $p=3\times 100352 + 1= 301057$. Now compute the orders of small prime elements

$$\mathrm{order}(2,301057) = 25088$$ $$\mathrm{order}(3,301057) = 37632$$ $$\mathrm{order}(5,301057) = 100352\quad \Rightarrow \textbf{Bingo}$$