---
title: 中國餘式定理 CRT
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# 中國餘式定理 CRT
## 簡介
Chinese Remainder Theorem (CRT)

若 $N = p \times q$ 其中 $p, q$ 互質
所有的 $a \in Z_N$ 可以 one-to-one mapping 到一張圖表
mapping 到的座標為 $(a\ mod\ p,\ a\ mod\ q)$

直接看一個例子，$N = 15 = 3 \times 5$
圖表的 y 軸為 $a\ mod\ 3$ ; x 軸為 $a\ mod\ 5$

| y軸\x軸 | 0 | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -- | -- | -- |
| 0 | 0 | 6 | 12 | 3 | 9
| 1 | 10 | 1 | 7 | 13 | 4
| 2 | 5 | 11 | 2 | 8 | 14

給 $a$ 能很好得出座標
但給座標要如何反推 $a$ ?

舉個例子，若已知 $(a\ mod\ 7,\ a\ mod\ 5)$ 系統，求在 $(4,\ 3)$ 座標上的數字 $x$

首先知道 $x \in Z_{7 \times 5}$

根據 $x \equiv 4\ (mod\ 7)$ 可得知 $x = 7 \times u + 4$
再根據 $x \equiv 3\ (mod\ 5)$
替換為
$7u + 4 \equiv 3\ (mod\ 5)$
$7u \equiv 3-4 \equiv 3-4+5 \equiv 4\ (mod\ 5)$
$2u \equiv 4\ (mod\ 5)$
$u \equiv 2\ (mod\ 5)$

求得 $u = 2,\ x = 7 \times 2 + 4 = 18$

## 擴展
剛剛的方式僅能簡單處理由兩個質數組成的 $N$
現在要擴展到

**由 $K$ 個不同的質數$\{P_1, P_2, ..., P_K\}$組成的 $N$，求快速從座標系統 $(a\ mod\ P_1, a\ mod\ P_2, ..., a\ mod\ P_K)$推回 x 的解法**

$$
x \equiv \sum_{i = 1}^Ka_i \times M_i \times y_i\ (mod\ N)
$$

- $a_i$: 第 i 軸上的係數
- $M_i = \frac{P}{P_i}$ , 其中 $P = \prod_{j = 1}^KP_j$
- $y_i \times M_i \equiv 1\ (mod\ P_i)$

### 例子
以上面舉過的例子
> 若已知 $(a\ mod\ 7,\ a\ mod\ 5)$ 系統，求在 $(4,\ 3)$ 座標上的數字 $x$
>

| 軸 | $a_i$ | $M_i$ | $y_i$ |
| -- | -------- | -------- | -------- |
| $mod\ 7$ | 4 | 5 | 3
| $mod\ 5$ | 3 | 7 | 3

$x \equiv a_1 \times M_1 \times y_1 + a_2 \times M_2 \times y_2\ (mod\ 35)$
$x \equiv 60 + 63 \equiv 123\ (mod\ 35)$
$x \equiv 18$