PyQdeck LogoPyQdeckSubjectsSyllabusBlog

Number Theory and Public-Key Cryptography · Cryptography and Network Security

Chinese Remainder Theorem

Watch lectures

Chinese Remainder Theorem

1. What It Says (beginner!)

System of remainders with coprime moduli has ONE solution mod product! Like two clocks (mod 3, mod 5) pin down exactly one hour mod 15!

x mod mi=ai(mi pairwise coprime)⇒ unique x mod M=m1×...×mkx \text{ mod } m_{i} = a_{i} \quad (m_{i} \text{ pairwise coprime}) ⇒ \text{ unique } x \text{ mod } M = m₁ \times ... \times m_{k}

2. Worked (exam numerical — memorize steps!)

x ≡ 2 mod 3, x ≡ 3 mod 5 → M = 15
M₁ = 15/3 = 5, inverse of 5 mod 3: 5 ≡ 2, 2⁻¹ mod 3 = 2 (2×2=4≡1!)
M₂ = 15/5 = 3, inverse of 3 mod 5: 3⁻¹ mod 5 = 2 (3×2=6≡1!)
x = 2×5×2 + 3×3×2 = 20 + 18 = 38 ≡ 8 mod 15 ✓ (8 mod 3=2, mod 5=3!)

3. Formula (one line!)

x=sum ai×Mi×yi mod M(Mi=M/mi,  yi=Mi−1 mod mi)x = \text{sum } a_{i} \times M_{i} \times y_{i} \text{ mod } M \quad (M_{i} = M/m_{i}, \; y_{i} = M_{i}^{-1} \text{ mod } m_{i})

4. Why Crypto Cares

  • RSA speedup: decrypt mod pp and mod qq (small!) then combine — ~4× faster (private ops use CRT!).
  • Split secrets/computation across moduli (parallel!).

5. Exam Points

  • Solve 2-congruence system — 7 marks, favourite numerical.
  • Inverse-finding step — 3 marks, most-error step.
  • RSA-CRT speedup — 2-3 marks, frequent viva.
Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.

Get on Google Play
Previous topicTesting for PrimalityNext topicDiscrete Logarithms

← All Cryptography and Network Security modules