平方剩余、二次互反律

一、平方剩余

1. 定义：设 p 为奇素数且 \(\mathsf{a \neq 0\ mod\ p}\) ，如果 a 在模 p 下是另一个数的平方，即 \(\mathsf{a \equiv b^{2}\ mod\ p}\) ，则称 a 为模 p 下的平方剩余，否则称 a 为平方非剩余。而二次同余式 \(\mathsf{x^{2}\equiv a\ mod\ p}\) 可能有 0—2 个解

• 例子：

  \(\mathsf{p=5}\) 时，因为

  \(\mathsf{1^{2}\equiv 1\ mod\ 5 \qquad 2^{2}\equiv 4\ mod\ 5 \qquad 3^{2}\equiv 4\ mod\ 5 \qquad 4^{2}\equiv 1\ mod\ 5}\)

  则 1，4 是模 5 下的平方剩余，而 2，3 是模 5 下的平方非剩余

  \(\mathsf{p=7}\) 时，因为

  \(\mathsf{1^{2}\equiv 1\ mod\ 7 \qquad 2^{2}\equiv 4\ mod\ 7 \qquad 3^{2}\equiv 2\ mod\ 7 \qquad 4^{2}\equiv 2\ mod\ 7 \qquad 5^{2}\equiv 4\ mod\ 7 \qquad 6^{2}\equiv 1\ mod\ 7}\)

  则 1，2，4 为模 7 下的平方剩余，而 3，5，6 是模 7 下的平方非剩余

1. 引理：令 \(\mathsf{a\neq0\ mod\ p}\) ，如果 \(\mathsf{a^{\frac{p-1}{2}}\equiv1\ mod\ p}\) ，则 a 是模 p 下的平方剩余

• 例子：

  15 是模 17 下的平方剩余，因为 \(\mathsf{15^{\frac{17-1}{2}}\equiv 1\ mod\ 17}\)

  12 是模 17 下的平方非剩余，因为 \(\mathsf{12^{\frac{17-1}{2}}\equiv -1\ mod\ 17}\)

• 证明：

  p 是奇数，所以根据欧拉定理：\(\mathsf{a^{p-1}\equiv 1\ mod\ p \qquad (a^{\frac{p-1}{2}})^{2}\equiv 1\ mod\ p \qquad a^{\frac{p-1}{2}}\equiv \pm1\ mod\ p}\)

  设 g 为模 p 下的原根，则 \(\mathsf{\{1,\ g,\ g^{2},\ \cdots,\ g^{p-2}\}=1,\ 2,\ \cdots,\ p-1\ mod\ p}\)

  对应某些 k ，设 \(\mathsf{a \equiv g^{k}\ mod\ p}\) ，所以 \(\mathsf{a \equiv g^{k+(p-1)m}\ mod\ p}\)

  当 k 是偶数时，a 是模 p 下的平方剩余

  如果 \(\mathsf{k=2l}\) ，那么 \(\mathsf{a \equiv g^{2l} \equiv (g^{l})^{2}}\)

  相反，如果\(\mathsf{a \equiv b^{2}\ mod\ p}\) 并且假设 \(\mathsf{b=g^{l}\ mod\ p}\) ，那么 \(\mathsf{a \equiv g^{2l}\ mod\ p}\) ，所以 k 是偶数。

1. 注：在模 p 的剩余系统当中，有一半的数是平方剩余，另一半是平方非剩余。

二、Legendre 符号

1. 定义：\(\mathsf{(\frac{a}{p})= \begin{cases}1 \qquad a\ 是\ mod\ p\ 的平方剩余 \\ -1 \qquad a\ 是\ mod\ p\ 的平方非剩余 \\ 0 \qquad a\ 为\ p\ 等整数倍 \end{cases} \qquad}\)，也可写作 \(\mathsf{(a \mid p)}\) 。满足 \(\mathsf{(\frac{a}{p})=a^{\frac{p-1}{2}}\ mod\ p}\) 。
2. 定理：\(\mathsf{(a \mid p)(b \mid p)=(ab \mid p)}\)

