数论（二）

5.二次剩余

5.1 二次剩余(Quadratic residue)和二次非剩余定义

设整数 $n > 1, a < n$ ,如果存在 $x \in z_{n}$ ,满足 $x^{2} \equiv a (\mod n)$ ,那么称 $a$ 是模 $n$ 的二次剩余,否则 $a$ 就称为模 $n$ 的二次非剩余，用 $Q R_{n}$ 表示模 $n$ 的二次剩余集合，用 $Q N R_{n}$ 表示模 $n$ 的二次非剩余集合

5.2 举例

\begin{aligned} Q R_{11} & = {0^{2}, 1^{2}, 2^{2}, 3^{2}, 4^{2}, 5^{2}, 6^{2}, 7^{2}, 8^{2}, 9^{2}, 10^{2}, 11^{2}, \dots} (\mod 11) = {0, 1, 3, 4, 5, 9} \\ Q N R_{11} & = {2, 6, 7, 8, 10} \end{aligned}

5.3 定理：欧拉准则

针对质数 $p$ 的二次剩余判定，对于质数 $p$ ,任意 $x \in Z_{p}^{*}$ ， $x \in Q R_{p}$ 的充分必要条件为

x^{(p - 1) / 2} \equiv 1 (\mod p)

$x \in Q N R_{p}$ 的充分必要条件为

x^{(p - 1) / 2} \equiv - 1 (\mod p)

5.4 定理

针对合数 $n$ 的二次剩余判定， $n = {p_{1}}^{a_{1}} \times {p_{1}}^{a_{1}} \times \dots \times {p_{k}}^{a_{k}}$ ，那么 $x \in Q R_{n}$ 的充分必要条件为：

x (\mod {p_{i}}^{a_{i}}) \in Q R_{{p_{i}}^{a_{i}}}

5.5 举例

\begin{aligned} n & = 5 \times 7 \\ Q R_{5} & = {0, 1, 4} \\ Q N R_{5} & = {2, 3} \\ Q R_{7} & = {0, 1, 2, 4} \\ Q N R_{7} & = {3, 5, 6} \\ Q R_{35} & = {0, 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30} \end{aligned}

5.6 定理

对于质数 $p$ , $Z_{p}^{*}$ 中有 $(p - 1) / 2$ 个元素是模 $p$ 的二次剩余，另外 $(p - 1) / 2$ 个元素是模 $p$ 的二次非剩余

5.7 举例

Z_{11}^{*} = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} {1, 3, 4, 5, 9} \in Q R_{11} {2, 6, 7, 8, 10} \in Q N R_{11}

5.8 定理

对于两个质数的乘积 $n = q p$ ，那么 $Z_{n}$ 里恰好有1/4的数，也就是 $(p - 1) (q - 1) / 4$ 个是二次剩余，一般来说，如果合数n有k个质数因子，那么 $Z_{n}^{*}$ 中的元素中有 $1 / 2^{k}$ 是二次剩余

5.9 举例

Z_{15}^{*} = {1, 2, 4, 7, 8, 11, 13, 14} {1, 4} \in Q R_{15} {2, 7, 8, 11, 13, 14} \in Q N R_{15}

6. 勒让德-雅可比符号

6.1 定义

对于任意质数 $p > 2$ ，和任意 $a$ ，定义勒让德符号(Legendre_symbol)为 $L (a, p)$

