# Efficient way to find primitive root without prime factorization

I was wondering if there is a more efficient brute-forcing approach to find any primitive root of number $$p$$ without prime factorization.

My approach is as follows:

1. Get a random residue class $$[x]$$ smaller than $$p$$.
2. Set exponent to $$1$$.
3. Calculate result = [x]^exponent mod p.
4. Check if result is $$1$$.
5. If result is $$1$$, check if exponent is $$p-1$$.
6. If condition 5 is true, we have found a primitive root.
7. If condition 5 is not true, we get a new random residue class $$[x]$$ smaller than $$p$$.
8. In each iteration, increase exponent by $$1$$.
• By the way: you could at least stop your algorithm at $(p-1)/2$. If $x$ is not a primitive root modulo $p$, its order in $\left(\Bbb{Z}/p\Bbb{Z}\right)^\times$ is guaranteed to be a proper divisor of $p-1$. – A.P. Oct 26 '15 at 9:24
• From these answers it looks like you are out of luck. – A.P. Oct 26 '15 at 9:44