• 证明：

  \(\mathsf{a^{\frac{p-1}{2}}b^{\frac{p-1}{2}}\equiv (ab)^{\frac{p-1}{2}}\ mod\ p \qquad (a^{2} \mid p)=(a \mid p)^{2}=1}\)

• 例子：

  \(\mathsf{(-9 \mid 71)=(-1 \times 3^{2} \mid 71)=(-1 \mid 71)(3^{2} \mid 71)=(-1 \mid 71)=(-1)^{35}\ mod\ 71=-1}\)

  \(\mathsf{(-9 \mid 53)=(-1 \times 3^{2} \mid 53)=(-1 \mid 53)(3^{2} \mid 53)=(-1 \mid 53)=(-1)^{26}\ mod\ 53=1}\)

三、高斯引理

1. 高斯引理：设 p 为奇素数并且 \(\mathsf{a \neq 0\ mod\ p}\) ，对于任意整数 x ，令 \(\mathsf{x_{p}}\) 为模 p 下关于 x 的同余，且具有最小的绝对值。将 x 除以 p ，余数为 b ，则 \(\mathsf{0 \leq b < p}\) 。如果 \(\mathsf{b<\frac{p}{2}}\) ，令 \(\mathsf{x_{p}=b}\) ，如果 \(\mathsf{b> \frac{p}{2}}\) ，令 \(\mathsf{x_{p}=b-p}\) ，则 \(\mathsf{-p/2 < x_{p} < p/2}\) 。令 n 为 \(\mathsf{(a)_{p},\ (2a)_{p},\ (3a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}}\) 中负数的个数，则 \(\mathsf{(a \mid p)=(-1)^{n}}\)

• 例子：

  \(\mathsf{p=13 \qquad a=5 \qquad \{a,\ 2a,\ \cdots,\ (\frac{p-1}{2})a\}=\{5,\ 10,\ 15,\ 20,\ 25,\ 30 \}}\)

  \(\mathsf{\{(a)_{p},\ (2a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}\}=\{5,\ -3,\ 2,\ -6,\ -1,\ 4\}}\)

  其中有 3 个负数，所以 \(\mathsf{(5 \mid 13)=(-1)^{3}=-1}\)

  \(\mathsf{p=13 \qquad a=10 \qquad \{a,\ 2a,\ \cdots,\ (\frac{p-1}{2})a\}=\{10,\ 20,\ 30,\ 40,\ 50,\ 60\}}\)

  \(\mathsf{\{(a)_{p},\ (2a)_{p},\ \cdots,\ ((\frac{p-1}{2})a)_{p}\}=\{-3,\ -6,\ 4,\ 1,\ -2,\ -5\}}\)

  其中有 4 个负数，所以 \(\mathsf{(10 \mid 13)=(-1)^{4}=1}\)

• 证明：

  首先证明：如果 \(\mathsf{1 \leq k \neq l \leq (p-1)/2}\) ，那么 \(\mathsf{(ka)_{p} \neq \pm (la)_{p}}\)

  假设 \(\mathsf{(ka)_{p}= \pm(la)_{p}}\) 不正确，那么有 \(\mathsf{ka \equiv \pm\ la\ mod\ p \Rightarrow (k \pm l)a \equiv 0\ mod\ p \Rightarrow k \pm l \equiv 0\ mod\ p}\)

  这是不可能的，因为 \(\mathsf{2 \leq k+l \leq p-1\ ,\ -p/2 < k-l < p/2\ ,\ k-l \neq 0}\)

  所以在模 p 下数 \(\mathsf{\mid (ka)_{p} \mid\ \qquad k=1,\ 2,\ \cdots,\ \frac{p-1}{2}}\) 全部是不同的 (它们有 \(\mathsf{\frac{p-1}{2}}\) 个) 并且必须是整数 \(\mathsf{\{1,\ 2,\ \cdots,\ \frac{p-1}{2} \}}\) 且按照某种顺序排列。

  \(\mathsf{1 \cdot 2 \cdots(\frac{p-1}{2})\equiv \prod\limits_{k=1}^{\frac{p-1}{2}}\mid (ka)_{p} \mid\ mod\ p}\) ，恰好是 n 个数字 \(\mathsf{(ka)_{p}<0}\) 则 \(\mathsf{\equiv(-1)^{n}\prod\limits_{k=1}^{\frac{p-1}{2}}(ka)_{p}\ mod\ p}\)

  \(\mathsf{\equiv (-1)^{n} \prod\limits_{k=1}^{\frac{p-1}{2}}ka\ mod\ p \equiv a^{\frac{p-1}{2}}(-1)^{n}(1\cdot 2 \cdots (\frac{p-1}{2}))\ mod\ p}\)

  \(\mathsf{\Rightarrow 1 \equiv a^{\frac{p-1}{2}}(-1)^{n}\ mod\ p \quad \Rightarrow \quad a^{\frac{p-1}{2}}\equiv (-1)^{n}\ mod\ p \quad \Rightarrow \quad (a \mid p)\equiv (-1)^{n}\ mod\ p}\)

