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$.
  • $\begingroup$ 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$. $\endgroup$ – A.P. Oct 26 '15 at 9:24
  • $\begingroup$ From these answers it looks like you are out of luck. $\endgroup$ – A.P. Oct 26 '15 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.