【信息安全数学基础】二次剩余（Quadratic residue）

什么是二次剩余呢？

小小定义

设 m 是大于 1 的整数，a 是与 m 互素的整数，若
x 2 ≡ a ( m o d m ) x^{2} \equiv a \pmod{m} x2≡a(modm)有解，则 a 叫作模 m 的二次剩余，或平方剩余。否则，a 叫作模 m 的二次非剩余，或平方非剩余。（这是贾春福老师的《信息安全数学基础》这本书里给出的定义，个人觉得不是特别准确，a 与 m 不一定要互素。）

简单说就是给定一个整数 a 和一个正整数 m，如果存在一个整数 x 使 x 2 ≡ a ( m o d m ) x^{2} \equiv a \pmod{m} x2≡a(modm) 成立，就可以说 a 是模 m 的二次剩余（x 叫 a 在模 m 下的平方根）。

小试牛刀

求模7的二次剩余和二次非剩余。

0 2 ≡ 0 ( m o d 7 ) 0^{2} \equiv 0 \pmod{7} 02≡0(mod7)
1 2 ≡ 1 ( m o d 7 ) 1^{2} \equiv 1 \pmod{7} 12≡1(mod7)
2 2 ≡ 4 ( m o d 7 ) 2^{2} \equiv 4 \pmod{7} 22≡4(mod7)
3 2 ≡ 2 ( m o d 7 ) 3^{2} \equiv 2 \pmod{7} 32≡2(mod7)
4 2 ≡ 2 ( m o d 7 ) 4^{2} \equiv 2 \pmod{7} 42≡2(mod7)
5 2 ≡ 4 ( m o d 7 ) 5^{2} \equiv 4 \pmod{7} 52≡4(mod7)
6 2 ≡ 1 ( m o d 7 ) 6^{2} \equiv 1 \pmod{7} 62≡1(mod7)

1，2，4是模7下的二次剩余，3，5，6是模7下的二次非剩余。（0？不管，lol， a ∈ Z n ∗ a\in Z_{n}^{\ast } a∈Zn∗​）

多算几个试试？
模13的二次剩余1，3，4，9，10，12，二次非剩余2，5，6，7，8，11
模17的二次剩余1，2，4，8，9，13，15，16，二次非剩余3，5，6，7，10，11，12，14
模19的二次剩余1，4，5，6，7，9，11，16，17，二次非剩余2，3，8，10，12，13，14，15，18
（模奇素数的二次剩余和二次非剩余个数相等（各占一半）？后面细说。lol）

当m较小时，我们还可以遍历1，2，3，……，m-1，逐一平方取模计算找模m的二次剩余，但当m较大时，我们可以怎么快速判断整数 a 是不是模m的二次剩余呢？

二次剩余判断

模m下，什么样的整数a才是二次剩余（有平方根）呢？
定义二次剩余的集合： ( Z m ∗ ) 2 \left ( Z_{m}^{\ast } \right ) ^{2} (Zm∗​)2
( Z m ∗ ) 2 = { b 2 ∣ b ∈ Z m ∗ } \left ( Z_{m}^{\ast } \right ) ^{2} = \left \{ b^{2}\mid b\in Z_{m}^{\ast } \right \} (Zm∗​)2={b2∣b∈Zm∗​}若 a ∈ ( Z m ∗ ) 2 a\in \left ( Z_{m}^{\ast } \right ) ^{2} a∈(Zm∗​)2，则存在 b ∈ Z m ∗ b\in Z_{m}^{\ast } b∈Zm∗​， 使得 b 2 ≡ a ( m o d m ) b^{2} \equiv a \pmod{m} b2≡a(modm)
a 是模 m 下的二次剩余 ⟺ a ∈ ( Z m ∗ ) 2 a 是模 m 下的二次剩余\Longleftrightarrow a\in \left ( Z_{m}^{\ast } \right ) ^{2} a是模m下的二次剩余⟺a∈(Zm∗​)2

欧拉判别条件（欧拉准则（Euler’s criterion））：设 p 是奇素数， gcd ⁡ ( a , p ) = 1 \gcd(a, p) =1 gcd(a,p)=1，则
（1）a 是模 p 的二次剩余的充要条件是 a p − 1 2 ≡ 1 ( m o d p ) a^{\frac{p-1}{2} } \equiv 1 \pmod{p} a2p−1​≡1(modp)（2）a 是模 p 的二次非剩余的充要条件是 a p − 1 2 ≡ − 1 ( m o d p ) a^{\frac{p-1}{2} } \equiv -1 \pmod{p} a2p−1​≡−1(modp)
当 a 是模 p 的二次剩余时， x 2 ≡ a ( m o d p ) x^{2} \equiv a \pmod{p} x2≡a(modp)恰好有两解。