1. 定理：如果 p 为奇素数且 \(\mathsf{gcd(a,\ p)=1}\) ，如果 a 是奇数，\(\mathsf{(a \mid p)=(-1)^{t}}\) 且 \(\mathsf{t=\sum\limits_{j=1}^{\frac{p-1}{2}} \lfloor \frac{ja}{p} \rfloor}\) 且 \(\mathsf{(a \mid p)=(-1)^{\frac{(p^{2}-1)}{8}}}\)

• 证明：

  使用高斯引理，主要关注 \(\mathsf{(-1)^{n}}\) 或 \(\mathsf{n\ mod\ 2}\) 的情况。

  对于 1 到 \(\mathsf{\frac{p-1}{2}}\) 之间的每个数 k ，\(\mathsf{ka=p\lfloor \frac{ka}{p} \rfloor +ka\ mod\ p}\)

  \(\mathsf{ka=p \lfloor \frac{ka}{p} \rfloor +(ka)_{p}+ \begin{cases}0 \qquad 如果 (ka)_{p}>0 \\p \qquad 如果 (ka)_{p}<0 \end{cases}}\)

  \(\mathsf{ka= \lfloor \frac{ka}{p} \rfloor + \mid (ka)_{p} \mid + \begin{cases}0 \qquad 如果 (ka)_{p}>0 \\1 \qquad 如果 (ka)_{p}<0 \end{cases}\ mod\ 2}\)

  \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}ka \equiv \sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor+\sum\limits_{k=1}^{\frac{p-1}{2}}\mid(ka)_{p}\mid+n\ (mod\ 2)}\)

  \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}ka=a\sum\limits_{k=1}^{\frac{p-1}{2}}k=\frac{a}{2}(\frac{p-1}{2})(\frac{p-1}{2}+1)=\frac{a(p^{2}-1)}{8}}\)

  由于 \(\mathsf{\{\mid a\mid_{p},\ \cdots,\ \mid \frac{p-1}{2} a \mid _{p}\}}\) 是 \(\mathsf{\{1,\ \cdots,\ \frac{p-1}{2} \}}\)

  \(\mathsf{\sum\limits_{k=1}^{\frac{p-1}{2}}\mid (ka)_{p} \mid = \sum\limits_{k=1}^{\frac{p-1}{2}}k=\frac{1}{2}(\frac{p-1}{2})(\frac{p-1}{2}+1)=\frac{(p^{2}-1)}{8}}\)

  所以，\(\mathsf{n\equiv \frac{a(p^{2}-1)}{8}-\frac{p^{2}-1}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor\ (mod\ 2)}\)

  \(\mathsf{n\equiv \frac{(a-1)(p^{2}-1)}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}}\lfloor \frac{ka}{p} \rfloor\ mod\ 2}\)

  \(\mathsf{n\equiv \sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{ka}{p} \rfloor \equiv t\ mod\ 2}\)

  由于 a 是奇数，所以 \(\mathsf{(a\mid p)=(-1)^{t}}\)

  如果 \(\mathsf{a=2}\) ，\(\mathsf{n\equiv \frac{(p^{2}-1)}{8}+\sum\limits_{k=1}^{\frac{p-1}{2}} \lfloor \frac{2k}{p} \rfloor\ mod\ 2 \qquad k \in \{1,\ 2,\ \cdots,\ \frac{p-1}{2}\}}\)

  所以 \(\mathsf{\lfloor \frac{2k}{p} \rfloor=0}\) ，则 \(\mathsf{n \equiv \frac{(p^{2}-1)}{8}\ mod\ 2}\) ，也就是说：

  \(\mathsf{(2 \mid p)=(-1)^{(p^{2}-1)/8}=\begin{cases}1 \qquad 如果\ p=1,7\ mod\ 8 \\-1 \qquad 如果\ p=3,5\ mod\ 8 \end{cases}}\)

  \(\mathsf{(-1 \mid p)=(-1)^{\frac{p-1}{2}}= \begin{cases}1 \qquad 如果\ p=1\ mod\ 4 \\-1 \qquad 如果\ p=3\ mod\ 4 \end{cases}}\)

