Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Knowing the factorisation of $g\in Z_p$, how to calculate the size of $\{g^i:0\leq i \leq p\}$? By $Z_p$ I mean the integers modulo $p$, where $p$ is prime.

share|improve this question
5  
The ordinary prime factorization of $g$ does not tell us much about the order of $g$ modulo $p$. –  André Nicolas Mar 21 '12 at 23:50
1  
I believe it is still unknown whether $2$ is a primitive root modulo infinitely many primes; of course, $2$ has a very simple factorization... –  Arturo Magidin Mar 22 '12 at 2:41

1 Answer 1

One way to calculate the number of distinct powers of $g$ modulo $p$ (and I think that's the question you are asking) is to just compute $1,g,g^2,g^3,\dots$ modulo $p$ until they start repeating. For small values of $p$ that may be the most efficient way.

If the factorization of $p-1$ is known then you only have to calculate $g^d$ for divisors $d$ of $p-1$, since the order of $g$ will be some such $d$.

If $p$ is so huge that factoring $p-1$ is out of the question then I don't think there's any computationally efficient way to calculate even the order of, say, 2 modulo $p$.

share|improve this answer
    
Thanks for pointing out that I misunderstood the question. I think your interpretation is certainly correct. –  MJD Mar 22 '12 at 2:31
    
@gerry myerson: so the size is the smallest $d|p-1$, for which $g^d=1$? –  asd Mar 22 '12 at 6:23
    
Yes. Look at an example; say, $g=3$, $p=11$. The powers of 3, reduced modulo 11, go 1, 3, 9, 5, 4, 1, so $3^5=1$, and your set has the five elements $\\{1,3,9,5,4\\}$. –  Gerry Myerson Mar 23 '12 at 0:34

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.