密码学数学基础 笔记 7：从模平方根出发，理解二次剩余、欧拉判别法、Legendre 符号、二次互反律与 Jacobi 符号，再求解素数和素数幂模数下的二次同余方程

二次剩余与二次互反律

上一篇用费马小定理和欧拉定理研究模幂。这一篇把问题反过来：给定 $a$ 和模数 $m$，什么时候存在 $x$，使得

$$x^2\equiv a\pmod m$$

这包含三个不同的问题：判断是否有解、计算一个解，以及确定全部解的个数。先研究奇素数模数，再借助素数幂提升与中国剩余定理处理合数模数

从二次同余到二次剩余

对奇素数 $p$，若 $p\nmid A$，一般二次同余方程

$$Ax^2+Bx+C\equiv0\pmod p$$

可以通过配方改写为

$$(2Ax+B)^2\equiv B^2-4AC\pmod p$$

令 $y=2Ax+B$、$\Delta=B^2-4AC$，便得到 $y^2\equiv\Delta\pmod p$。因为 $2A$ 可逆，求出 $y$ 后可以唯一恢复 $x\equiv(y-B)(2A)^{-1}\pmod p$。因此，模平方根是求解这类二次同余方程的核心

设 $m>1$ 且 $\gcd(a,m)=1$。若 $x^2\equiv a\pmod m$ 有解，就称 $a$ 是模 $m$ 的二次剩余（quadratic residue，QR）；否则称为二次非剩余（quadratic nonresidue，QNR）。本文沿用讲义的约定，只在可逆剩余类中区分二次剩余与非剩余

以模 $13$ 为例，先计算前一半非零剩余类的平方：

由于 $(13-x)^2\equiv x^2\pmod{13}$，后一半不会产生新的平方值。因此

$$\mathrm{QR}_{13}=\{1,3,4,9,10,12\},\qquad \mathrm{QNR}_{13}=\{2,5,6,7,8,11\}$$

为什么恰好一半是平方

设 $p$ 是奇素数。若 $x^2\equiv y^2\pmod p$，则

$$p\mid(x-y)(x+y) \Longrightarrow x\equiv y\pmod p\quad\text{或}\quad x\equiv-y\pmod p$$

所以每个非零平方值恰好对应两个不同的平方根 $x,-x$。将 $p-1$ 个非零剩余类两两配对，得到

$$\boxed{|\mathrm{QR}_p|=|\mathrm{QNR}_p|=\frac{p-1}{2}}$$

这里素数条件保证了“整除乘积就整除某个因子”。合数模数下不一定只有两个根，例如 $x^2\equiv1\pmod8$ 有 $1,3,5,7$ 四个解

欧拉判别法

费马小定理说明，对 $p\nmid a$ 有

$$\left(a^{(p-1)/2}\right)^2\equiv1\pmod p$$

因此 $a^{(p-1)/2}$ 只能同余于 $1$ 或 $-1$。欧拉判别法（Euler’s criterion）进一步指出，这个符号恰好区分平方与非平方：

$$\boxed{ a^{(p-1)/2}\equiv \begin{cases} 1\pmod p,&a\in\mathrm{QR}_p\\ -1\pmod p,&a\in\mathrm{QNR}_p \end{cases}}$$

若 $a\equiv b^2\pmod p$，由费马小定理直接得到

$$a^{(p-1)/2}\equiv b^{p-1}\equiv1\pmod p$$

对于非剩余，可以沿用上一篇 Wilson 定理的配对方法。给每个非零剩余类 $x$ 分配伙伴 $ax^{-1}$，两者的乘积为 $a$，而且伙伴的伙伴仍是 $x$。只有满足 $x^2\equiv a\pmod p$ 时，$x$ 才会与自己配对

当 $a$ 是非剩余时，没有这样的自配对元素，全部 $p-1$ 个元素分成 $(p-1)/2$ 对。于是

$$a^{(p-1)/2}\equiv\prod_{x=1}^{p-1}x =(p-1)!\equiv-1\pmod p$$

最后一步使用 Wilson 定理，证明完成。实际计算时，只需用平方乘法求 $a^{(p-1)/2}\bmod p$，需要 $O(\log p)$ 次模乘法，无须枚举所有可能的平方根

Legendre 符号

对奇素数 $p$，定义 Legendre 符号

$$\left(\frac ap\right)= \begin{cases} 0,&p\mid a\\ 1,&a\text{ 是模 }p\text{ 的二次剩余}\\ -1,&a\text{ 是模 }p\text{ 的二次非剩余} \end{cases}$$