四、二次互反律

1. 定理 (二次互反律)：如果 p，q 是不同的奇素数，那么 \(\mathsf{(\frac{p}{q})(\frac{q}{p})=(-1)^{(\frac{p-1}{2})(\frac{q-1}{2})}}\) ，或其他版本：\(\mathsf{(\frac{p}{q})=\begin{cases}+(\frac{q}{p}) \qquad 如果\ p\equiv 1\ mod\ 4\ 或者\ q \equiv 1\ mod\ 4 \\-(\frac{q}{p}) \qquad 如果\ p\equiv q \equiv 3\ mod\ 4 \end{cases}}\)

• 例子：

  \(\mathsf{(\frac{37}{73}) \leftarrow (\frac{73}{37}) \leftarrow (\frac{-1}{37})}\)

  \(\mathsf{(7 \mid 11)=-(11 \mid 7)=-(4 \mid 7)=-1}\)

  \(\mathsf{(10 \mid 13)=(2 \mid 13)(5 \mid 13)=(-1)(13 \mid 5)=-(3 \mid 5)=-(5 \mid 3)=-(2 \mid 3)=-(-1)=1}\)

  \(\mathsf{p=11,\ x=\pm 1,\ \pm2,\ \pm3,\ \pm4,\ \pm5,\ \Rightarrow x^{2}=1,\ 3,\ 4,\ 5,\ 9}\)

  \(\mathsf{p=13,\ x=\pm1,\ \pm2,\ \pm3,\ \pm4,\ \pm,5\ \pm6 \Rightarrow x^{2}=1,\ 3,\ 4,\ 9,\ 10,\ 12}\)

1. 雅克比符号(n 不一定只是奇素数)：对于任意整数 a 和任意正奇数 n ，雅克比符号被定义为对应于 n 的素因子的 Legendre 符号的乘积。即：\(\mathsf{(\frac{a}{n})=(\frac{a}{p_{1}})^{\alpha_{1}}(\frac{a}{p_{2}})^{\alpha_{2}}\cdots(\frac{a}{p_{k}})^{\alpha_{k}}}\) ，其中 \(\mathsf{n=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\cdots p_{k}^{\alpha_{k}}}\)

• 注意：

  如果 \(\mathsf{(\frac{a}{n})=-1}\) 那么 a 是模 n 下的平方剩余。如果 a 是模 n 下的平方剩余并且 \(\mathsf{gcd(a,\ n)=1}\)，则 \(\mathsf{(\frac{a}{n})=1}\)

  但是，不同于 Legendre 符号：如果 \(\mathsf{(\frac{a}{n})=1}\) 那么 a 可能是也可能不是模 n 下的平方剩余。如：\(\mathsf{(\frac{-1}{77})=1}\) ，但是 -1 是平方非剩余