证明
（1）先证必要性，若 a 是模 p 的二次剩余，则有整数 x 满足 x 2 ≡ a ( m o d p ) x^{2} \equiv a \pmod{p} x2≡a(modp)因为 gcd ⁡ ( a , p ) = 1 \gcd(a, p)=1 gcd(a,p)=1，所以 gcd ⁡ ( x , p ) = 1 \gcd(x, p)=1 gcd(x,p)=1(想想为什么?)，由欧拉定理，可知 a p − 1 2 ≡ ( x 2 ) p − 1 2 ≡ x p − 1 ≡ 1 ( m o d m ) a^{\frac{p-1}{2} } \equiv \left ( x^{2} \right ) ^{\frac{p-1}{2} } \equiv x^{p-1} \equiv 1 \pmod{m} a2p−1​≡(x2)2p−1​≡xp−1≡1(modm)（欧拉定理：设 m 是一个大于1的整数，若 a 是满足(a,m)=1的整数，则 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi \left ( m \right ) } \equiv 1 \pmod{m} aφ(m)≡1(modm)，下次再证）

再证充分性，用反证法，假设满足 a p − 1 2 ≡ 1 ( m o d p ) a^{\frac{p-1}{2} } \equiv 1 \pmod{p} a2p−1​≡1(modp)即a不是模p的二次剩余。考虑线性同余方程 s x ≡ a ( m o d p ) sx \equiv a \pmod{p} sx≡a(modp) ，当 s 从 p 的最小正缩系（什么是最小正缩系呢？）中取值时，方程 s x ≡ a ( m o d p ) sx \equiv a \pmod{p} sx≡a(modp) 必有唯一解（想想为什么？）。亦即 s 取 p 的最小正缩系中的每一个元素 i，必有唯一的 x = x i x_{i} xi​属于p的最小正缩系，使得 s x ≡ a ( m o d p ) sx \equiv a \pmod{p} sx≡a(modp) 成立；若 a 不是 p 的二次剩余，则 i ≠ x i x_{i} xi​，这样 p 的最小正缩系中的 p-1 个数可以按<i, x i x_{i} xi​>两两配对相乘，得到
( p − 1 ) ! ≡ a p − 1 2 ( m o d p ) (p-1)! \equiv a^{\frac{p-1}{2} } \pmod{p} (p−1)!≡a2p−1​(modp)由威尔逊定理（这个也下次再说） ( p − 1 ) ! ≡ − 1 ( m o d p ) (p-1)! \equiv -1 \pmod{p} (p−1)!≡−1(modp)，所以有
a p − 1 2 ≡ − 1 ( m o d p ) a^{\frac{p-1}{2} } \equiv -1 \pmod{p} a2p−1​≡−1(modp)这与条件 a p − 1 2 ≡ 1 ( m o d p ) a^{\frac{p-1}{2} } \equiv 1 \pmod{p} a2p−1​≡1(modp)矛盾。所以肯定存在一个 i，使得 i = x i i=x_{i} i=xi​，即 a 是模 p 的二次剩余。

（2）由于 a 与 p 互素，由欧拉定理有 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1 \pmod{p} ap−1≡1(modp)即 p | (a^p-1-1)，有
p ∣ ( a p − 1 2 − 1 ) 或 p ∣ ( a p − 1 2 + 1 ) p\mid (a^{\frac{p-1}{2} }-1) 或 p\mid (a^{\frac{p-1}{2} }+1) p∣(a2p−1​−1)或p∣(a2p−1​+1)
根据（1）的证明，a 是模 p 的二次非剩余的充要条件是 p ∣ ( a p − 1 2 + 1 ) p\mid (a^{\frac{p-1}{2} }+1) p∣(a2p−1​+1)即 a p − 1 2 ≡ − 1 ( m o d p ) a^{\frac{p-1}{2} } \equiv -1 \pmod{p} a2p−1​≡−1(modp)定理得证。

定理：设p是奇素数，则模p的缩系中二次剩余与二次非剩余的个数各为 p − 1 2 \frac{p-1}{2} 2p−1​，且 p − 1 2 \frac{p-1}{2} 2p−1​个二次剩余分别与序列 1 2 ， 2 2 ， … ， ( p − 1 2 ) 2 1^{2} ，2^{2}，\dots ，(\frac{p-1}{2})^{2} 12，22，…，(2p−1​)2中的一个数模p同余，且仅与一个数模p同余。（证明 … \dots …）

结

下次一定！