829 Fundamental

Chinese Remainder Theorem

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Chinese Remainder Theorem" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences: given `x ≡ a1 (mod m1)`, `x ≡ a2 (mod m2)`, ..., find x mod (m1 * m2 * ...) when the moduli are pairwise coprime. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The Chinese Remainder Theorem (CRT) solves systems of simultaneous congruences: given x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., find x mod (m1 m2 ...) when the moduli are pairwise coprime. This has applications in: cryptography (RSA-CRT speedup), number theory, calendar calculations, and distributed hashing. CRT also enables working with multiple small moduli instead of one large modulus, which is the key technique in Number Theoretic Transform (NTT) for polynomial multiplication. In competitive programming, CRT reconstructs a number from its remainders under several moduli, enabling range queries on large integers.

🎯 Learning Outcomes

• State the CRT: system x ≡ ai (mod mi) with pairwise coprime mi has unique solution mod M = m1m2...*mk

• Implement the constructive proof: for each i, compute Mi = M/mi, then yi = Mi^(-1) mod mi via extended GCD

• Combine: x = sum(ai * Mi * yi) mod M

• Handle the case of non-coprime moduli using the generalized CRT

• Apply CRT to RSA decryption speedup: compute separately mod p and mod q, combine with CRT

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Chinese Remainder Theorem in OCaml *)

(* Extended GCD: returns (g, x, y) where a*x + b*y = g *)
let rec extended_gcd (a : int) (b : int) : int * int * int =
  if b = 0 then (a, 1, 0)
  else
    let (g, x, y) = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Combine two congruences: x ≡ a1 (mod m1), x ≡ a2 (mod m2) *)
(* Returns Some (remainder, modulus) or None if no solution *)
let crt_combine (a1 : int) (m1 : int) (a2 : int) (m2 : int)
    : (int * int) option =
  let (g, p, _) = extended_gcd m1 m2 in
  if (a2 - a1) mod g <> 0 then None
  else begin
    let lcm = m1 / g * m2 in
    (* x = a1 + m1 * ((a2 - a1) / g * p mod (m2/g)) *)
    let m2g = m2 / g in
    let diff = ((a2 - a1) / g) mod m2g in
    let x = (a1 + m1 * ((diff * p mod m2g + m2g) mod m2g)) mod lcm in
    let x = (x + lcm) mod lcm in
    Some (x, lcm)
  end

(* Solve a system of congruences: x ≡ a_i (mod m_i) for all i *)
let crt (congruences : (int * int) list) : (int * int) option =
  List.fold_left (fun acc (a, m) ->
    match acc with
    | None -> None
    | Some (r, lcm) -> crt_combine r lcm a m
  ) (Some (0, 1)) congruences

let () =
  (* x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = 23 *)
  let system = [(2, 3); (3, 5); (2, 7)] in
  (match crt system with
   | Some (x, m) -> Printf.printf "x ≡ 2(mod 3), x ≡ 3(mod 5), x ≡ 2(mod 7): x = %d (mod %d)\n" x m
   | None -> Printf.printf "No solution\n");

  (* x ≡ 0 (mod 4), x ≡ 6 (mod 10) — non-coprime moduli, has solution *)
  (match crt [(0, 4); (6, 10)] with
   | Some (x, m) -> Printf.printf "x ≡ 0(mod 4), x ≡ 6(mod 10): x = %d (mod %d)\n" x m
   | None -> Printf.printf "No solution\n");

  (* x ≡ 1 (mod 4), x ≡ 6 (mod 10) — no solution since 6-1=5 not div by gcd(4,10)=2 *)
  (match crt [(1, 4); (6, 10)] with
   | Some (x, m) -> Printf.printf "x ≡ 1(mod 4), x ≡ 6(mod 10): x = %d (mod %d)\n" x m
   | None -> Printf.printf "x ≡ 1(mod 4), x ≡ 6(mod 10): No solution\n")

Key Differences

