纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

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

3cH0-Nu1L   2021-01-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 ∈ Zc ≡ 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.34.44.5);
  4. 具体求解(定理2.1定理4.1)。

2、一次同余式

一次同余式求解的基本思路:

(am)= 1ax ≡ 1(mod m)===> (am)= 1ax ≡ b(mod m)===> ax ≡ b(mod m)0

定理1.1:

设m是一个正整数a是满足m  a的整数则一次同余式ax ≡ 1(mod m)(*)有解的充分必要条件是(am)= 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个不同的根。


相关文章

猜您喜欢

网友评论

Copyright 2020 www.SiJiMeiShi.com 【四季软件园】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式