# How to test if a number is a primitive root?

How to test if a number is a primitive root, assuming the modulus is a prime? And if not?

Is it not enough if the number is relatively prime to the modulus or prime?

I'll write down what I've done and would like to know if I'm right:

I tested if the modulus is prime with rabin-miller test, the program is here. It was prime, so I used this program to factor $modulus-1$ since $phi(prime) = prime - 1$. It printed out $2$ and another prime. So then I calculated $g ^ q \bmod (p-1)$ for all factors where $q$ is the factor and they were $\neq 1$. So $g$ should be a generator, right?

• Since I don't know whether your second link does a complete factorization or stops after having found $\;\;\;\;$ a single non-trivial factor, I don't know whether or not its actually asserting the "another prime" is prime. $\;\;$ In either case, you would then compute g^((p-1)/q) mod p for all prime factors q of p-1. $\hspace{1 in}$ – user991 May 31 '13 at 16:24
• The output is: <code>PRIME FACTOR x1 PRIME FACTOR x2</code>, so it should check for primarity. And there are only 2 factors. – Smit Johnth May 31 '13 at 16:25
• The main thing is that the exponentiation should be modulo the modulus (which is p), not modulo p-1. – user991 May 31 '13 at 16:29
• I mistyped. It was p. – Smit Johnth May 31 '13 at 19:14
• The person who gave another answer deleted it and probably removed his upvote and unstarred the question :) Or was it someone else? – Smit Johnth May 31 '13 at 19:16

For all $m$, if $m$ is a positive integer then

$g$ is a primitive root mod $m$ $\;$ if and only if
$0\leq g< m$ $\:$ and $\:$ $\operatorname{gcd}(\hspace{.015 in}g,\hspace{-0.01 in}m) = 1$ $\:$ and $\;\;$ for all prime factors $q$ of $\phi$$(m)$, $\: g^{(\phi(m))/q} \not\equiv 1 \pmod m$.

I assume we are in the case of $G = \mathbb{Z}_p^*$, and we have $g\in G$, and we want to determine whether the order of $g$ is in fact $p-1$.

From Exercise 1.31, Silverman and Pipher: Let $a\in\mathbb{F}_p^*$ and let $b = a^{(p-1)/q}$. Prove that either $b=1$ or else $b$ has order $q$.

(In addition, by remark 1.33, there are exactly $\phi(p-1)$ primitive elements.)

Naively, I would try to use the result of the exercise on the prime factorization of $p-1$, and since the order of the product of the $a^{(p-1)/q}$ is the LCM of the orders of the terms, you get an element of order $p-1$. I don't know if this is more efficient than trying random elements and computing powers $1,...,p-1$.

edit: it seems I am not too far off. source: http://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots

If you don't trust that, one can look up the sequence on OEIS, and the reference there is: Burton, D. M. "The Order of an Integer Modulo n," "Primitive Roots for Primes," and "Composite Numbers Having Primitive Roots." Sections 8.1-8.3 in Elementary Number Theory, 4th ed. Dubuque, IA: William C. Brown Publishers, pp. 184-205, 1989. [From Jonathan Vos Post, Sep 10 2010]

• Well, I haven't really understood your answer. Could you give me an algorith to prove it or probably a program source? – Smit Johnth May 30 '13 at 22:24
• I could easily write a program for this, the question is whether it makes sense for the bit-length of $p$ that you are considering. If it is 32 bits, for example, then no problem. Any larger than that and I cannot guarantee anything.. computing the prime factorization of $p-1$ is expensive (for 64 bit $p$, it costs 2^32 work, doable but slow if you want many generators). edit: doing this now. – Michael May 30 '13 at 22:31
• Assume at least 256 bits. Is there no ready software? What if p-1 is prime too? Do you know a software to test if a number is prime? – Smit Johnth May 30 '13 at 22:46
• I am sure there is some software to do this already. If $p$ is prime, $p-1$ cannot be prime since $2 | p-1$, but $(p-1)/2$ may be prime (although this is not that likely; 'safe' primes do not have small prime factors, each should be roughly the same size). Another source: cacr.uwaterloo.ca/~dstinson/papers/cs877s10.ps – Michael May 30 '13 at 23:02
• You will see in that reference that often a choice of $p$ is made so that the factorization of $p-1$ is already known. Primality testing is a separate issue, but it is well-studied. In practice, the Miller-Rabin primality test performs well. – Michael May 30 '13 at 23:04