Chinese Remainder Theorem

Jim Hefferon · Elementary Number Theory · Ch. 5

If moduli are pairwise coprime, a system of congruences has a unique solution mod their product. The Chinese Remainder Theorem gives a constructive algorithm to find it.

Overlapping cycles

Think of CRT as synchronizing clocks with different periods. A cycle of length 3 and a cycle of length 5 meet every 15 steps. The meeting point is the unique solution.

The algorithm

Given x ≡ a1 (mod n1), x ≡ a2 (mod n2), ..., with pairwise coprime ni: compute N = n1 n2 ... nk. For each i, let Ni = N/ni. Find yi such that Ni yi ≡ 1 (mod ni) using extended GCD. Then x ≡ sum of ai Ni yi (mod N).

Scheme

; Chinese Remainder Theorem
(define (extended-gcd a b)
  (if (= b 0)
      (list a 1 0)
      (let* ((result (extended-gcd b (modulo a b)))
             (g (car result))
             (x1 (cadr result))
             (y1 (caddr result)))
        (list g y1 (- x1 (* (quotient a b) y1))))))

(define (crt remainders moduli)
  (let* ((big-n (apply * moduli))
         (terms
          (map (lambda (ai ni)
                 (let* ((big-ni (quotient big-n ni))
                        (result (extended-gcd big-ni ni))
                        (yi (cadr result)))
                   (* ai big-ni yi)))
               remainders moduli)))
    (modulo (apply + terms) big-n)))

; x = 2 mod 3, x = 3 mod 5
(display "x = 2 mod 3, x = 3 mod 5: x = ")
(display (crt (list 2 3) (list 3 5))) (newline)
; Answer: 8.  8 mod 3 = 2, 8 mod 5 = 3

; x = 1 mod 3, x = 2 mod 5, x = 3 mod 7
(display "x = 1 mod 3, x = 2 mod 5, x = 3 mod 7: x = ")
(display (crt (list 1 2 3) (list 3 5 7)))
; Answer: 52.  52 mod 3 = 1, 52 mod 5 = 2, 52 mod 7 = 3

; Chinese Remainder Theorem
(define (extended-gcd a b)
  (if (= b 0)
      (list a 1 0)
      (let* ((result (extended-gcd b (modulo a b)))
             (g (car result))
             (x1 (cadr result))
             (y1 (caddr result)))
        (list g y1 (- x1 (* (quotient a b) y1))))))

(define (crt remainders moduli)
  (let* ((big-n (apply * moduli))
         (terms
          (map (lambda (ai ni)
                 (let* ((big-ni (quotient big-n ni))
                        (result (extended-gcd big-ni ni))
                        (yi (cadr result)))
                   (* ai big-ni yi)))
               remainders moduli)))
    (modulo (apply + terms) big-n)))

; x = 2 mod 3, x = 3 mod 5
(display "x = 2 mod 3, x = 3 mod 5: x = ")
(display (crt (list 2 3) (list 3 5))) (newline)
; Answer: 8.  8 mod 3 = 2, 8 mod 5 = 3

; x = 1 mod 3, x = 2 mod 5, x = 3 mod 7
(display "x = 1 mod 3, x = 2 mod 5, x = 3 mod 7: x = ")
(display (crt (list 1 2 3) (list 3 5 7)))
; Answer: 52.  52 mod 3 = 1, 52 mod 5 = 2, 52 mod 7 = 3

Applications

CRT speeds up RSA by splitting computation mod p and mod q separately (smaller numbers, then recombine). It also explains why calendar cycles repeat: the day-of-week cycle (7) and day-of-month cycle interact via CRT.

Scheme

; Application: what day is it?
; A day is simultaneously at position d mod 7 (weekday)
; and d mod 30 (roughly, day of month).
; If today is Wednesday (day 3) and the 17th:
; what is the next day that is both Wednesday and the 17th?
; CRT: x = 3 mod 7, x = 17 mod 30.

(define (extended-gcd a b)
  (if (= b 0) (list a 1 0)
      (let* ((r (extended-gcd b (modulo a b)))
             (g (car r)) (x (cadr r)) (y (caddr r)))
        (list g y (- x (* (quotient a b) y))))))

(define (crt remainders moduli)
  (let* ((big-n (apply * moduli))
         (terms (map (lambda (ai ni)
                       (let* ((big-ni (quotient big-n ni))
                              (r (extended-gcd big-ni ni))
                              (yi (cadr r)))
                         (* ai big-ni yi)))
                     remainders moduli)))
    (modulo (apply + terms) big-n)))

(let ((day (crt (list 3 17) (list 7 30))))
  (display "Next Wednesday the 17th: day ")
  (display day)
  (display " in a 210-day cycle"))

← Euler and Fermat by june.kim Quadratic Residues →