FHE之代数基础（二）中国剩余定理

引言

中国剩余定理(Chinese Remainder theorem, CRT)，又称孙子定理，是数论中一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的判定及求解方法。其问题最早可见于南北朝时期的《孙子算经》，描述如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

白话文：一个整数除以3余2，除以5余3，除以7余2，求该整数。

《孙子算经》

这个问题怎么解呢？最初对该问题给出完整系统解答的是宋朝数学家秦九韶，后来明朝数学家程大位将该解法收录在《孙子歌诀》中：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知

白话文：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后再减去105或者105的整数倍，即得答案。

《孙子歌诀》

将该解法用算式表示即为：

$70\times 2+21\times 3+15\times 2=233=2\times 105+23$

从特殊到一般

定理叙述

若$q_1, q_2,...,q_n$均为大于1的整数，那么当$q_1, q_2,...,q_n$两两互质时，对任意$a_i\in \mathbb{Z}$且$0\le a_i<q_i(0<i\le n)$，以下一元线性同余方程组：

$$(S):\begin{cases}{\begin{matrix}x\equiv a_{1}{\pmod {q_{1}}}\\x\equiv a_{2}{\pmod {q_{2}}}\\\vdots \qquad \qquad \qquad \\x\equiv a_{n}{\pmod {q_{n}}}\end{matrix}} \end{cases}$$

有解。其中一个解可通过如下方法构造得到：

$$记\begin{cases} Q=q_{1}\times q_{2}\times \cdots \times q_{n}=\prod _{i=1}^{n}q_{i}\\ Q_{i}=Q/q_{i},\;\;\forall i\in \{1,2,\cdots ,n\}\\Q_i^{-1}Q_i\equiv 1\pmod{q_i},\;\;\forall i\in \{1,2,\cdots ,n\}\end{cases}$$

$$x\equiv\sum\limits_{i=1}^{n}a_iQ_i^{-1}Q_i\equiv\sum\limits_{i=1}^{n}{\left(a_i\times\left[ \left( \frac{Q}{q_i} \right)^{-1} \right]_{q_i}\right)_{q_i}\times\frac{Q}{q_i}}\pmod Q$$

通解：$x\equiv\sum\limits_{i=1}^{n}a_iQ_i^{-1}Q_i+kQ, \;\;k\in \mathbb{Z}$

在模Q意义下有唯一解：$x\equiv\sum\limits_{i=1}^{n}a_iQ_i^{-1}Q_i\pmod Q$

例子

我们重新看《孙子算经》中的例子，该问题定义了以下方程组

$$(S):\begin{cases}x\equiv 2{\pmod {3}}\\x\equiv 3{\pmod {5}}\\x\equiv 2{\pmod {7}}\end{cases}$$

三个模数$\begin{cases}q_1=3\\\\q_2=5\\\\q_3=7\end{cases}$，乘积$Q=105$，对应$\begin{cases}Q_1=\frac{105}{3}=35\\\\Q_2=\frac{105}{5}=21\\\\Q_3=\frac{105}{7}=15 \end{cases}$，

求数论倒数（乘法逆元）$\begin{cases}Q_1^{-1}=2\pmod3\\\\Q_2^{-1}=1\pmod5\\\\Q_3^{-1}= 1\pmod7\end{cases}$。由此我们可以计算出该模数集(i.e.,$3,5,7$)的基础解：

$$70=2\times 35\equiv \begin{cases}{\begin{matrix}1{\pmod {3}}\\0{\pmod {5}}\\0{\pmod {7}}\end{matrix}},\end{cases}\\21=1\times 21\equiv \begin{cases}{\begin{matrix}0{\pmod {3}}\\1{\pmod {5}}\\0{\pmod {7}}\end{matrix}},\end{cases}\\15=1\times 15\equiv \begin{cases}{\begin{matrix}0{\pmod {3}}\\0{\pmod {5}}\\1{\pmod {7}}\end{matrix}},\end{cases}$$

可以看到，所谓“基础解”，即轮流对其中一个模数取模为1，对其他模数取模为0得到的一组解。它可以由$Q_i^{-1}Q_i,\;\;\forall i\in \{1,2,\cdots ,n\}$计算得到。

