Composite moduli

Let n be a product of distinct primes p₁, p₂, ... p_k. The Chinese Remainder theorem implies we can solve a polynomial f(x) over each Z_pi, and then combine the roots together to find the solutions modulo n. This is because a root a of f(x) in Z_n corresponds to (a₁, a₂, ... a_k) ∈ Z_p1 × Z_p2 × ... × Z_pk, where each a_i is a root of f(x) in Z_pi.

Description from https://crypto.stanford.edu/pbc/notes/numbertheory/

by Kaiying Shan