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 a multiplicative group of prime order (any nontrivial element would do), but it is computationally very difficult to produce a generator of the multiplicative group of $\mathbb Z / n \mathbb Z$ for composite $n$ (because its order is $\varphi (n)$).