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