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:
- Get a random residue class $[x]$ smaller than $p$.
result = [x]^exponent mod p.
- Check if
resultis $1$, check if
- If condition 5 is true, we have found a primitive root.
- If condition 5 is not true, we get a new random residue class $[x]$ smaller than $p$.
- In each iteration, increase