[dmarquis]

The difficulty of the discrete log problem doesn't have anything to do with the modulus being prime, DLP is at least as hard for composite moduli. Its considered a hard problem because after 30 years a fast algorithm hasn't been found and a majority of experts think there isn't one. Also, a prime modulus is used for Diffie Hellman since the set {1,2...,p-1} mod p forms a cyclic group (under multiplication) which makes the method as simple as possible. However, a slightly more complicated variation of DH could be used for a composite modulus (where the group is not usually cyclic).

[dhaivatpandya]

If the modulus isn't prime, we can split it apart into two, much simpler modular equations, which is part of the reason WHY its so hard to come up with a good algorithm, and the other half is what you said.