How would one go about in finding all of the primitive roots of a prime number?
I know how to check if for example a is a primitve root of the primitive number p.
We look at the expression $$ a^n \bmod p $$ for n = 1 to n = p -1. Once we go through all of the iterations we see if the remainders are unique and in the range of $$ (1, p-1) $$
How do I find for example all the primitive roots of 71, the method above seems highly time consuming...
For $p$ prime, a primitive root always exists and there are in fact $\phi(\phi(p))=\phi(p-1)$ of them, where $\phi$ is the Euler totient function defined by $\phi(n)= |\{1\leq a \leq n | \gcd(a,n)=1\}|$.
So once you've found a primitive root $a$, all the others are of the form $a^m$ where $\gcd(m,p-1)=1$. Hence all you need to do is find a single primitive root.