hw09

1. 同余方程组求解

题目： 求 $x$ 的所有整数解：

$\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}4)\\ x\equiv 1(\mathrm{mod}5)\end{array}$

解答：

根据中国剩余定理 (CRT)：

计算 $M=3\times 4\times 5=60$。 计算各分项：

• $M_1=20$，求 $20\times y_1\equiv 1(\mathrm{mod}3)⟹2y_1\equiv 1(\mathrm{mod}3)⟹y_1=2$。
• $M_2=15$，求 $15\times y_2\equiv 1(\mathrm{mod}4)⟹3y_2\equiv 1(\mathrm{mod}4)⟹y_2=3$。
• $M_3=12$，求 $12\times y_3\equiv 1(\mathrm{mod}5)⟹2y_3\equiv 1(\mathrm{mod}5)⟹y_3=3$。 合成解： $x=(2\times 20\times 2)+(3\times 15\times 3)+(1\times 12\times 3)=80+135+36=251$取模得到通解：$251\equiv 11(\mathrm{mod}60)$。 所有整数解为： $x=60k+11,k\in \mathbb{Z}$。

---

2. RSA 公钥算法

题目： 设 $n=143$，分解 $n$ 得到素因子。取公钥 $e=7$：

• 私钥 $d=?$
• 对消息 $m=10$ 加密，密文是什么？

解答：

1. 分解 $n$： $n=11\times 13$，故 $p=11,q=13$。
2. 计算欧拉函数： $\varphi (n)=(11-1)(13-1)=10\times 12=120$。
3. 求私钥 $d$： 满足 $ed\equiv 1(\mathrm{mod}\varphi (n))$，即 $7d\equiv 1(\mathrm{mod}120)$。
   • 通过辗转相除法或观察：$7\times 103=721=6\times 120+1$。
   • 故 $d=103$。
4. 加密消息 $m=10$： 密文 $c\equiv m^e(\mathrm{mod}n)$。
   • $c=10^7(\mathrm{mod}143)$。
   • $10^1=10$
   • $10^2=100$
   • $10^4=10000=143\times 69+133\equiv -10(\mathrm{mod}143)$
   • $10^7=10^4\times 10^2\times 10\equiv (-10)\times 100\times 10=-10000\equiv -(-10)=10(\mathrm{mod}143)$。 密文为： $10$。

---

3. 局部化环 ${\mathbb{Z}}_p$

题目： 设 $A=\mathbb{Z}$， $p=p\mathbb{Z}$（$p$ 为素数），$S=\mathbb{Z}-p\mathbb{Z}$。回答关于局部化环 ${\mathbb{Z}}_p$ 的问题：

解答：

(1) 写出 ${\mathbb{Z}}_p$ 中元素形式：

${\mathbb{Z}}_p=\left\{\frac{a}{b}\mid a,b\in \mathbb{Z},b\notin p\mathbb{Z}\right\}=\left\{\frac{a}{b}\mid a,b\in \mathbb{Z},p\nmid b\right\}$

即分子为整数，分母为不能被 $p$ 整除的整数。

(2) 写出 $p{S}^{-1}$ 的元素形式（唯一极大理想）：

$p{\mathbb{Z}}_p=\left\{\frac{pa}{b}\mid a\in \mathbb{Z},b\in \mathbb{Z},p\nmid b\right\}=\left\{\frac{x}{b}\in {\mathbb{Z}}_p\mid p\mid x\right\}$

也就是分子能被 $p$ 整除的那些元素。

(3) 写出 ${\mathbb{Z}}_p$ 中 units（可逆元）的形式：

一个元素 $\frac{a}{b}$ 在局部化环中可逆，当且仅当其分子 $a\in S$。

$\text{Units}({\mathbb{Z}}_p)=\left\{\frac{a}{b}\mid a,b\in \mathbb{Z},p\nmid a\text{ 且 }p\nmid b\right\}$

分子和分母都不能被 $p$ 整除的元素。