亲宝软件园·资讯

展开

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

3cH0-Nu1L 人气:0

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

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的完全剩余系中,使得同余式 * 成立的剩余个数叫做同余式 * 的解数。

同余式求解的基本思路:

  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) = 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个不同的根。

加载全部内容

相关教程
猜你喜欢
用户评论