# 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 you'll say if I'm right. I tested if the modulus is prime with rabin-miller test, the program is here en.literateprograms.org/Miller-Rabin_primality_test_(Python). It was prime, so I used this ftp.computing.dcu.ie/pub/crypto/factor.exe program to factor the modulus-1 since phi(prime) = prime - 1. It printed out 2 and another prime. So then I calculated g ^ q % (p-1) for all factors where q is the factor and they were != 1. So g should be a generator, right? –  Smit Johnth May 31 '13 at 13:38
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}$ –  Ricky Demer 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. –  Ricky Demer May 31 '13 at 16:29
I mistyped. It was p. –  Smit Johnth May 31 '13 at 19:14

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

-
A short and precise answer. –  Smit Johnth May 31 '13 at 13:39

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. –  alt 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 –  alt 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. –  alt May 30 '13 at 23:04