# Generated subgroup size

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.

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

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$.
@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