CRT Decryption Speedup Calculator

About this calculator

RSA decryption normally computes m = c^d mod n directly, an expensive modular exponentiation with d often 2048 bits long. The Chinese Remainder Theorem (CRT) optimization splits this into two smaller exponentiations modulo the prime factors p and q instead: m_p = c^dp mod p and m_q = c^dq mod q, using the reduced exponents dp = d mod (p−1) and dq = d mod (q−1).

Because p and q are each roughly half the bit-length of n, these two exponentiations are individually much cheaper, and recombining m_p and m_q with Garner's formula restores the full plaintext m. The net effect is close to a 4× speedup over plain modular exponentiation — this is why CRT-based decryption is the default implementation choice in TLS stacks and crypto libraries like OpenSSL, and why RSA private keys are usually stored with p, q, dp, dq and qInv rather than just d.