Chinese remainder theorem

The Chinese remainder theorem reduces the problem of determining the structure of rings Z to rings Z r for prime powers pL The most important theorem about the latter is lliat for p 2, each multiplicative group Z r is cyclic. 

The situation modulo a general odd n can be derived with the Chinese remainder theorem A number y is a quadratic residue modulo n if and only if it is one modulo each prime factor of n. If n has i distinct prime factors, the number of square roots of each quadratic residue is 2, and l(2 l = IZ I / 2. ... 

Remark 8.72. One can write hashgim) = r> m(prefixjree (m)), jjere X is the length of the encoded message, prefix free m). If the party that has generated the key applies the hash function, this can be used to improve efficiency greatly The Chinese remainder theorem can be used to evaluate hashjfm) modulo the factors p and qoin separately, and the exponents, which may be quite long, can first be reduced modulo p- and q-. ... 

If the recipient is the risk bearer, his entity can use the Chinese remainder theorem to speed up testing, because it knows the factors of the prekey. 

Note that if we attempt to compute as an integer first, and then reduce modulo n, the intermediate result will be quite large, even for such small values of m and e. For this reason, it is important for RSA implementations to use modular exponentiation algorithms that reduce partial results as they go and to use more efficient techniques such as squaring and multiply rather than iterated multiplications. Even with these improvements, modular exponentiation is still somewhat inefficient, particularly for the large moduli that security demands. To speed up encryption, the encryption exponent is often chosen to be of the form 2 - -1, to allow for the most efficient use of repeated squarings. To speed up decryption, the Chinese Remainder Theorem can be used provided p and q are remembered as part of the private key. 

---