第3章 同餘式 -《資訊安全數學基礎》
- 2021 年 1 月 19 日
- 筆記
一、基本概念及一次同餘式：
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個不同的根。
上一篇：
//www.cnblogs.com/3cH0-Nu1L/p/14267885.html