这里的括号表示一个取值为 $0,\pm1$ 的符号，不是分数。把整除情形也纳入后，欧拉判别法可以统一写成

$$\boxed{a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p}$$

Legendre 符号只取决于分子模 $p$ 的剩余类，并且具有完全乘法性：

$$\boxed{\left(\frac{ab}{p}\right) =\left(\frac ap\right)\left(\frac bp\right)}$$

这可以由 $(ab)^{(p-1)/2}=a^{(p-1)/2}b^{(p-1)/2}$ 和欧拉判别法得到。如果 $a,b$ 均不被 $p$ 整除，乘法规则就是

特别地，若 $p\nmid b$，则平方因子可以去掉：

$$\left(\frac{ab^2}{p}\right)=\left(\frac ap\right)$$

例如

$$\left(\frac{75}{97}\right) =\left(\frac{3\cdot5^2}{97}\right) =\left(\frac3{97}\right)=1$$

最后一个等号可由 $10^2\equiv3\pmod{97}$ 验证。相应地，$50^2\equiv75\pmod{97}$，两个平方根是 $50$ 和 $47$

乘法性将计算归结为 $-1$、$2$ 和奇素数的符号，接下来分别处理它们

两个补充定律与 Gauss 引理

$-1$ 什么时候是平方

将 $a=-1$ 代入欧拉判别法，得到

$$\boxed{ \left(\frac{-1}{p}\right)=(-1)^{(p-1)/2} =\begin{cases} 1,&p\equiv1\pmod4\\ -1,&p\equiv3\pmod4 \end{cases}}$$

例如 $5^2\equiv-1\pmod{13}$，但模 $7$ 的平方值只有 $1,2,4$，所以 $-1\equiv6\pmod7$ 不是平方

Gauss 引理：数一数负号

设 $h=(p-1)/2$，且 $p\nmid a$。取

$$a,2a,\ldots,ha$$

模 $p$ 的最小正剩余 $r_1,\ldots,r_h$，记其中大于 $p/2$ 的项数为 $\nu$。Gauss 引理给出

$$\boxed{\left(\frac ap\right)=(-1)^\nu}$$

证明的关键是把每个较大的 $r_i$ 替换成 $r_i-p$，使全部代表元落入 $[-h,h]$。它们的绝对值恰好是 $1,2,\ldots,h$ 的一个排列：若两个绝对值相同，就有 $ia\equiv\pm ja\pmod p$，约去 $a$ 后得到 $i\equiv\pm j\pmod p$；在 $1\le i,j\le h$ 的范围内，只能有 $i=j$

比较替换前后的乘积，便有

$$a^h h!\equiv r_1\cdots r_h \equiv(-1)^\nu h!\pmod p$$

约去可逆的 $h!$，再用欧拉判别法，即得结论。例如取 $p=13,a=2$，列表

$$2,4,6,8,10,12$$

变成

$$2,4,6,-5,-3,-1$$

共有三个负号，因此 $\left(\frac2{13}\right)=-1$

$2$ 什么时候是平方

对 $a=2$，列表 $2,4,\ldots,p-1$ 已经都是最小正剩余，其中超过 $p/2$ 的项数为

$$\nu=\frac{p-1}{2}-\left\lfloor\frac p4\right\rfloor$$

按 $p\bmod8$ 分别计算，得到

这就是第二个补充定律：

$$\boxed{ \left(\frac2p\right)=(-1)^{(p^2-1)/8} =\begin{cases} 1,&p\equiv1,7\pmod8\\ -1,&p\equiv3,5\pmod8 \end{cases}}$$

二次互反律

设 $p,q$ 是两个不同的奇素数，二次互反律把“$q$ 是否是模 $p$ 的平方”和“$p$ 是否是模 $q$ 的平方”联系起来：

$$\boxed{ \left(\frac qp\right)\left(\frac pq\right) =(-1)^{\frac{p-1}{2}\frac{q-1}{2}}}$$

因此，交换分子与分母时，只有 $p,q$ 都同余于 $3\pmod4$ 才需要变号；其他情况下符号不变。交换之后还可以对新的分子取模，这往往会把计算规模显著缩小

从 Gauss 引理到格点计数

沿用 $h=(p-1)/2$，对 $1\le i\le h$ 作带余除法：

$$iq=p\left\lfloor\frac{iq}{p}\right\rfloor+r_i, \qquad1\le r_i\le p-1$$

