Editing RSA cryptosystem (section)

===Using the Chinese remainder algorithm===
For efficiency, many popular crypto libraries (such as [[OpenSSL]], [[Java (programming language)|Java]] and [[.NET Framework|.NET]]) use for decryption and signing the following optimization based on the [[Chinese remainder theorem]].<ref>{{cite web |title=OpenSSL bn_s390x.c |url=https://github.com/openssl/openssl/blob/422a13fb5cd668cdc4c1eebce8accb4d25c3d8eb/crypto/bn/bn_s390x.c#L70 |website=Github |access-date=2 August 2024}}</ref>{{fact|date=December 2023}} The following values are precomputed and stored as part of the private key:
* <math>p</math> and <math>q</math>{{snd}} the primes from the key generation,
* <math>d_P = d \pmod{p - 1},</math>
* <math>d_Q = d \pmod{q - 1},</math>
* <math>q_\text{inv} = q^{-1} \pmod{p}.</math>

These values allow the recipient to compute the exponentiation {{math|1=''m'' = ''c''<sup>''d''</sup> (mod ''pq'')}} more efficiently as follows:
{{indent|5}}<math>m_1 = c^{d_P} \pmod{p}</math>,
{{indent|5}}<math>m_2 = c^{d_Q} \pmod{q}</math>,
{{indent|5}}<math>h = q_\text{inv}(m_1 - m_2) \pmod{p}</math>,{{efn|If <math>m_1 < m_2</math>, then some{{clarify|date=June 2020}} libraries compute {{mvar|h}} as <math>q_\text{inv}\left[\left(m_1 + \left\lceil \frac{q}{p} \right\rceil p\right) - m_2\right] \pmod{p}</math>.}}
{{indent|5}}<math>m = m_2 + hq</math>.

This is more efficient than computing [[exponentiation by squaring]], even though two modular exponentiations have to be computed. The reason is that these two modular exponentiations both use a smaller exponent and a smaller modulus.