同余与同余式

一、概念及性质

1. 同余的定义？“定义域”？P54 模 m 同余是等价关系吗？P55
   同余的定义并不直接是其字面意义 ，而是“跨度”为模的整数倍。
2. $a_1\equiv{b_1}\pmod{m}$，$a_2\equiv{b_2}\pmod{m}$，则 a₁+a₂，b₁+b₂ 和 a₁a₂，b₁b₂ 之间存在怎样的关系？P56
   由此，某天是星期三，这天后的 2²⁰⁰⁸ 天是星期几？

3. 怎样快速判断某数是否能被 3 或 9 整除？如何借助同余来证明？P57 怎样利用 7×11×13=1001 判断某数是否能被 7，11，13 整除？

4. $d\cdot{a}\equiv{d\cdot{b}}\pmod{m}$，什么条件下 $a\equiv{b}\pmod{m}$？怎么证明？P59
   “可以直接除去与模互素的公因数”

5. $a\equiv{b}\pmod{m}$，d>0，那么 da 与 db 满足什么关系？P59 反过来，如果 $a\equiv{b}\pmod{m}$，且 a，b，m 有公因数 d，那么能得到怎样的关系？
   “同余关系可以整体放大和缩小。换言之，在模和被取模的数中都含有的因数无影响”

6. 模 m 同余可以推出模 m 的因数同余。模一组数同余可以推出模这一组数的最小公倍数同余。怎么证明？P60 因此，模一组素数同余相当于模这些素数的积同余。
   证明利用作差可证，因为模谁同余实际上是说的两数之差的性质。

7. $a\equiv{b}\pmod{m}$，那么(a, m) 和 (b, m) 有何关系？证明。
   （欧几里得除法计算最大公因数）

8. 设 m，n，a 都是正整数，如果 $n^{a}\not\equiv{0, 1}\pmod{m}$，那么对于 n 的素因数 p 有何要求？P61

二、模运算

（笔记补充）

1. 模运算的定义？P61

2. $a+b\pmod{n}=(a\pmod{n}+b\pmod{n})\pmod{n}$。

三、剩余类与完全剩余系

1. 模 m 的 a 的剩余类 C_a 的定义？模 m 共有几个不同的剩余类？剩余类的剩余（代表元）？任一整数必包含在一个剩余类中吗？所有剩余类的集合怎么用符号表示？模为素数时这个符号还可以怎样表示？P62
   （由 mZ 诱导的对 Z 的划分）（是模 m，不要缺字）剩余类实际上是集合。
2. 什么是 $(\pmb{Z}/m\pmb{Z})^{*}$？对于$C_a, C_b\in(\pmb{Z}/m\pmb{Z})^*$，有$C_{a\cdot{b}}\in{(\pmb{Z}/m\pmb{Z})^*}$。P64
   （简化剩余类集合）P69

3. 什么是完全剩余系？一个完全剩余系中有几个数？ P63 最小非负完全剩余系、最小正完全剩余系、最大非正完全剩余系、最大负完全剩余系？绝对值最小完全剩余系？P64

4. k 遍历模 m 的完全剩余系，(a, m)=1，经过怎样变换还能得到完全剩余系？证明。P65
   “一个与模互素的数遍历相乘整个完全剩余系，得到的仍然是完全剩余系”。直接反证作差证明。

5. 若 k₁，k₂ 分别遍历模 m₁，m₂ 的完全剩余系，且 m₁，m₂ 满足   ，则   遍历模   的完全剩余系。证明？P65
   （肯定是遍历模 m₁m₂ 的完全剩余系，因为 k₁ 有 m₁ 个候选项，k₂ 有 m₂ 个候选项。）
   想证遍历完全剩余系，只需要任取两个数，推导出这两个数不同余即可。
   “对于互素的m₁m₂，m₂ 的完全剩余系中的数与 m₁ 之积和 m₁ 完全剩余系中的数与 m₂ 之积的和遍历 m₁m₂ 的完全剩余系。”
   推论：p，q 是两个不同的素数，对任意整数 c，能找出唯一的一对 x，y 使得$q\cdot{x}+p\cdot{y}\equiv{c}\pmod{p\cdot{q}}$。（任意小于两素数之积的整数都可以被这两个素数线性表出）P66