• 例子：

  \(\mathsf{(\frac{1001}{9907})=(\frac{7}{9907})(\frac{11}{9907})(\frac{13}{9907})}\)

  \(\mathsf{ (\frac{7}{9907})=-(\frac{9907}{11})=-(\frac{2}{7})=-1 \qquad (\frac{11}{9907})=-(\frac{9907}{11})=-(\frac{7}{11})=(\frac{11}{7})=(\frac{4}{7})=1 \qquad (\frac{13}{9907})=(\frac{9907}{13})=(\frac{1}{3})=1}\)

  \(\mathsf{(\frac{1001}{9907})=(\frac{9907}{1001})=(\frac{898}{1001})=(\frac{2}{1001})(\frac{449}{1001})=(\frac{449}{1001})=(\frac{1001}{449})=(\frac{103}{449})=(\frac{449}{103})=(\frac{37}{103})=(\frac{103}{37})=(\frac{29}{37})=(\frac{37}{29})=(\frac{8}{29})=(\frac{2}{29})^{3}=-1}\)

五、Tonelli-Shanks 算法

1. Tonelli-Shanks 算法用于求解形如：\(\mathsf{x^{2} \equiv n\ mod\ p}\) 的二次同余方程。

   输入：p ，一个奇素数。n 是一个整数，其中 n 是模 p 下的平方剩余。意味着 Legendre 符号\(\mathsf{(n/p)=1}\)

   输出：R ，一个整数满足\(\mathsf{R^{2} \equiv n}\)

   (1) 从 p-1 开始，对 p-1 进行因式分解，分解为\(\mathsf{p-1=Q2^{S}}\) ，其中 Q 为奇数。如果 \(\mathsf{S=1\ (p \equiv 3\ mod\ 4)}\) ，则由 \(\mathsf{R \equiv \pm n^{\frac{p+1}{4}}}\) 直接给出解。

   (2) 选择一个 Z 为模 p 下的平方非剩余，令\(\mathsf{c \equiv z^{Q}}\)

   (3) 令\(\mathsf{R \equiv n^{\frac{Q+1}{2}}，t \equiv n^{Q}，M=S}\)

   (4) 循环：

   <1> 如果\(\mathsf{t \equiv 1}\) ，返回 R

   <2> 否则，找一个最小的 i ，\(\mathsf{0<i<M}\) ，使得 \(\mathsf{t^{2^{i}} \equiv 1}\) (重复平方)

   <3> 令\(\mathsf{b\equiv c^{2^{(M-i-1)}}}\) 并且令 \(\mathsf{R \equiv Rb,\ t \equiv tb^{2},\ c \equiv b^{2}}\) 且 \(\mathsf{M=i}\) (mod p 条件下)

   如果 R 是一个解，那么第二个解就是\(\mathsf{p-R}\)