令 $t_i=r_i$ 或 $p-r_i$，使 $1\le t_i\le h$，并记后一个情形的项数为 $\nu$。Gauss 引理的证明说明 $t_i$ 是 $1,\ldots,h$ 的排列。每次用 $p-t_i$ 代替 $t_i$，总和的奇偶性都改变一次，因此

$$\sum_{i=1}^h r_i\equiv\sum_{i=1}^h i+\nu\pmod2$$

将带余除法求和，再利用 $p,q$ 都是奇数，得到

$$\nu\equiv\sum_{i=1}^h\left\lfloor\frac{iq}{p}\right\rfloor\pmod2$$

于是

$$\left(\frac qp\right) =(-1)^{\sum_{i=1}^{(p-1)/2}\lfloor iq/p\rfloor}$$

现在考虑矩形内的整数点

$$1\le i\le\frac{p-1}{2},\qquad 1\le j\le\frac{q-1}{2}$$

直线 $j=qi/p$ 不经过这些点，否则 $pj=qi$ 会迫使 $p\mid i$，与 $i$ 的范围矛盾。直线下方和上方的点数分别是

$$\sum_{i=1}^{(p-1)/2}\left\lfloor\frac{iq}{p}\right\rfloor, \qquad \sum_{j=1}^{(q-1)/2}\left\lfloor\frac{jp}{q}\right\rfloor$$

两个区域恰好分完矩形中的所有格点，所以

$$\sum_{i=1}^{(p-1)/2}\left\lfloor\frac{iq}{p}\right\rfloor +\sum_{j=1}^{(q-1)/2}\left\lfloor\frac{jp}{q}\right\rfloor =\frac{p-1}{2}\frac{q-1}{2}$$

将这个等式代入两个 Legendre 符号的乘积，二次互反律便得到证明

用互反律计算

例如判断 $14$ 是否是模 $137$ 的平方。因为 $137\equiv1\pmod8$，有

$$\begin{aligned} \left(\frac{14}{137}\right) &=\left(\frac2{137}\right)\left(\frac7{137}\right)\\ &=\left(\frac{137}{7}\right) =\left(\frac47\right)=1 \end{aligned}$$

所以方程有解。直接代回可验证两个根是 $39$ 和 $98$，但符号计算本身只给出了有解的结论

互反律还可以回答“固定一个数，对哪些素数模数它是平方”。例如对素数 $p>3$，

$$\left(\frac3p\right) =(-1)^{(p-1)/2}\left(\frac p3\right)$$

右侧只依赖 $p\bmod4$ 和 $p\bmod3$。将两者合并为模 $12$ 的条件，得到

$$\boxed{ \left(\frac3p\right)= \begin{cases} 1,&p\equiv1,11\pmod{12}\\ -1,&p\equiv5,7\pmod{12} \end{cases}}$$

Jacobi 符号：不用分解也能计算

如果总是先分解分子，再对每个素因子应用互反律，大整数分解可能成为计算的瓶颈。Jacobi 符号允许分母为任意正奇数，让交换和取余能够一直进行下去

设 $m=\prod_{i=1}^s p_i^{e_i}$ 是正奇数的素因数分解，定义

$$\boxed{\left(\frac am\right) =\prod_{i=1}^s\left(\frac a{p_i}\right)^{e_i}}$$

右侧每一项都是 Legendre 符号，另约定 $\left(\frac a1\right)=1$。若 $\gcd(a,m)>1$，符号为 $0$；若互素，则符号为 $1$ 或 $-1$。当 $m$ 是奇素数时，两种符号完全一致

值为 $1$ 不一定有平方根

对与 $m$ 互素的 $a$，如果 $a$ 是模 $m$ 的平方，它在每个素因子模数下也是平方，所以 Jacobi 符号必为 $1$。反方向不成立，因为若干个 $-1$ 的乘积也可能是 $1$

例如

$$\left(\frac2{15}\right) =\left(\frac23\right)\left(\frac25\right) =(-1)(-1)=1$$

但 $x^2\equiv2\pmod3$ 已经无解，故 $x^2\equiv2\pmod{15}$ 无解。对于可逆剩余类，Jacobi 符号为 $-1$ 可以排除平方，为 $1$ 则还不能确定

互反律仍然成立

Jacobi 符号对分子、分母都具有乘法性，并且只依赖分子对分母的余数。对互素的正奇数 $a,m$，有

$$\left(\frac am\right)\left(\frac ma\right) =(-1)^{\frac{a-1}{2}\frac{m-1}{2}}$$

两个补充定律也仍然有效：

$$\left(\frac{-1}{m}\right)=(-1)^{(m-1)/2},\qquad \left(\frac2m\right)=(-1)^{(m^2-1)/8}$$

