Efficient way to find primitive root without prime factorization

401 Views Asked by At

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