• 证明：

  已知 \(\mathsf{p-1=Q2^{S} \qquad r \equiv n^{\frac{Q+1}{2}}\ mod\ p \qquad t \equiv n^{Q}\ mod\ p}\)

  所以 \(\mathsf{r^{2}\equiv nt\ mod\ p}\) 对于每次迭代都为真

  如果 \(\mathsf{t \equiv 1\ mod\ p}\) ，那么 \(\mathsf{r^{2} \equiv n\ mod\ p}\) 并且该算法以 \(\mathsf{R \equiv \pm r\ mod\ p}\) 结束

  如果 \(\mathsf{t \neq 1\ mod\ p}\) ，那么认为 z 为模 p 下的平方非剩余

  令 \(\mathsf{c \equiv z^{Q}\ mod\ p}\) ，那么 \(\mathsf{c^{2^{S}} \equiv (z^{Q})^{2^{S}} \equiv z^{2^{S}Q} \equiv z^{p-1} \equiv 1\ mod\ p}\) 并且 \(\mathsf{c^{2^{S-1}} \equiv z^{\frac{p-1}{2}} \equiv -1\ mod\ p}\) 这表明 c 的阶数是 \(\mathsf{2^{S}}\)

  同理，有 \(\mathsf{t^{2^{S}} \equiv 1\ mod\ p}\) ，所以 t 的阶数整除 \(\mathsf{2^{S}}\)

  假设 t 的阶数是 \(\mathsf{2^{S^{'}}}\) 。由于 n 是模 p 的平方，\(\mathsf{t \equiv n^{Q}\ mod\ p}\) 也是一个平方，因此 \(\mathsf{S^{'} \leq S-1}\)

  之后令 \(\mathsf{b \equiv c^{2^{S-S^{'}-1}}\ mod\ p \qquad r^{'} \equiv br\ mod\ p \qquad c^{'} \equiv b^{2}\ mod\ p \qquad t^{'} \equiv c^{'}t\ mod\ p}\) 则和上述一致，\(\mathsf{(r^{'})^{2} \equiv nt^{'}\ mod\ p}\) 成立

  然而 t 和 \(\mathsf{c^{'}}\) 的阶都是 \(\mathsf{2^{s^{'}}}\) 。这表明 \(\mathsf{t^{'}}\) 的阶数为 \(\mathsf{2^{S^{''}}}\)满足 \(\mathsf{S^{''}<S{'}}\)

  如果 \(\mathsf{S^{''}=0}\) 那么 \(\mathsf{t^{'} \equiv 1\ mod\ p}\) 并且该算法在 \(\mathsf{R \equiv \pm r^{'}\ mod\ p}\) 终止

  否则，用 \(\mathsf{b^{'},\ r^{''},\ c^{''},\ t^{''}}\) 相似的定义重新开始循环直到 \(\mathsf{S^{' \cdots '}}\) 等于 0

  因此，一系列的 S 是属于严格逐渐减少的算法，一定会终止

• 例子：

  求解二次同余方程 \(\mathsf{x^{2} \equiv 10\ mod\ 13}\) ，明显 13 是奇素数。由于 \(\mathsf{10^{\frac{13-1}{2}}=10^{6}\equiv 1\ mod\ 13}\) ，10 是平方剩余

  (1) 已知 \(\mathsf{p-1=12=3 \cdot 2^{2}}\) ，令 \(\mathsf{Q=3,\ S=2}\)

  (2) 令 \(\mathsf{Z=2}\) 为平方剩余，因为 \(\mathsf{2^{\frac{13-1}{2}}=-1\ mod\ 13}\) ，令 \(\mathsf{c=2^{3} \equiv 8\ mod\ 13}\)

  (3)\(\mathsf{R=10^{2} \equiv -4\ ,\ t \equiv 10^{3} \equiv-1\ mod\ 13 \qquad M=2}\)

  (4) 开始循环：\(\mathsf{t \neq 1\ mod\ 13}\) ，所以 \(\mathsf{0<i<2}\) ，则 \(\mathsf{i=1}\) 。

  令 \(\mathsf{b \equiv 8^{2^{2-1-1}}\equiv 8\ mod\ 13 \qquad c=b^{2}\equiv 8^{2} \equiv -1\ mod\ 13}\)

  \(\mathsf{R=Rb=-4 \cdot 8 \equiv 7\ mod\ 13 \qquad t=tb^{2} \equiv -1 \cdot -1 \equiv 1\ mod\ 13 \qquad M=i=1}\)

  返回开始，因为 \(\mathsf{t \equiv 1\ mod\ 13}\) 。返回 \(\mathsf{R \equiv 7\ mod\ 13}\)

  验证：\(\mathsf{7^{2}=49 \equiv 10\ mod\ 13}\) 且 \(\mathsf{(-7)^{2} \equiv 6^{2} \equiv 10\ mod\ 13}\)

1. 引理：如果 a，b 都与 p 互素，且 a，b 的阶都为 \(\mathsf{2^{j}\ mod\ p\ (j>0)}\) ，则对于某些 \(\mathsf{k<j}\) 时 ab 的阶表示为 \(\mathsf{2^{k}}\)

• 证明：

  a 的阶数为 \(\mathsf{2^{j}\ mod\ p}\) ，则 \(\mathsf{a^{2^{j-1}} \equiv -1\ mod\ p}\) 。同理 \(\mathsf{b^{2^{j-1}} \equiv -1\ mod\ p}\)

  所以，\(\mathsf{(ab)^{2^{j-1}} \equiv 1\ mod\ p}\) ，也就是说 ab 的阶数整除 \(\mathsf{2^{j-1}}\) ，因此，\(\mathsf{k<j}\)