L (a, p) = {\begin{cases} 1 & if a \in Q R_{p} and a ≢ 0 (\mod p) \\ - 1 & if a \in Q N R_{p} and a ≢ 0 (\mod p) \\ 0 & if a \equiv 0 (\mod p) \end{cases}

6.2 定理

勒让德符号计算方法

L (a, p) = a^{(p - 1) / 2} (\mod p), and L (a, p) =\in {- 1, 0, 1}

6.4 简写

勒让德符号和雅可比符号也可统一简写为 $(\frac{a}{p})$ ,或者 $(a | p)$

7. 模质数的二次平方根

7.1 定理

对于质数 $p > 2$ ，如果 $a \in Q R_{p}, a \neq 0$ ，那么方程

x^{2} \equiv a (\mod p)

在有两个解，也就是说a有两个平方根，其中一个在区间 $[1, (p - 1) / 2]$ ，另一个在区间 $[(p + 1) / 2, p - 1]$ ，而且，其中一个平方根也属于模 $p$ 的二次剩余，称为主平方根(pricipal square root)

7.2 举例

对于方程

x^{2} \equiv 9 (\mod 11)

有两个解 $x_{1} = 3, x_{2} = 8$ , 其中

3 \in [1, 5], 8 \in [6, 10], 3 \in Q R_{11}

对于方程 $x^{2} \equiv a (\mod p), a \in Q R_{p}$ 如果 $p \equiv 3, 7 (\mod 8)$ , $x \equiv \pm a^{(p + 1) / 2} (\mod p)$ 如果 $p \equiv 5 (\mod 8)$ , $x \equiv \pm a^{(p + 3) / 8} (\mod p)$ 如果 $p \equiv 3 (\mod 4)$ , $x \equiv \pm a^{(p + 1) / 4} (\mod p)$

7.3.2

对于一般情况的质数 $p$ ,使用Tonelli–Shanks算法求解

8. 模合数的二次平方根

参考: https://www.johndcook.com/blog/quadratic_congruences/

8.1 算法模2的幂

对于方程 $x^{2} \equiv a (\mod 2)$ ，有解 $x \equiv 1 (\mod 2)$ 方程 $x^{2} \equiv a (\mod 2^{2})$ ，当 $a \equiv 1 (\mod 4)$ 时有2个解， $x \equiv \pm 1 (\mod 4)$ 方程 $x^{2} \equiv a (\mod 2^{n}), n \geq 3, gcd (a, 2) = 1$ , 当 $a \equiv 1 (\mod 8)$ 时有4个解，

8.2 算法模质数的幂

求解方程 $x^{2} \equiv a (\mod p^{k}), k > 0, gcd (a, p) = 1$ , 方程有解的充分必要条件是 $(\frac{a}{p}) = 1$ , 也就是a是模p的二次剩余方程有两个解，使用Hensel's lemma算法设 $x_{k}$ 是 $x^{2} \equiv a (\mod p^{k})$ 的解，有 $y_{k}$ 存在使得等式 $2 x_{k} y_{k} \equiv 1 (\mod p^{k})$ 成立，那么 $x_{k + 1} = x_{k} - (x_{k}^{2} - a) y_{k}$ 是方程 $x^{2} \equiv a (\mod p^{k + 1})$ 的解

8.3 举例

求解方程

x^{2} \equiv 23 (\mod 343)

其中 $343 = 7^{3}$ ，首先解方程

x_{1}^{2} \equiv 23 \equiv 2 (\mod 7), x_{1} = \pm 3

以 $x_{1} = 3$ 为例，使用扩展欧几里得算法求解

2 \times 3 \times y_{1} \equiv 1 (\mod 7), y_{1} = 6 x_{2} = (x_{1} - (x_{1}^{2} - a) y_{1}) (\mod 49) = 38

同理，求方程

2 \times 38 \times y_{2} \equiv 1 (\mod 49), y_{2} = 20 x_{3} = (38 - (38^{2} - 23) \times 20) (\mod 343) = 87

所以，最终方程的两个解是 $\pm 87 (87, 256)$

8.4 算法

对于合数 $n = p_{1} p_{2} \dots p_{k}$ ，整数 $a \in Q R_{n}$ , 求解方程 $x^{2} \equiv a (\mod n)$ 首先求解模质数方程

x_{p_{1}}^{2} \equiv a (\mod p_{1}) x_{p_{1}}^{2} \equiv a (\mod p_{1}) \dots x_{p_{k}}^{2} \equiv a (\mod p_{k})

然后根据中国剩余定理，解方程组

{\begin{cases} x \equiv x_{p_{1}} (\mod p_{1}) \\ x \equiv x_{p_{2}} (\mod p_{2}) \\ \dots \\ x \equiv x_{p_{k}} (\mod p_{k}) \end{cases}

得到 $x$ ，由于每个 $x_{p_{i}}$ 有两个解，所以最终 $x$ 有 $2^{k}$ 个解

8.5 举例

x^{2} \equiv 15 (\mod 77), p = 7, q = 11

按照模为质数的方法解方程

{\begin{cases} x_{p}^{2} \equiv 15 \equiv 1 (\mod 7) & x_{p} = \pm 1 (1, 6) \\ x_{q}^{2} \equiv 15 \equiv 4 (\mod 11) & x_{q} = \pm 9 (2, 9) \end{cases}

按照中国剩余定理，解以下四个方程组

{\begin{cases} x \equiv 1 (\mod 7) \\ x \equiv 2 (\mod 11) \end{cases} {\begin{cases} x \equiv 1 (\mod 7) \\ x \equiv 9 (\mod 11) \end{cases} {\begin{cases} x \equiv 6 (\mod 7) \\ x \equiv 2 (\mod 11) \end{cases} {\begin{cases} x \equiv 6 (\mod 7) \\ x \equiv 9 (\mod 11) \end{cases}

得到四个解 $x = 57, 64, 13, 20$

8.6 定理

如果不知道 $n$ 的素因子，那么就模 $n$ 的平方根是非常困难的问题