四、简化剩余类、简化剩余系与逆元

1. 简化剩余类、简化剩余的定义？P68 模 m 的简化剩余类的全体组成的集合怎么用符号表示？m 为素数时符号怎么表示？P69

2. 若剩余类中的一个剩余与 m 互素，是不是整个剩余类中的剩余均与 m 互素？P68
   （用欧几里得除法计算最大公因数证明）

3. 简化剩余系的定义？P69

4. k 遍历模 m 的某个简化剩余系时，(a, m)=1，ak 也遍历模 m 的一个简化剩余系吗？（和完全剩余系中类似的性质作比较）证明。P70

5. 设 m₁，m₂ 是互素的两个正整数，如果 k₁，k₂ 分别遍历模 m₁，模 m₂ 的简化剩余系，则 m₂k₁+m₁k₂ 遍历模 m₁m₂ 的简化剩余系吗？P72（类似完全剩余系中的性质）证明。（P73引理）

6. 逆元的定义？（逆元其实不是在这里定义的）“定义域”？具有唯一性吗？证明？（两种方法，一种是用简化剩余系证其存在性，再证其唯一性；另一种是构造性证明，即用广义欧几里得除法求 a 和 m 的最大公因数，在这个过程中就可以具体地求出逆元的值）

五、欧拉函数、欧拉定理、费马小定理与 Wilson 定理

1. 欧拉函数的定义？p 为素数时 $\varphi(p^\alpha)$ 如何计算？P68

2. 模 m 的简化剩余系的元素个数为？P69 简化剩余系判别法？P70

3. 欧拉函数的可乘性？证明？P73
   （利用欧拉函数的值等于简化剩余系中元素的个数这一性质，把两个因数 m，n 的简化剩余系之积转化为类似两组简化剩余系“笛卡尔积”的形式作为 mn 的简化剩余系元素；需要证明这一关系是双射的，上面简化剩余系也要注意双射）

4. 已知正整数 m 的标准分解式，如何求其欧拉函数？证明。P73
   利用可乘性。“一个数的欧拉函数等于其本身连续乘上 1 减去素因子的倒数”。

5. 欧拉定理的内容？证明。P77
   （利用欧拉函数值等于简化剩余系中元素个数的性质，a 乘上最小正简化剩余系得一组简化剩余系，这组简化剩余系中所有元素乘积（构造出 $a^{\varphi(m)}$）与最小正简化剩余系是同余的，移项后把最小正简化剩余系去掉（和 m 互素）即可证明）

6. 费马小定理内容，证明。P78
   有点类似欧拉定理的素数情况。

7. Wilson 定理内容？证明。P79
   “素数减一的阶乘加一能被素数整除。”（[1, p-1]两两配对，使得其互为逆元）

六、RSA 公钥密码算法

执行步骤：

1. 选取两个不同的大素数 p，q；
2. 计算 n=pq，$\varphi(n)=(p-1)(q-1)$；
3. 随机选取正整数 e，$1<e<\varphi(n)$，满足$(e, \varphi(n))=1$；
4. 计算 d，满足 $de\equiv{1}\pmod{\varphi(n)}$；p、q、$\varphi(n)$、d 是保密的，丢弃 p、q、$\varphi(n)$，只保留 n、e、d，(n, e) 公开，(n, d) 为私钥，(n, e) 为公钥。
5. 加密变换：对明文 a，1<$a$<$n$，加密后的密文为 $c\equiv{a^e}\pmod{n}$；
6. 解密变换：对密文 c，1<$c$<$n$，解密后的明文为 $a\equiv{c^d}\pmod{n}$。
   （依次求解 p，q，n，e，d，c，a；注意公钥是 K_e=(n, e)，私钥是 K_d=(n, d)）
   如何证明？P77（a 与 n 互素好说，不互素时 a 只能是其中一个数 q 的倍数而不可能是公倍数，证出 a^q-1=kq+1，则 a^(p-1)(q-1)=k’q+1，同乘 a=bp 得证。）