证明时，把 Jacobi 符号展开为 Legendre 符号的乘积，对各素因子应用相应定律，再合并符号即可。例如奇数 $u,v$ 满足

$$\frac{uv-1}{2}\equiv\frac{u-1}{2}+\frac{v-1}{2}\pmod2$$

这保证了互反律中各素因子贡献的指数，可以合并成原来两个整数的指数

因此可以反复执行“取余、提取 $2$ 的因子、交换分子分母”。如果使用负的代表元，需要先提取 $\left(\frac{-1}{m}\right)$；交换时使用正奇数，并在两者都为 $3\pmod4$ 时变号

讲义中的例子是

$$\begin{aligned} \left(\frac{383}{443}\right) &=-\left(\frac{443}{383}\right) =-\left(\frac{60}{383}\right) =-\left(\frac{15}{383}\right)\\ &=\left(\frac{383}{15}\right) =\left(\frac8{15}\right) =\left(\frac2{15}\right)=1 \end{aligned}$$

中间分母 $15$ 对应的是 Jacobi 符号；原分母 $443$ 是素数，所以最终结果仍然证明了 $383$ 是模 $443$ 的二次剩余

一个计算实现

下面的算法通过不断缩小余数计算 Jacobi 符号，不需要知道分母的素因数分解。先取非负余数，也就统一处理了负分子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def jacobi(a, m):
    if m <= 0 or m % 2 == 0:
        raise ValueError("m must be a positive odd integer")

    a %= m
    sign = 1
    while a:
        while a % 2 == 0:
            a //= 2
            if m % 8 in (3, 5):
                sign = -sign

        if a % 4 == 3 and m % 4 == 3:
            sign = -sign
        a, m = m % a, a

    return sign if m == 1 else 0

取余和交换保留最大公因数；在奇分母下去掉分子的 $2$ 的因子也不会改变它。因此终止时若分母不是 $1$，就说明原分子与分母不互素，应返回 $0$

从判定有解到实际求根

下面设 $p$ 是奇素数，且 $\left(\frac ap\right)=1$。判定有解之后，还需要构造平方根。某些素数模数允许直接使用模幂公式

$p\equiv3\pmod4$

这时 $(p+1)/4$ 是整数，取

$$\boxed{r\equiv a^{(p+1)/4}\pmod p}$$

由欧拉判别法，

$$r^2\equiv a^{(p+1)/2} =a\cdot a^{(p-1)/2}\equiv a\pmod p$$

所以全部解就是 $x\equiv\pm r\pmod p$。例如 $p=11,a=5$ 时，$r\equiv5^3\equiv4\pmod{11}$，两个根是 $4$ 和 $7$

$p\equiv5\pmod8$

令

$$r\equiv a^{(p+3)/8}\pmod p,\qquad t\equiv a^{(p-1)/4}\pmod p$$

因为 $t^2\equiv1\pmod p$，所以 $t\equiv\pm1\pmod p$，而

$$r^2\equiv at\pmod p$$

若 $t\equiv1$，$r$ 已经是平方根；若 $t\equiv-1$，则 $r^2\equiv-a$，只需乘上一个 $-1$ 的平方根

由于 $p\equiv5\pmod8$，第二个补充定律给出 $\left(\frac2p\right)=-1$，因此可以取

$$z\equiv2^{(p-1)/4}\pmod p,\qquad z^2\equiv2^{(p-1)/2}\equiv-1\pmod p$$

于是

$$\boxed{ x\equiv \begin{cases} \pm r\pmod p,&t\equiv1\pmod p\\ \pm rz\pmod p,&t\equiv-1\pmod p \end{cases}}$$

例如 $p=13,a=10$ 时，$r\equiv10^2\equiv9$、$t\equiv10^3\equiv-1$，而 $z\equiv2^3\equiv8$，所以 $rz\equiv7\pmod{13}$，两个根是 $7$ 和 $6$

讲义也用 Wilson 定理构造 $-1$ 的平方根：当 $p\equiv1\pmod4$ 时，$\bigl(((p-1)/2)!\bigr)^2\equiv-1\pmod p$。在当前 $p\equiv5\pmod8$ 的情形，上面的模幂构造计算量更小

对于一般奇素数，可以使用 Tonelli–Shanks 等算法。这里的两种公式展示了模数的剩余类如何简化求根过程；若 $a\equiv0\pmod p$，则单独返回唯一的根 $0$

素数幂模数与解的个数

记 $N_{p^\ell}(a)$ 为 $x^2\equiv a\pmod{p^\ell}$ 的不同解类数，以下假设 $p\nmid a$、$\ell\ge1$

