第3章 同余式 -《信息安全数学基础》

• 2021 年 1 月 19 日
• 笔记

一、基本概念及一次同余式：

1、同余式的基本概念

定义1.1：

设m是一个正整数，f(x)为多项式f(x) = a_nxⁿ + ··· + a₁x + a₀，其中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的完全剩余系中，使得同余式 * 成立的剩余个数叫做同余式 * 的解数。

同余式求解的基本思路：

1. 求解归约（f(x)（mod m）<=== f(x)（mod pα）<=== f(x)（mod p））；
2. 解的存在性（如定理1.1）；
3. 解的个数（如定理1.3，4.4，4.5）；
4. 具体求解（定理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) = a_nxⁿ + ··· + a₁x + a₀为n次整系数多项式，g(x) = x^m + ··· + b₁x + b₀为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 ≡ a_i（mod p），i = 1，···，k，是同余式的k个不同解，则对任何整数x，都有f(x) ≡ f_k(x) · (x – a₁) · ··· ·(x – a_k)（mod p），其中f_k(x)是n – k次多项式，首项系数是a_n。

定理4.3：

4、素数模的同余式的解数估计

定理4.4：

同余式的解数不超过它的次数。

推论：

次数 < p的整系数多项式对所有整数取值模p为0的充要条件是其系数被p整除。

定理4.5：

设p是一个素数，n是一个正整数，n ≤ p。那么同余式f(x) = x_n + ··· + a₁x + a₀ ≡ 0（mod p）有n个解得充分必要条件是x^p – x被f(x)除所得余式的所有系数都是p的倍数。

推论：

设p是一个正整数，d是p – 1的正因数，那么多项式x^d – 1模p有d个不同的根。

上一篇：

//www.cnblogs.com/3cH0-Nu1L/p/14267885.html