中国剩余定理CRT

CRT 的另一个用途是用一组比较小的质数表示一个大的整数。

例如，若 $a$ 满足如下线性方程组，且 $a < \prod_{i = 1}^{k} p_{i}$ （其中 $p_{i}$ 为质数）：

⎩ ⎨ ⎧ a a a \equiv a_{1} (mod p_{1}) \equiv a_{2} (mod p_{2}) ⋮ \equiv a_{k} (mod p_{k})

我们可以用以下形式的式子（称作 $a$ 的混合基数表示）表示 $a$ ：

a = x_{1} + x_{2} p_{1} + x_{3} p_{1} p_{2} + \dots + x_{k} p_{1} \dots p_{k - 1}

Garner 算法 将用来计算系数 $x_{1}, \dots, x_{k}$ 。

a_{1} \equiv x_{1} (mod p_{1})

a_{2} \equiv x_{1} + x_{2} p_{1} (mod p_{2})

(a_{2} - x_{1}) r_{1, 2} \equiv x_{2} (mod p_{2})

a_{3} \equiv x_{1} + x_{2} p_{1} + x_{3} p_{1} p_{2} (mod p_{3})

((a_{3} - x_{1}) r_{1, 2} - x_{2}) r_{2, 3} \equiv x_{3} (mod p_{3})

(\dots ((a_{k} - x_{1}) r_{1, k} - x_{2}) r_{2, k} - \dots - x_{k - 1}) r_{k - 1, k} \equiv x_{k} (mod p_{k})

a_{k} i = 1 \prod k - 1 r_{i, i + 1} - x_{1} i = 1 \prod k - 1 r_{i, i + 1} - x_{2} i = 2 \prod k - 1 r_{i, i + 1} - \dots - x_{k - 1} r_{k - 1, k} \equiv x_{k} (mod p_{k})

a = a_{1} + (a_{2} - x_{1}) r_{1, 2} p_{1} + ((a_{3} - x_{1}) r_{1, 2} - x_{2}) r_{2, 3} p_{1} p_{2} + \dots +

a = a_{1} + (a_{2} - a_{1}) r_{1, 2} p_{1} + ((a_{3} - a_{1}) r_{1, 2} - (a_{2} - a_{1}) r_{1, 2}) r_{2, 3} p_{1} p_{2} + x_{k} p_{1} \dots p_{k - 1} = a_{1} + (a_{2} - a_{1}) r_{1, 2} p_{1} + (a_{3} - a_{2} r_{1, 2}) r_{2, 3} p_{1} p_{2}

Quartz