# Is modulus a prime number important for non-symmetric cryptology?

From this link Generation of a cyclic group of prime order we know how to generate a prime order group.

This illustrates why a prime order group is important.

But why is modulus a prime number also important?

In the theory of RSA, the modulus $$N=pq$$, and $$\operatorname{totient}(N)=(p-1)(q-1)$$， if we can find a factor $$p'$$ of $$p-1$$, then we can claim there is a $$p'$$ order sub-group? But it is not a modulus prime group, the $$N$$ is a composite number, is such a group useful?

• In classical Diffie-Hellman, you work on the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ where $p$ is prime. All computations are done modulo the prime $p$. – Tosh Sep 10 '19 at 10:31
• Another example is elliptic curve cryptography, which is often performed with an elliptic curve with x and y coordinates in the prime field $\Bbb Z_p$. Yet another is fast implementations of RSA signature and decryption (CRT-based), where the heaviest computations are performed modulo each prime dividing the public modulus. – fgrieu Sep 10 '19 at 17:13

Yes, such a group is useful. In particular, when $$N= p\cdot q$$ where $$p,q$$ are both strong primes (i.e. $$p=2p'+1,q=2q'+1$$ where $$p',q'$$ are also prime numbers).
Discrete logarithm in the prime order cyclic groups (order-$$p'$$ and order-$$q'$$) is believed to be hard. Such a group is called a group with hidden order.
Note that security does not hold for any arbitrary $$N$$ (even if it has only two large prime factors), see this paper.