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$.
- Set
exponent
to $1$. - Calculate
result = [x]^exponent mod p
. - Check if
result
is $1$. - If
result
is $1$, check ifexponent
is $p-1$. - 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
exponent
by $1$.