Chinese Remainder Theorem
Chinese Remainder Theorem: if the moduli are pairwise coprime, a system of congruences has a unique solution modulo their product.
Purpose
To decompose large-modulus arithmetic into parallel small-modulus arithmetic, speeding up big-number modular computation.
Mechanism
Given x≡a_i (mod n_i) with the n_i pairwise coprime, x has a unique solution mod N (N=∏n_i). Use N_i=N/n_i, M_i=N_i^(-1) mod n_i, and x=∑a_i*N_i*M_i mod N.
Use cases
- RSA acceleration
- Big-number modular arithmetic
- Number-theoretic algorithms