而后，我们将这几组$Q_i^{-1}Q_i$累加：

$$2\times 70+3\times 21+2\times 15\equiv \begin{cases}{\begin{matrix}2\times 1+3\times 0+2\times 0\equiv 2{\pmod {3}}\\\\2\times 0+3\times 1+2\times 0\equiv 3{\pmod {5}}\\\\2\times 0+3\times 0+2\times 1\equiv 2{\pmod {7}}\end{matrix}}\end{cases}=233$$

通解：$x=233+k\times105,\;k\in\mathbb{Z}$

最小正整数解：$x=233-2\times105=23$

剩余数表示系统(RNS)

由CRT，我们可以构建一套全新的数字表示系统——剩余数表示系统(Residue Number System, RNS)。这是一个将数值很大的数表示为几个数值小的数的系统。

构建方式

一个RNS系统由一个两两互质的模数集(moduli)定义：

$\{q_{1},q_{2},q_{3},\ldots ,q_{n}\}$

在该模数集下，任意整数$x$可表示为：

$\{x_{1},x_{2},x_{3},\ldots ,x_{n}\},\;x_{i}=x\pmod{q_{i}}$

运算

在RNS系统下，原数$x$的加减乘除运算可以分解为每个$x_i$的运算。

我们以模数集$(8,7,5,3)$为例：

这样分解的好处在于，当$x$很大的时候，我们不必直接对$x$进行运算，而是可以并行地对每个小数$x_i$进行运算，提高速度。

下图展示了RNS的ALU结构：

拓展

更多更详细的内容，可参见

引用站外地址

【硬件算法笔记04】剩余数表示系统

binder

更高的视角：环同构

整数环

RNS：向我们揭示了一个整数环的自同构：

$$x\bmod q \cong (|x|_{q_1},\cdots,|x|_{q_k}),即\mathbb{Z}_q \cong \prod_{i=1}^k\mathbb{Z}_{q_i}。$$

多项式环

引理

令$(R,+,·)$是一个交换环，而$(I_i)_{1\le i\le n}$是$R$的一族两两互素的理想(ideal)，即对任何$i\ne j$均有$I_i+I_j=R$，由交换环性质，有

$$I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{n}$$

此时我们有一组同构：

$${\begin{aligned}R/I&\cong (R/I_{1})\times \cdots \times (R/I_{n})\\\\x{\bmod {I}}&\cong (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{n})\end{aligned}}$$

特别的，当$\bigcap _{i=1}^{k}I_{i}=0$时，有以下同构：

$$\varphi :R\cong (R/I_{1})\times \cdots \times (R/I_{n})$$

有了以上引理后，由RNS定义的整数环同构的可以自然而然推广到多项式环上。

多项式环同构

若已知 $R_q = \mathbb{Z}_q[X]/\left< f(X) \right>$ 且 (在 $\mathbb{Z}_q[X]$ 上) $f(x)=g(x)\cdot h(x)$ ，

其中 $g(x)$ 与 $h(x)$ 互素，则以下映射为同构映射：

$$\pi:\mathbb{Z}_q[X]/\left< f(X) \right>\rightarrow\mathbb{Z}_q[X]/\left< g(X) \right>\times\mathbb{Z}_q[X]/\left< h(X) \right> \\ 简记为P_{d}(x)\mapsto \left( A_{d_1}(x), B_{d_2}(x)\right)$$

其中假设 $d=d_1+d_2$ 分别是多项式 $f(x),g(x),h(x)$ 的次数，

并且

$$\begin{cases}A_{d_1}(x) = P_d(x) \mod g(x)\\\\ B_{d_2}(x) = P_d(x) \mod h(x) \end{cases}$$

也就是说, $R_q$上的 $d$ 次多项式 $P_d(x)$ ，可转换为$P_d(x)_\pmod{g(x)}$ 得到的 $d_1$ 次多项式 $A_d(x)$ 和 $P_d(x)\pmod{h(x)}$ 得到的 $d_2$ 次多项式$B_d(x)$ 。该转换为同构映射。

基于该多项式环的同构，我们可以引出NTT。