0
$\begingroup$

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.

  • 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...2012-03-22

1 Answers 1

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

  • 0
    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\\}$.2012-03-23