Aspect	Rust	OCaml
Modular inverse	Extended GCD returning `Option<i64>`	Returns `(int * int * int)`
Accumulation	`zip` iterator loop	`List.fold_left2`
Overflow	`i128` for large product M	`Zarith` for arbitrary precision
Error handling	`?` operator for `None` propagation	`Option.bind` chain
Non-negative result	`((x % m) + m) % m`	Same idiom
Return type	`Option<i64>`	`int option`

OCaml Approach

OCaml's CRT uses List.fold_left to accumulate the sum: List.fold_left2 (fun acc a mi -> ...) 0 remainders moduli. The modular inverse uses the extended Euclidean algorithm returning int * int. OCaml's Int64 or Zarith handles large products. The Option type signals failure when moduli are not coprime. OCaml's pattern matching on the extended GCD result tuple is clean: let (g, x, _) = extended_gcd mi m_i in if g <> 1 then None else Some x.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Chinese Remainder Theorem in OCaml *)

(* Extended GCD: returns (g, x, y) where a*x + b*y = g *)
let rec extended_gcd (a : int) (b : int) : int * int * int =
  if b = 0 then (a, 1, 0)
  else
    let (g, x, y) = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Combine two congruences: x ≡ a1 (mod m1), x ≡ a2 (mod m2) *)
(* Returns Some (remainder, modulus) or None if no solution *)
let crt_combine (a1 : int) (m1 : int) (a2 : int) (m2 : int)
    : (int * int) option =
  let (g, p, _) = extended_gcd m1 m2 in
  if (a2 - a1) mod g <> 0 then None
  else begin
    let lcm = m1 / g * m2 in
    (* x = a1 + m1 * ((a2 - a1) / g * p mod (m2/g)) *)
    let m2g = m2 / g in
    let diff = ((a2 - a1) / g) mod m2g in
    let x = (a1 + m1 * ((diff * p mod m2g + m2g) mod m2g)) mod lcm in
    let x = (x + lcm) mod lcm in
    Some (x, lcm)
  end

(* Solve a system of congruences: x ≡ a_i (mod m_i) for all i *)
let crt (congruences : (int * int) list) : (int * int) option =
  List.fold_left (fun acc (a, m) ->
    match acc with
    | None -> None
    | Some (r, lcm) -> crt_combine r lcm a m
  ) (Some (0, 1)) congruences

let () =
  (* x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) → x = 23 *)
  let system = [(2, 3); (3, 5); (2, 7)] in
  (match crt system with
   | Some (x, m) -> Printf.printf "x ≡ 2(mod 3), x ≡ 3(mod 5), x ≡ 2(mod 7): x = %d (mod %d)\n" x m
   | None -> Printf.printf "No solution\n");

  (* x ≡ 0 (mod 4), x ≡ 6 (mod 10) — non-coprime moduli, has solution *)
  (match crt [(0, 4); (6, 10)] with
   | Some (x, m) -> Printf.printf "x ≡ 0(mod 4), x ≡ 6(mod 10): x = %d (mod %d)\n" x m
   | None -> Printf.printf "No solution\n");

  (* x ≡ 1 (mod 4), x ≡ 6 (mod 10) — no solution since 6-1=5 not div by gcd(4,10)=2 *)
  (match crt [(1, 4); (6, 10)] with
   | Some (x, m) -> Printf.printf "x ≡ 1(mod 4), x ≡ 6(mod 10): x = %d (mod %d)\n" x m
   | None -> Printf.printf "x ≡ 1(mod 4), x ≡ 6(mod 10): No solution\n")

Deep Comparison

OCaml vs Rust: Chinese Remainder Theorem

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement CRT for two congruences iteratively and verify on the classic example: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).

Extend to handle non-coprime moduli using the generalized CRT with GCD-based compatibility checking.

Implement RSA-CRT decryption: given ciphertext c, p, q, d, compute p-component and q-component separately, then combine.

Use CRT with NTT-friendly primes to multiply polynomials with large coefficients.

Benchmark CRT-based RSA decryption against naive modular exponentiation with the full modulus.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust