Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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]

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.