Is there a simple way to determine if an element is a primitive root modulo n?

[sid_galt]

Is there an easy (by which I mean an algorithm polynomial in size of input) way to know whether in the multiplicative group of integers mod P (P is a prime), whether an element is a generator or not?

 

[ialbrekht]

Hi, there is one method but it required knowing expansion of the number P-1 on the simple factors.

So, if P-1 = p_{1}^{a_1} \times \cdots \times p_{n}^{a_n} where each p_i is prime and for each i=1...n : \frac{g^{P-1}}{p_i} \equiv 1 (mod P), than g - is primitive root (generator) by modulo P.

Unfortunately, exponential factorization algorithms not known yet.

 

[robert Ihnot]

ialbekht: Hi, there is one method

THAT! You are submitting as an EASY method? Anyway you got the exponent wrong. Should be:

i=1...n : g^\frac{P-1}{p_i} \equiv 1 (mod P) Also, to be a primitative root, it would NOT--by definition--be congruent to 1 for any value less than\varphi({P}).

 

[ialbrekht]

robert Ihnot:
Thanks for correcting me.

It's the first method I've remembered. The hardest thing is to factorize P-1, and It's not a problem for a not large P and if you know factorization of P-1 you may check g to be primitive root for polynomial time.

And I did not say that it's EASY way. Unfortunately, there are not much easy solutions in number-theory problems

 

[robert Ihnot]

From Wickipedia: Gauss defines primitive root in Article 57 of the Disquisitiones Arithmeticae (1801), where he credits Euler with coining the term.

Gauss then went ahead and gave the reader a table of primitive roots, so that he was aware that there was no really easy way to find them. It then seems, from the responses we are getting here, that's about where it is today!