# Primitive root modulo n

1. Jan 9, 2009

### 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?

2. Jan 16, 2009

### 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.

Last edited: Jan 16, 2009
3. Jan 16, 2009

### 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})$$.

Last edited: Jan 17, 2009
4. Jan 16, 2009

### 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

5. Jan 17, 2009

### 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!