Chinese remainder algorithm

Inversion, Chinese Remainder Algorithm, and Jacobi Symbol... 

The Chinese remainder algorithm is very efficient after a little precomputation that can be done once and for all in cryptologic situations for two congruences modulo numbers of length 112 it needs one modular and one non-modular multiplication of numbers of length HI. 

Consequently, if one has to carry out computations modulo a composite modulus n whose factors are known, it is often advantageous to compute modulo each of the factors separately and to combine the results with the Chinese remainder algorithm at the end [QuCo82]. 

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. 

---