书写：设 RSA 公钥密码算法使用 26 字符集 {a, b, c …, x, y, z} = {0, 1, 2, …, 23, 24, 25}，明文信息空间是由 2 字符构成的集合 {aa, ab, ac, …, zx, zy, zz}，以两字符一组对 “de” 进行编码。

七、模重复平方计算法

可以用于计算大底数、相对小指数的模运算，例如 $12996^{227}\pmod{37909}$。
把指数 n 展开成 2 的幂之和，令 a_i 表示已经取模乘到 b²ⁱ 的积；b_i 表示 $b^{2^i}\pmod{m}$；a₀=0，如果 2ⁱ 在 n 展开为 2 的幂的和的式子里系数为 0，那么 a_i=a_i-1，如果系数为 1 则 $a_i=a_{i-1}\cdot{b_i}\pmod{m}$；计算 $b_{i+1}=b_i^2\pmod{m}$，如此循环。
查看参考代码。

但是，如果计算的是 $2^{20046118}\pmod{7}$ 此类小底数、大指数的模运算，那么直接应用 $2^3\pmod{7}=1$ 更加合适。

八、同余式与中国剩余定理

1. 同余式的定义？什么是次数 degf（要满足什么条件）？什么是同余式的一个解？为什么同余式的解 a 常写成 $x\equiv{a}\pmod{m}$ ？什么是同余式的解数？P91
   （模 m 同余于 0 的 n 多项式；之所以要同余于 0 是因为这个多项式已经自带常数项了）

2. 模 m 的可逆元和逆元有何不同？P92

3. 设 m₁，m₂，…，m_k 是两两互素的正整数，那么同余式组
   $$\begin{cases} \begin{align} x &\equiv{b_1}\pmod{m_1} \\ &\vdots \\ x &\equiv{b_k}\pmod{m_k} \end{align} \end{cases}$$ 一定有唯一解吗？将其解用构造和递归两种方法表示。（背不过递归的话，可以从它的推导入手，现场推导）P97
   给出其构造证明（先证明其是唯一的，即解必然位于同一剩余类中；再把已知的解代入方程组中，验证这个解是满足所有方程的）（P99）和递归证明（即“归纳构造”）（从 k=2 入手，关键是借助逆元求出 y₁；然后假设 i-1 时命题成立，像对待 k=2 一样地求解，即可证明；每次把新一代的式子用上一代求出来的解和这次式子里已知的表示，这才起到递归的作用；注意 x≠x_n-1，但 x=x_n）（P101）。
   查看参考代码。

九、二次同余式与平方剩余

1. 二次同余式的一般形式？P125

2. a 是模 m 的平方剩余（二次剩余）是什么意思？a 是模 m 的平方非剩余呢（也要满足前式的“定义域”条件）？P125

3. 什么是欧拉判别条件？要求 m 是什么样的数？P129

4. 什么是勒让得符号？“定义域”？P131 欧拉判别法则可以用勒让得符号怎么改写？P132

十、离散对数与 Diffie-Hellman 密钥共享算法

1. 离散对数是什么？P79，P191
   （为了实现在 [1, $\varphi(m)$]内唯一，需要满足原根和互素 ）
2. Diffie-Hellman 密钥共享算法步骤：P79
   Alice 选取素数 p 和正整数 g，1≤g≤p 且 (g, p)=1，公开 p 和 g。
   Alice 选取 x∈{1, 2, …, p-1}，计算 $R_1=g^x\pmod{p}$，并将 R₁ 发送给 Bob。
   Bob 选取 y∈{1, 2, …, p-1}，计算 $R_2=g^y\pmod{p}$ 并将 R₂ 发送给 Alice。
   Eve 可以获得 R₁ 和 R₂，但很难计算出 x 或 y （离散对数求解困难）。
   Alice 计算密钥 $k=R_2^x\pmod{p}=(g^y)^x\pmod{p}=g^{xy}\pmod{p}$，Bob 计算密钥 $k=R_1^y\pmod{p}=(g^x)^y\pmod{p}=g^{xy}\pmod{p}$。
   （分别把 g^x，g^y 发送给对方，结合对方手里掌握的另一半信息，双方都能得到一样的密钥）
   查看参考代码。