奇素数幂：每个根唯一提升

对 $f(X)=X^2-a$，模 $p$ 的根 $r$ 满足 $r\not\equiv0\pmod p$，因此

$$f'(r)=2r\not\equiv0\pmod p$$

由第 5 篇的 Hensel 提升，每个根都能唯一提升到任意模 $p^\ell$ 的根。所以根的个数始终不变：

$$\boxed{N_{p^\ell}(a)=1+\left(\frac ap\right)\qquad(p>2)}$$

也就是说，模 $p$ 无解时，更高次素数幂下仍然无解；模 $p$ 有两个根时，每一层也恰有两个根

$2$ 的幂：需要单独处理

当 $a$ 是奇数时，根也必须为奇数，而任何奇数的平方都满足

$$(2k+1)^2=4k(k+1)+1\equiv1\pmod8$$

完整的计数结果是

不满足相应条件时，根数为 $0$。对最后一行，充分性可以逐层证明：模 $8$ 时已有根；若 $r^2\equiv a\pmod{2^{\ell-1}}$ 且 $\ell\ge4$，写 $a-r^2=2^{\ell-1}c$，则

$$(r+2^{\ell-2}b)^2 \equiv r^2+2^{\ell-1}rb \equiv r^2+2^{\ell-1}b\pmod{2^\ell}$$

选择 $b\equiv c\pmod2$ 就得到模 $2^\ell$ 的根

一旦找到一个根 $r$，全部四个根为

$$\boxed{x\equiv r,-r,r+2^{\ell-1},-r+2^{\ell-1}\pmod{2^\ell}}$$

要说明没有其他根，设 $s$ 也是根，则 $2^\ell\mid(r-s)(r+s)$。由于 $r,s$ 都是奇数，$(r-s)/2$ 与 $(r+s)/2$ 一奇一偶，所以其中一个必须被 $2^{\ell-2}$ 整除。这意味着 $s\equiv\pm r\pmod{2^{\ell-1}}$，恰好给出上面的四个解类。例如 $x^2\equiv1\pmod{16}$ 的解是 $1,7,9,15$

用 CRT 拼回合数模数

若已知 $m=\prod_i p_i^{e_i}$ 的素因数分解，且 $\gcd(a,m)=1$，则 CRT 给出

$$\boxed{N_m(a)=\prod_i N_{p_i^{e_i}}(a)}$$

每选择一组局部平方根，就唯一确定一个模 $m$ 的根。例如 $77=7\cdot11$，求解 $x^2\equiv15\pmod{77}$ 时，局部条件为

$$x\equiv\pm1\pmod7,\qquad x\equiv\pm2\pmod{11}$$

将四种组合分别用 CRT 合并，得到

$$\boxed{x\equiv13,20,57,64\pmod{77}}$$

模平方根与密码学中的困难问题

对已知素数模数，可以用欧拉判别法判断平方性，再用模平方根算法求根。对合数模数，若知道素因数分解，也可以逐个求局部根后用 CRT 合并

当 $n=pq$ 是两个不同奇素数的乘积而分解未知时，需要区分讲义中的两个问题：

• 二次剩余判定问题（QRP）：给定 Jacobi 符号为 $1$ 的 $a$，判断它是否真的是模 $n$ 的平方
• 模平方根问题（SQROOT）：已知 $a$ 是模 $n$ 的二次剩余，求出一个平方根

求平方根与分解 $n$ 的联系，可以直接从平方差看出。若找到 $x,y$ 满足

$$x^2\equiv y^2\pmod n,\qquad x\not\equiv\pm y\pmod n$$

并且 $x,y$ 都与 $n$ 互素，则两个素因子分别落在 $x-y$ 和 $x+y$ 中，从而

$$\gcd(x-y,n),\qquad\gcd(x+y,n)$$

给出非平凡因子。例如上面的 $13$ 和 $20$ 都是 $15$ 的模 $77$ 平方根，且不互为相反数，于是

$$\gcd(20-13,77)=7,\qquad \gcd(20+13,77)=11$$

更一般地，均匀随机选取 $x\in(\mathbb Z/n\mathbb Z)^\times$，把 $a=x^2\bmod n$ 交给一个只接收 $a,n$ 的求根算法，得到根 $y$。给定 $a$ 后，原来的 $x$ 均匀分布在四个平方根中，其中两个不等于 $\pm y$，因此每次有 $1/2$ 的概率分解 $n$。这说明，对这类模数能普遍求平方根，就能通过随机归约完成因数分解