Return to Revisions

Everything related to the computational difficulty of factorizing integers should give you an answer. For instance, it is computationally easy to compute Euler's totient function for powers of primes, but it is computationally difficult to compute it for arbitrary integers. As a consequence, it is trivial to produce a generator of the additive group $\mathbb Z / p \mathbb Z$ for $p$ prime, but the same problem is computationally very difficult (and currently unsolved) for non-prime integers. (In turn, this makes it difficult to compute (multiplicative) square roots in $\mathbb Z / n \mathbb Z$, because its multiplicative group has order $\varphi(n)$ which, as seen above, is difficult to compute.)