数论（三）

9. Blum整数 Blum Integer

9.1 定义

如果有质数 $p, q$ ，满足 $p \equiv 3 (\mod 4), q \equiv 3 (\mod 4)$ ,那么 $n = p q$ 称为Blum整数
比如 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, 253, 301, 309, 321, 329, 341, 381, 393, 413, 417, 437, 453, 469, 473, 489, 497, ...

9.2 历史

以数学家Manuel Blum命名

9.3 特性

设 $n$ 是Blum整数

9.3.1

由于 $p = 4 k + 3, \frac{p - 1}{2} = 2 k + 1$ , 所以 $L (- 1, p) = (- 1)^{\frac{p - 1}{2}} = (- 1)^{2 k + 1} = - 1$
所以

J (- 1, n) = L (- 1, p) \times L (- 1, q) = 1

推论： $J (a, n) = J (- a, n)$
举例：

\begin{aligned} J (1, 21) & = J (20, 21) = 1 \\ J (2, 21) & = J (19, 21) = - 1 \\ J (4, 21) & = J (17, 21) = 1 \\ \dots \\ J (10, 21) & = J (11, 21) = - 1 \end{aligned}

9.3.2

对于任意 $y \in Z_{n}^{*}$ ，如果 $L (y, n) = 1$ ，那么 $y$ 和 $- y$ 有一个属于 $Q R_{n}$ ，有一个属于 $Q N R_{n}$
举例：
满足 $J (y, 21) = 1$ 的数有 ${\pm 1, \pm 4, \pm 5}$ ，其中 ${1, 4, - 5 (16)}$ 属于 $Q R_{21}$ , ${- 1 (20), - 4 (17), 5}$ 属于 $Q N R_{21}$

9.3.3

对于任意 $y \in Q R_{n}$ ，方程 $x^{2} \equiv y (\mod n)$ 有四个根 $\pm u, \pm v$ ，这四个根满足以下组合

{\begin{cases} L (u, p) = 1 \\ L (u, q) = 1 \end{cases} {\begin{cases} L (- u, p) = - 1 \\ L (- u, q) = - 1 \end{cases} {\begin{cases} L (v, p) = - 1 \\ L (v, q) = 1 \end{cases} {\begin{cases} L (- v, p) = 1 \\ L (- v, q) = - 1 \end{cases}

其中有且仅有一个解 $u \in Q R_{n}$ ，
举例：
方程 $x^{2} \equiv 4 (\mod 21)$ 有四个解 $\pm 2 (2, 19), \pm 5 (5, 16)$ ,

{\begin{cases} L (16, 3) = 1 \\ L (16, 7) = 1 \end{cases} {\begin{cases} L (5, 3) = - 1 \\ L (5, 7) = - 1 \end{cases} {\begin{cases} L (2, 3) = - 1 \\ L (2, 7) = 1 \end{cases} {\begin{cases} L (19, 3) = 1 \\ L (19, 7) = - 1 \end{cases}

9.3.4

函数 $f (x) = x^{2} (\mod n)$ 是集合 $Q R_{n}$ 的一个置换，也就是说，对于任意 $x \in Q R_{n}, f (x) \in Q R_{n}$ ，且 $f (x)$ 和 $x$ 一一对应
举例57=3x19：

$x \in Q R_{57}$	1	4	7	16	25	28	43	49	55
$x^{2} \mod 57$	1	16	49	28	55	43	25	7	4

9.3.5

对于任意 $y \in Q R_{n}$ ，方程 $x^{2} \equiv y (\mod n)$ 有四个根 $\pm u, \pm v$ ，其中一对解 $\pm u$ ,也就是 $u, n - u$ , 一定有一个是奇数，另一个是偶数，一个是在 $[1, (n - 1) / 2]$ 区间，另一个在 $[(n + 1) / 2, n - 1]$ 区间
比如 $x^{2} \equiv 16 (\mod 21)$ 有四个解 $(4, 17), (10, 11)$

9.3.6

$Z_{n}^{*}$ 被分成不相交且数量相等的四份，分别为 $Q R_{n}, (- 1) Q R_{n}, ξ Q R_{n}, (- ξ) Q R_{n}$ ，其中 $ξ^{2} \equiv 1 (\mod n)$ , 而且 $L (ξ, n) = - 1$
举例：
对于 $n = 21, ξ = 8, Z_{21}^{*} = {1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}$ ,

\begin{aligned} Q R_{21} & = {1, 4, 16} \\ (- 1) Q R_{21} & = {20, 17, 5} \\ ξ Q R_{21} & = {8, 32, 128} \mod 21 = {8, 11, 2} \\ (- ξ) Q R_{21} & = {13, 10, 19} \end{aligned}

9.3.7

如果已知Blum整数 $n$ ，方程 $x^{2} \equiv a (\mod n)$ 的四个解 $\pm x_{1}, \pm x_{2}$ , 那么可以推导出 $n$ 的两个质数因子 $gcd (x_{1} + x_{2}, n), gcd (x_{1} - x_{2}, n)$

举例：
如果已知方程 $x^{2} \equiv 16 (\mod 21)$ 的四个解为 $\pm 4, \pm 10$ ，那么 $gcd (10 + 4, 21) = 7, gcd (10 - 4, 21) = 3$ ，所以可以推导出21的两个质因子为3和7