【数论与组合数学 4】平方剩余、二次互反律
平方剩余、二次互反律
一、平方剩余
- 定义:设 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 下的平方非剩余
- 引理:令 \(\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 是偶数。
- 注:在模 p 的剩余系统当中,有一半的数是平方剩余,另一半是平方非剩余。
二、Legendre 符号
- 定义:\(\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}\) 。
- 定理:\(\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}\)
三、高斯引理
- 高斯引理:设 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}\)
- 定理:如果 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}}\)
四、二次互反律
- 定理 (二次互反律):如果 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}\)
- 雅克比符号(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 算法
-
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}\)
- 引理:如果 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}\)
热门相关:骑士归来 别那么骄傲 第一神算:纨绔大小姐 霸皇纪 薄先生,情不由己