密码学数学基础（三）同余方程
三、同余方程
3.1 同余方程的概念
定义3.1：设\(f(x)\)为整系数多项式 \[ f(x)=a_nx^n+\cdots+a_1x+a_0 \] 则含有变量\(x\)的同余式 \[ f(x)\equiv0\pmod m \] 叫做模\(m\)的同余方程。若整数\(c\)满足 \[ f(c)\equiv0\pmod m \] 则\(c\)叫做同余方程的解。
显然若\(c\)是同余方程的解，则同余类\(c\bmod m\)中所有的数都是该同余方程的解，我们把同余类\(c\bmod m\)称为同余方程\(f(x)\equiv0\pmod m\)的一个解，记为 \[ x\equiv c\pmod m \] 满足解的同余类的个数称为解数。
定义3.2：在定义3.1的条件下，若\(m\nmid a_n\)，则同余方程的次数为\(n\)；若\(m\mid a_j,k+1\le j\le n\)，且\(m\nmid a_k\)，则同余方程的次数为\(k\)。
因此同余方程的次数并不一定等于多项式的次数。下面给出同余方程的一些性质：
定理3.1：
若\(f(x)\equiv g(x)\pmod m\)，则同余方程\(f(x)\equiv0\pmod m\)与同余方程\(g(x)\equiv0\pmod m\)等价；
若 \[ f(x)=q(x)h(x)+r(x) \] 且同余方程\(h(x)\equiv0\pmod m\)为恒等同余式（即方程的解数为\(m\)），则同余方程\(f(x)\equiv0\pmod m\)与\(r(x)\equiv0\pmod m\)等价。
若\((a,m)=1\)，则同余方程\(f(x)\equiv0\pmod m\)和同余方程\(af(x)\equiv0\pmod m\)等价。
根据上述性质第2条，可以通过构造模\(m\)的恒等同余式来降低方程的次数，如根据费马小定理可知 \[ h(x)=x^p-x\equiv0\pmod m \] 为恒等同余式。
定理3.2：若\(p\)为素数，同余方程\(f(x)\equiv0\pmod p\)的次数为\(k\)，解的个数为\(T\)，则 \[ T\le min(p,k) \]
证明：因为剩余类才只有\(p\)个，所以\(T\le p\)。如果\(a\)是一个解，则\(f(x)\)可以分解为\(f(x)\equiv q(x)(x-a)\pmod m\)，次数为\(k\)的方程至多只能分解\(k\)次，因此\(T\le k\)。
定理3.3：设整数\(d\mid m\)，若同余方程\(f(x)\equiv0\pmod m\)有解，则\(f(x)\equiv0\pmod d\)有解。
根据同余的性质（定理2.5）不难得出上述结论，该定理可以反过来用于判断一个方程无解。
例3.1：
解同余方程：\(f(x)=4x^2-27x-9\equiv0\pmod{15}\)。
解：将\(0,1,2,3,4\)代入\(f(x)=4x^2-27x-9\equiv0\pmod{5}\)无解，由定理3.3，原方程无解。
解同余方程：\(f(x)=2x^5-x^3-2x+1\equiv0\pmod 3\)。
解：\(f(x)=(2x^2+1)(x^3-x)-x+1\equiv0\pmod 3\)，等价于\(-x+1\equiv0\pmod 3\)，解为\(x\equiv1\pmod 3\)。
3.2 一次同余方程
本节讨论一次同余方程 \[ ax\equiv b\pmod m \] 解的情况以及求解方法。
定理3.4：若\((a,m)=1\)，则同余方程\(ax\equiv b\pmod m\)有且仅有一个解。
证明：当\((a,m)=1\)时，\(a^{-1}\)存在，两边同时乘以\(a^{-1}\)可得解为\(x\equiv a^{-1}b\pmod m\)。若还存在另一个解\(x'\)，则\(ax'\equiv ax\equiv b\pmod m\)，因为\((a,m)=1\)，两边同时约掉\(a\)有\(x'\equiv x\pmod m\)，因此解唯一。
结合欧拉定理可知，当\((a,m)=1\)时，方程的唯一解为\(x\equiv a^{\varphi(m)-1}b\pmod m\)。
定理3.5：同余方程\(ax\equiv b\pmod m\)有解的充要条件是\((a,m)\mid b\)。在有解时，解数等于\((a,m)\)。若\(x_0\)是它的一个解，则它的\((a,m)\)个解是 \[ x\equiv x_0+\frac{m}{(a,m)}t\pmod m,\quad t=0,1,\cdots,(a,m)-1 \]
证明：
必要性：同余方程\(ax\equiv b\pmod m\)有解，则存在\(x_0,y_0\)，使得\(ax_0+my_0=b\)，由定理1.8可知\((a,m)\mid b\)。
充分性：设\(d=(a,m)\)，若\((a,m)\mid b\)，由定理2.6可知，\(ax\equiv b\pmod m\)等价于 \[ \frac{a}{d}x\equiv\frac{b}{d}\pmod{\frac{m}{d}} \] 因为\((\frac{a}{d},\frac{m}{d})=1\)，由定理3.4可得方程有解。
设同余方程\(ax\equiv b\pmod m\)的特解为\(x_0\)，任意解为\(x\)，他们都是\(\frac{a}{d}x\equiv\frac{b}{d}\pmod{\frac{m}{d}}\)的唯一解，即\(x\equiv x_0\pmod{\frac{m}{d}}\)。因此，对于任意的\(x\)，只要满足\(x\equiv x_0\pmod{\frac{m}{d}}\)就是\(ax\equiv b\pmod m\)的解。显然在模\(m\)的剩余类中，满足该条件的剩余类有\(d\)个，即 \[ x_0+\frac{m}{d}t\bmod m,\quad t=0,1,\cdots,d-1 \]
一次同余方程\(ax\equiv b\pmod m\)求解等价于求\(x\)使得\(ax+my=b\)，因此可以利用扩展欧几里得算法求出\(ax_0+my_0=d\)的解，再扩大\(\frac{b}{d}\)倍即可，算法如下。
# ax = b (mod m)
d, x0, y0 = exgcd(a, m)
if b % d != 0:
raise ArithmeticError('无解')
x = (b // d * x0) % m
print(x)当\(d=(a,m)\nmid b\)时无解，最后取模\(m\)只是让结果的范围在\([0,m)\)之间。
3.3 中国剩余定理
定义3.3：设\(f_i(x)\)是整系数多项式，\(1\le i\le k\)，我们把含有变量\(x\)的一组同余式 \[ f_i(x)\equiv0\pmod{m_i},\quad1\le i\le k \] 称为同余方程组。若整数\(c\)同时满足 \[ f_i(c)\equiv0\pmod{m_i},\quad1\le i\le k \] 则称\(c\)是同余方程组的解。
显然若\(c\)是同余方程组的解，则同余类\(c\bmod m,m=[m_1,\cdots,m_k]\)中所有的数都是该同余方程组的解，我们把同余类\(c\bmod m\)称为同余方程组的一个解，满足解的同余类的个数称为解数。易知同余方程组至多有\(m\)个解，且只要一个方程无解，则同余方程组无解。
下面的中国剩余定理（Chinese Remainder Theorem，CRT，或孙子定理）给出了\(m_1,\cdots,m_k\)两两既约时，一次同余方程组解的情况。
定理3.6（中国剩余定理）：设\(m_1,\cdots,m_k\)是两两既约的正整数，那么对任意整数\(a_1,\cdots,a_k\)，一次同余方程组 \[ x\equiv a_i\pmod{m_i},\quad1\le i\le k \] 必有唯一解，这个解是 \[ x\equiv M_1M_1^{-1}a_1+\cdots+M_kM_k^{-1}a_k\pmod m \] 其中 \[ \begin{align} m=m_1\cdots m_k=m_iM_i&,\quad 1\le i\le k\\ M_iM_i^{-1}\equiv1\pmod{m_i}&,\quad 1\le i\le k \end{align} \]
证明：
由定理2.8，\(x\equiv M_1M_1^{-1}a_1+\cdots+M_kM_k^{-1}a_k\pmod m\)等价于 \[ x\equiv M_1M_1^{-1}a_1+\cdots+M_kM_k^{-1}a_k\pmod{m_i},\quad 1\le i\le k \] 化简得\(x\equiv M_iM_i^{-1}a_i\equiv a_i\pmod{m_i},1\le i\le k\)，因此\(x\)是方程组的解。
下面证明唯一性，若同余方程组有两个解\(x_1,x_2\)，则有 \[ x_1\equiv x_2\equiv a_i\pmod{m_i},\quad1\le i\le k \] 所以 \[ m_i\mid x_1-x_2,\quad1\le i\le k \] 因为\(m_1,\cdots,m_k\)两两既约，所以\(m=m_1\cdots m_k\mid x_1-x_2\)，即\(x_1\equiv x_2\pmod{m}\)，因此解唯一。
对于一般的一组模\(m_1,\cdots,m_k\)，总是可以将其分解为两两既约的形式，从而使用中国剩余定理求解。
例3.2：
解同余方程组 \[ \begin{cases} x\equiv2\pmod 3\\ x\equiv3\pmod 5\\ x\equiv2\pmod 7 \end{cases} \] 解：模数两两既约，直接用中国剩余定理求解。计算得 \[ \begin{align} &M_1=35,\quad M_2=21,\quad M_3=15\\ &M_1^{-1}=2,\quad M_2^{-1}=1,\quad M_3^{-1}=1\\ x&\equiv35\times2\times2+21\times1\times3+15\times1\times2\\ &\equiv140+63+30\\ &\equiv23\pmod{105} \end{align} \]
解同余方程组
\[ \begin{cases} 4x\equiv14\pmod{15}\\ 9x\equiv11\pmod{20} \end{cases} \] 解：将模分解如下 \[ \begin{cases} 4x\equiv14\pmod{3}\\ 4x\equiv14\pmod{5}\\ 9x\equiv11\pmod{4}\\ 9x\equiv11\pmod{5} \end{cases}\Rightarrow \begin{cases} x\equiv2\pmod{3}\\ 4x\equiv4\pmod{5}\\ x\equiv3\pmod{4}\\ 4x\equiv1\pmod{5} \end{cases} \Rightarrow \begin{cases} x\equiv2\pmod{3}\\ x\equiv1\pmod{5}\\ x\equiv3\pmod{4}\\ x\equiv4\pmod{5} \end{cases} \] 第2个和第4个方程矛盾，因此无解。
3.4 一般同余方程
高次的同余方程没有一般的求解方法，下面仅简要描述求解一般同余方程的步骤。
定理3.7：当\(m=m_1\cdots m_k\)，且\(m_i(1\le i\le k)\)两两互素时，同余方程 \[ f(x)\equiv0\pmod m \] 与同余方程组 \[ f(x)\equiv0\pmod{m_i},\quad1\le i\le k \] 同解。
该定理由同余的性质容易得到。由此求解一般的同余方程，步骤归纳如下：
- 根据定理3.7将求解同余方程\(f(x)\equiv0\pmod m\)转化为求解同余方程组\(f(x)\equiv0\pmod{m_i},1\le i\le k\)；
- 分别求解\(f(x)\equiv0\pmod{m_i},1\le i\le k\)得到每一个方程的解为\(x\equiv a_{ij}\pmod{m_i},1\le j\le l\)，\(l\)表示每个方程的解数；
- 取每个方程的一个解\(x\equiv a_{ij}\pmod{m_i}\)，把它们拿出来组成一次同余方程组，用中国剩余定理即可求得一个解。
因此现在要解决的问题就是第2步如何求解，即当我们把\(m\)因式分解为\(p_1^{\alpha_1}\cdots p_k^{\alpha_k}\)后，如何求解 \[ f(x)\equiv0\pmod{p^\alpha} \] 下面的定理给出了一种递推求解的方法。
定理3.8：若\(f(x)\equiv0\pmod{p^{\alpha-1}}\)的解为\(x\equiv c_1,\cdots,c_s\pmod{p^{\alpha-1}}\)，则方程 \[ f(x)\equiv0\pmod{p^\alpha} \] 的解有\(x\equiv c_j+p^{\alpha-1}y\pmod{p^\alpha},1\le j\le s\)的形式，其中\(y\)是 \[ f'(c_j)y\equiv-\frac{f(c_j)}{p^{\alpha-1}}\pmod p \] 的解。
由于本节不是重点，故该定理仅作了解，不再证明。
3.5 二次剩余
由上一节可知求解同余方程可以归结为求\(f(x)\equiv0\pmod p\)的解，其中\(p\)为素数。本节讨论的二次剩余都是针对\(p\)为奇素数（或素数\(p>2\)）的情况。
二次同余方程的一般形式为 \[ ax^2+bx+c\equiv0\pmod p \] 若\((a,p)=1\)，则可以通过乘\(a^{-1}\)和凑平方的方式化为如下标准形式： \[ x^2\equiv d\pmod p \] 若\(p\mid d\)，则方程有唯一解\(x\equiv0\pmod p\)，因此下面的讨论都假定\((p,d)=1\)。
定义3.4：设\(p\)为奇素数，\((p,d)=1\)。若同余方程\(x^2\equiv d\pmod p\)有解，则称\(d\)是模\(p\)的二次剩余；若无解，则称\(d\)是模\(p\)的二次非剩余。记模\(p\)的二次剩余和二次非剩余的全体分别为 \[ \begin{align} QR_p&=\{a|a\in\mathbb Z_p^*,\ \exists x\in\mathbb Z_p^*,\ x^2\equiv a\pmod p\}\\ QNR_p&=\{a|a\in\mathbb Z_p^*,\ \forall x\in\mathbb Z_p^*,\ x^2\not\equiv a\pmod p\} \end{align} \]
\(\mathbb Z_p^*\)即模\(p\)的既约剩余类的集合（见定义2.5），简单来说\(\mathbb Z_p^*=\{1,\cdots,p-1\}\)。
定理3.9：在上述定义下，模\(p\)的既约剩余系中二次剩余与二次非剩余各占一半，即 \[ |QR_p|=|QNR_p|=\frac{p-1}{2} \]
证明：对于同余方程\(x^2\equiv d\pmod p\)，写出\(x\)的所有取值如下（模\(p\)的绝对既约剩余系） \[ -\frac{p-1}{2},-\frac{p-1}{2}+1,\cdots,-1,1,\cdots,\frac{p-1}{2}-1,\frac{p-1}{2} \] 由于左边负的部分和右边正的部分各自平方之后值相同，因此只需考虑正的部分。现在我们来看\(x\)取正值\(1,\cdots,\frac{p-1}{2}\)的时候\(d\)是否相同：设\(1\le i,j\le\frac{p-1}{2}\)，如果其平方相同，有 \[ \begin{align} i^2\equiv j^2\pmod p&\Leftrightarrow p\mid(i+j)(i-j)\\ &\Leftrightarrow p\mid i-j\\ &\Leftrightarrow i=j \end{align} \] 这说明只有\(x\)取值相同的时候\(d\equiv x^2\pmod p\)才相同，反过来如果\(x\)取值不同\(d\)也必定不同。因此\(x\)取\(1,\cdots,\frac{p-1}{2}\)对应了\(\frac{p-1}{2}\)个不同的\(d\)，所以二次剩余的个数为\(\frac{p-1}{2}\)，二次非剩余的个数为\((p-1)-\frac{p-1}{2}=\frac{p-1}{2}\)。
从上面定理的证明可以看出，同余方程\(x^2\equiv d\pmod p\)要么无解，要么有2个解。下面给出判定\(d\)是否为模\(p\)的二次剩余的方法。
定理3.10（欧拉判别法）：设\(p\)为奇素数，\((p,d)=1\)，那么\(d\)为模\(p\)的二次剩余的充要条件是 \[ d^{\frac{p-1}{2}}\equiv1\pmod p \] \(d\)为模\(p\)的二次非剩余的充要条件是 \[ d^{\frac{p-1}{2}}\equiv-1\pmod p \]
证明：由欧拉定理，有 \[ d^{p-1}\equiv1\pmod p\Leftrightarrow(d^{\frac{p-1}{2}}-1)(d^{\frac{p-1}{2}}+1)\equiv0\pmod p \] 因此要么\(d^{\frac{p-1}{2}}\equiv1\pmod p\)，要么\(d^{\frac{p-1}{2}}\equiv-1\pmod p\)，证明一个即可。
下面证明：\(d\)为模\(p\)的二次剩余的充要条件是\(d^{\frac{p-1}{2}}\equiv1\pmod p\)。
必要性：若\(d\)为模\(p\)的二次剩余，则存在\(x_0\)使得\(x_0^2\equiv d\pmod p\)，由欧拉定理可得 \[ d^{\frac{p-1}{2}}\equiv x_0^{p-1}\equiv1\pmod p \]
充分性：若\(d^{\frac{p-1}{2}}\equiv1\pmod p\)，采用反证法，设\(d\)不是二次剩余。考虑一次同余方程\(ax\equiv d\pmod p\)，当\(a\)取模\(p\)的既约剩余系中的某个\(r_i\)时，方程只有唯一的解\(r_j\)，\(r_i\)和\(r_j\)一一对应且\(r_i\ne r_j\)（因为假设\(d\)不是二次剩余），因此模\(p\)的既约剩余系中的数两两一组配对，共\(\frac{p-1}{2}\)对，每一对\(r_ir_j\equiv d\pmod p\)，由威尔逊定理有 \[ \prod_{r\bmod p}r\equiv d^{\frac{p-1}{2}}\equiv-1\pmod p \] 与假设不符，因此\(d\)是二次剩余。
由欧拉判别法可以容易得出：若\(p\equiv1\pmod4\)，则\(-1\)是模\(p\)的二次剩余；若\(p\equiv3\pmod4\)，则\(-1\)是模\(p\)的二次非剩余。因为\(p\)是奇素数，\(p\)模\(4\)实际上只有\(1\)和\(3\)两种取值，所以这个性质涵盖了所有的\(p\)，由它可以快速判断\(-1\)是否是二次剩余。
定理3.11：设\(p\)为奇素数，\((p,d_1)=1\)，\((p,d_2)=1\)。那么\(d_1d_2\)是模\(p\)的二次剩余的充要条件是\(d_1,d_2\)均是模\(p\)的二次剩余或二次非剩余；\(d_1d_2\)是模\(p\)的二次非剩余的充要条件是\(d_1,d_2\)一个是模\(p\)的二次剩余，一个是模\(p\)的二次非剩余。
证明：定理很简单，下面会用到，还是说一下。 \[ (d_1d_2)^{\frac{p-1}{2}}\equiv d_1^{\frac{p-1}{2}}\cdot d_2^{\frac{p-1}{2}}\equiv\pm1\pmod p \] 因为\(d^{\frac{p-1}{2}}\pmod p\)要么等于\(1\)要么等于\(-1\)，所以当\(d_1^{\frac{p-1}{2}}\)和\(d_2^{\frac{p-1}{2}}\)同号时\(d_1d_2\)为二次剩余，异号时为二次非剩余。
例3.3：判断下列同余方程的解数。
\(x^2\equiv3\pmod{91}\)。
解：等价于 \[ \begin{cases} x^2\equiv3\pmod7\\ x^2\equiv3\pmod{13} \end{cases} \] 由欧拉判别法，\(3^{\frac{7-1}{2}}\equiv-1\pmod7\)，即\(3\)不是模\(7\)的二次剩余，因此无解。
\(x^2\equiv4\pmod{55}\)。
解：等价于 \[ \begin{cases} x^2\equiv4\pmod5\\ x^2\equiv4\pmod{11} \end{cases} \] 由欧拉判别法，\(4\)是模\(5\)和模\(11\)的二次剩余，因此方程组的两个方程各有2个解，原方程共\(2\times2=4\)个解。
3.5 勒让德（Legendre）符号
本节和下一节介绍非常重要的两个数论函数——勒让德符号和雅可比符号。
定义3.5：设\(p\)为奇素数，令 \[ \left(\frac{d}{p}\right)= \begin{cases} 0&p\mid d\\ 1&d为p的二次剩余\\ -1&d为p的二次非剩余 \end{cases} \] 称\(\left(\frac{d}{p}\right)\)为模\(p\)的勒让德符号。
勒让德符号有以下性质，结合欧拉判别法和定理3.11容易得出前4条。第5条是\(d=2\)时的简化公式，会使用即可，不再证明。
定理3.12：
\[ \left(\frac{d}{p}\right)\equiv d^{\frac{p-1}{2}}\pmod p \]
\[ \left(\frac{d}{p}\right)=\left(\frac{d+p}{p}\right) \]
\[ \left(\frac{dc}{p}\right)=\left(\frac{d}{p}\right)\left(\frac{c}{p}\right) \]
\[ \left(\frac{-1}{p}\right)= \begin{cases} 1&p\equiv1\pmod4\\ -1&p\equiv3\pmod4 \end{cases}=(-1)^\frac{p-1}{2} \]
\[ \left(\frac{2}{p}\right)=(-1)^\frac{p^2-1}{8} \]
下面给出本节最重要的二次互反律。
定理3.13（二次互反律）：设\(p,q\)均为奇素数，\(p\ne q\)，那么 \[ \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}} \]
证明可以参考这篇帖子，因为证明繁琐，这里就略去了。
由于\(\left(\frac{q}{p}\right)\)和\(\left(\frac{p}{q}\right)\)都是\(1\)或\(-1\)，因此将其中的一项移到等号右边也是可以的，即 \[ \left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\left(\frac{p}{q}\right) \] 二次互反律可以用于快速求解勒让德符号的值，看下面的例子。
例3.4：求\(\left(\frac{22}{47}\right)\)。
解：根据勒让德符号的性质得 \[ \left(\frac{22}{47}\right)=\left(\frac{2}{47}\right)\left(\frac{11}{47}\right) \] 根据定理3.12第5条得 \[ \left(\frac{2}{47}\right)=(-1)^\frac{47^2-1}{8}=1 \] 根据二次互反律得 \[ \left(\frac{11}{47}\right)=(-1)^{23\times5}\left(\frac{47}{11}\right)=-\left(\frac{3}{11}\right)=-1 \] 因此 \[ \left(\frac{22}{47}\right)=1\times-1=-1 \]
3.6 雅可比（Jacobi）符号
定义3.6：设奇数\(P>1\)，\(P=p_1p_2\cdots p_n\)，其中\(p_i(1\le i\le n)\)是素数。把 \[ \left(\frac{d}{P}\right)=\left(\frac{d}{p_1}\right)\left(\frac{d}{p_2}\right)\cdots\left(\frac{d}{p_n}\right) \] 称为雅可比符号。此处的\(\left(\frac{d}{p_i}\right)\)是勒让德符号。
与勒让德符号类似，雅可比符号也有如下性质，由定义可以直接推出，不再证明。
定理3.14：
- \((d,P)\ne1\)时，\(\left(\frac{d}{P}\right)=0\)；
- \((d,P)=1\)时，\(\left(\frac{d}{P}\right)=\pm1\)；
- \(\left(\frac{d}{P}\right)=\left(\frac{d+P}{P}\right)\)；
- \(\left(\frac{dc}{P}\right)=\left(\frac{d}{P}\right)\left(\frac{c}{P}\right)\)。
对于特殊的\(d\)，雅可比符号也有如下简化公式，不再证明。
定理3.15：
\[ \left(\frac{-1}{P}\right)=(-1)^\frac{P-1}{2} \]
\[ \left(\frac{2}{P}\right)=(-1)^\frac{P^2-1}{8} \]
另外雅可比符号也满足二次互反律，不再证明。
定理3.16（二次互反律）：若奇数\(P>1,Q>1\)，且\((P,Q)=1\)，则 \[ \left(\frac{Q}{P}\right)\left(\frac{P}{Q}\right)=(-1)^{\frac{P-1}{2}\cdot\frac{Q-1}{2}} \]
3.7 SageMath
# 中国剩余定理 crt(余数列表, 模数列表)
sage: crt([2, 3, 2], [3, 5, 7])
23# 求模n的二次剩余全体
sage: quadratic_residues(5)
[0, 1, 4]# 计算勒让德符号
sage: legendre_symbol(22, 47)
-1