第3章 同余式 -《信息安全数学基础》
二、中国剩余定理；
三、高次同余式的解数及解法；
四、素数模的同余式。
一、基本概念及一次同余式：
1、同余式的基本概念
定义1.1：
设m是一个正整数，f(x)为多项式f(x) = anxn + ··· + a1x + a0，其中ai是整数，则f(x) ≡ 0（mod m）（*）叫做模m同余式。
若an 0（mod m），则n叫做f(x) 的次数，记为degf。此时 * 式又叫做模m的n次同余式。
如果整数x = a使得 * 式成立，即f(a) ≡ 0（mod m）则a叫做该同余式 * 的解。
事实上，满足x ≡ a（mod m）的所有整数使得同余式 * 成立，即a所在剩余类Ca = { c | c ∈ Z，c ≡ a（mod m）}中的每个剩余都使得同余式 * 成立，因此，同余式 * 的解a通常写成x ≡ a（mod m）。
在模m的完全剩余系中，使得同余式 * 成立的剩余个数叫做同余式 * 的解数。
同余式求解的基本思路：
- 求解归约（f(x)（mod m）<=== f(x)（mod pα）<=== f(x)（mod p））；
- 解的存在性（如定理1.1）；
- 解的个数（如定理1.3，4.4，4.5）；
- 具体求解（定理2.1，定理4.1）。
2、一次同余式
一次同余式求解的基本思路：
（a，m）= 1，ax ≡ 1（mod m）===> （a，m）= 1，ax ≡ b（mod m）===> ax ≡ b（mod m）0
定理1.1：
设m是一个正整数，a是满足m a的整数，则一次同余式ax ≡ 1（mod m）（*）有解的充分必要条件是（a，m）= 1。而且，当同余式 * 有解时，其解是唯一的。
定义1.2：
设m是一个正整数，a是一个整数。如果存在整数a’使得a · a’ ≡ a’ ` a ≡ 1（mod m）成立，则a叫做模m可逆元。
根据定理1.1，在模m的意义下，a’是唯一存在的。这是a’叫做a的模m逆元，记作a’ = a-1（mod m）。
因此，在定理3.1的条件下，同余式（*）即ax ≡ 1（mod m）的解可写成x ≡ a-1（mod m）。
定理1.2：
设 m 是一个正整数，则整数 a 是模 m简化剩余的充要条件是整数 a 是模 m 逆元。
定理1.3：
二、中国剩余定理：
1、中国剩余定理：“物不知数”与韩信点兵
定理2.1：
2、两个方程的中国剩余定理
定理2.2：
定理2.3：
3、中国剩余定理之构造证明
4、中国剩余定理之递归证明
5、中国剩余定理之应用 —— 算法优化
例2.1：
例2.2：
例2.3：
定理2.4：
命题2.1：
推论：
三、高次同余式的解数及解法：
1、高次同余式的解数
定理3.1：
2、高次同余式的提升
定理3.2：
3、高次同余式的提升 —— 具体应用
例3.1：
四、素数模的同余式：
1、素数模的多项式欧几里得除法
引理4.1（多项式欧几里得除法）：
设f(x) = anxn + ··· + a1x + a0为n次整系数多项式，g(x) = xm + ··· + b1x + b0为m ≥ 1次首一整系数多项式，则存在整系数多项式q(x)和r(x)使得f(x) = q(x) · g(x) + r(x)，deg r(x) < deg g(x)。
2、素数模的同余式的简化
定理4.1：
同余式与一个次数不超过p – 1的模p同余式等价。
3、素数模的同余式的因式分解
定理4.2：
设1 ≤ k ≤ n。如果x ≡ ai（mod p），i = 1，···，k，是同余式的k个不同解，则对任何整数x，都有f(x) ≡ fk(x) · (x – a1) · ··· ·(x – ak)（mod p），其中fk(x)是n – k次多项式，首项系数是an。
定理4.3：
4、素数模的同余式的解数估计
定理4.4：
同余式的解数不超过它的次数。
推论：
次数 < p的整系数多项式对所有整数取值模p为0的充要条件是其系数被p整除。
定理4.5：
设p是一个素数，n是一个正整数，n ≤ p。那么同余式f(x) = xn + ··· + a1x + a0 ≡ 0（mod p）有n个解得充分必要条件是xp – x被f(x)除所得余式的所有系数都是p的倍数。
推论：
设p是一个正整数，d是p – 1的正因数，那么多项式xd – 1模p有d个不同的根。