I am currently trying to learn about the ElGamal Digital Signature scheme.
It is based on the discrete logarithm problem, where it is computationally infeasible to find $x$ in $y=g^x \mod{p} $), if the following is met:
(1) The chosen prime, p, is a large one.
(2) p-1 needs at least one prime factor that is big.
(3) The order of $x$ in $y = g^x \mod{p}$ needs to be large, where $y$ and $g$ are elements in $\mathbb{Z}^*_p$. In other words: The smallest integer, $x$, that fulfills $g^x \equiv 1 \mod {p}$ has to be big.
I was wondering with regard to the third point, what the highest possible order achievable is? I know that if p is a prime, then the highest possible order for $x$ in $y = g^x \mod{p}$ is $p-1$. However, what if p was not a prime, but a composite number, $n$, that was the product of two primes, we can call p and q, what would the highest possible order then be and why? I cannot seem to quite figure this out, and it's bugging me... I hope that someone can help me out, so I can get this off my mind.
Thanks alot.
PS. My current guess is that the answer involves Euler's phi, as it counts the numbers relatively prime to the composite number $n$... It is mostly just a guess though, since I am not sure why this should be the case.
The maximum such order is the Carmichael function $\lambda$, applied to $pq$. It is known that $\lambda(pq)=\textrm{lcm} (\lambda(p),\lambda(q))$ for $p,q$ distinct primes. It is also known that $\lambda(p)=p-1$ and $\lambda(q)=q-1$, so in your case the answer is $\textrm{lcm}(p-1,q-1)$.
PS. your suspicions are right, the totient $\phi(pq)$ is an upper bound for the Carmichael function.