Skip to main content
deleted 123 characters in body
Source Link
Alex M.
  • 5.4k
  • 11
  • 35
  • 52

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 additivea multiplicative group $\mathbb Z / p \mathbb Z$ for $p$of prime order (any nontrivial element would do), but the same problemit is computationally very difficult to produce a generator of the multiplicative group of (and currently unsolved)$\mathbb Z / n \mathbb Z$ for non-prime integers.composite (In turn, this makes it difficult to compute$n$ (multiplicative) square roots in $\mathbb Z / n \mathbb Z$, becausebecause its multiplicative group has order $\varphi(n)$ which, as seen above, is difficult to compute.$\varphi (n)$).

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

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

Source Link
Alex M.
  • 5.4k
  • 11
  • 35
  • 52

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

Post Made Community Wiki by Alex M.