信息安全数学基础ppt课件

来自202122
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
问答环节
Q|A 您的问题是？ ——善于提问,勤于思考
结束语
感谢参与本课程，也感激大家对我们工作的支持与积极 的参与。课程后会发放课程满意度评估表，如果对我们
群练习题
信息安全数学基础
1
标题添加
点击此处输入相 关文本内容
标题添加
点击此处输入相 关文本内容
总体概述
点击此处输入 相关文本内容
点击此处输入 相关文本内容
1.证明：|An|=n!/2
3
2.求出正四面体的旋转群
4
3.
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
课程或者工作有什么建议和意见，也请写在上边
感谢观看
The user can demonstrate on a projector or computer, or print the presentation and make it into a film

如, 1与4是模5的平方剩余，2与3是模5的平方非剩余，
所以有
(1) 1， (2) 1， ( 3) 1， (4) 1，(5) 0.
5
5
5
5
5
11
4.5 二次剩余-勒让德符号(1)(n)
n
p1 2
(mod
p);
p
1
1
p1
(2) ( ) 1, ( ) (1) 2 ;
p
p
(3)
a
a1(mod
p)
(
a p
)
(
a1 p
);
(4) ( a1a2 an ) ( a1 )( a2 ) ( an );
p
pp p
ab2 a (5) ( ) ( ), p b.
pp
12
4.5 二次剩余-勒让德符号
例： 求( 20 )与( 2) 37
( 20)
225 ()
(5)
51
1(mod 3)
3 33
2 7
通过引入勒让德符号， 本节给出了较方便的判别 方法。
阿德昂·利·埃·勒 让德（公元1752─公 元1833）,法国数学 家
10
4.5 二次剩余-勒让德符号
定理4.53 给定奇素数p, 对于整数n, 定义Legendre符号为
0， p n；
(
n p
)
1， n是p的平方剩余；
1，n是p的平方非剩余.
111
111
而 (1) 2 1(mod11); 2 2 1(mod11);
111
111
111
(3) 2 (4) 2 (5) 2 1(mod11);
∴ 模11的平方剩余为1，-2，3，4，5；

（2）背包问题 背包问题是这样的一个问题：已知长度为k的 圆形背包及长度分别为a1，a2，…，an的n个 圆形物品。假定这些物品的半径和背包半径 相同，要求从n个物品中选出若干个正好装满 这个背包。
第3章 信息论与数学基础
把背包问题抽象成数学模型，称为子集合问题： 设有长度为n的向量 A=（ a1，a2，…，an ），任意给定一个正整 数k，寻找有没有一些恰好等于k，即求方程：


n
xiai k
i 1
的解向量 x=(x1，x2，…，xn）其中xi=0或1。 当n比较小的时候，可以用穷举法求得解向量， 但当n比较大时，穷举法就不可行了。 背包问题是NP－完全问题。
第3章 信息论与数学基础
（3）离散对数问题 设x，r，n是正整数，已知x，r和n，可以很快 r 地求得 y x (mod n ) 反过来，如果已知y，χ和n，求r使得：
第3章 信息论与数学基础
第3章 信息论与数学基础
3.1 信息论 3.2 复杂性理论 3.3 数论 3.4 因子分解
3.5 素数生成元
3.6 有限域上的离散对数
返回目录
第3章 信息论与数学基础
3.1 信息论 3.1.1 熵和不确定性 3.1.2 语言信息率 3.1.3 密码体制的安全性 3.1.4 唯一解距离
（“≡”表示同余）。
第3章 信息论与数学基础

从0~n-1的整数组成的集合构成了模n的“完 全剩余集”。这意味着，对每一个整数a ，它 的模n的余项是从0~n-1的某个整数。 a模n的运算给出了a的余数，这样的余数是从 0~n-1的某个整数。这种运算称为模变换。例 如，5 mod 3=2。
3.3.9 勒让德符号
3.3.10 雅可比符号

规律：余数－除数－被除 数－忽略
最大公约数的欧几里得算法（续）
欧几里得算法实现
2020/10/3
算 法 gcd(a,b) :
r0 a ; r1 b ; m 1
w h ile
rm 0
do
qm
rm 1 rm
rm 1 rm 1 q m rm
m m 1
r e tu r n (q 1, q 2 ,..., q m , rm ) c o m m e n t : g c d (a , b ) rm
2020/10/3
素数定义及素数个数定理
1.定义：
一个大于1的整数p，只能被1或者是它本身整除,而不能 被其他整数整除，则称整数为素数(prime number)，否 则就叫做合数(composite)。 eg 素数（2，3，5，7，11，13等）
合数（4，6，8，9，12等）
2020/10/3
素数补充定理
2020/10/3
素数个数定理及证明
3.素数个数定理（1）： 素数的个数是无限的
证明：反证法 假设正整数个数是有限的，设为p1,p2,…..,pk 令：p1p2…pk+1=N (N>1) 则N有一个素数p，且p≠pi（i=1,2,…,k). 故p是上述k个素数外的另外一个素数。 因此与假设矛盾。 原因： （1）N（N>1）的除1外的最小正因数q是一个素数 （2）如果q=pi，（i＝1,2,…,k), 且q|N，因此q|(N2020/10/3 p1p2,…..pk)，所以q|1，与q是素数矛盾。
2020/10/3
模运算的除法运算及其性质
4.模运算的性质
（4）除法：相对复杂 如果：12x＝24，那么：3x＝8 如果：12x＝24（mod3），那么：3x＝8（mod3）？？？ 定理：设整数a，b，c，n（n≠0），gcd(a，n)＝1，如果

信息安全数学基础 第一章下演示文稿
1
一、信息安全数学基础的内容
内容： 初等数论、近世（抽象）代数、椭圆曲线
二、教学方式和目的
方式：课堂教学为主 目的：了解和掌握数论和代数的基本知识，包括整数
的可除性 、同余、同余式、二次同余式与平方 剩余 、原根、群、环、域和椭圆曲线等
三、数论和代数在信息安全中的作用
1.1 整除的概念 欧几里得除法
一、整除基本概念及性质
定 义 1.1.1设 a,b是 任 意 两 个 整 数 ,其 中 b0, 如 果 存 在 一 个 整 数 q使 得 等 式
abq 成 立 ,则 称 b整 除 a或 者 a被 b整 除 ,记 作 b|a. 此时q可
写成a / b或 a . b
如 果 b |a ,则 b 叫 做 a 的 因 数 ,而 a 叫 做 b 的 倍 数 . 如 果 b 不 能 整 除 a ,则 记 作 b |a .
假 设 矛 盾 ,所 以 p 是 素 数 . 因 n 是 合 数 ,p 是 n 的 大 于 1 的 最 小 正 因 数 , 所 以
存 在 整 数 n1,使 得 np n 1 1pn 1n
因 此 p2n,故 p n.
整 数 为 素 数 的 判 别 法 定 理 1 .1 .7设 n 是 一 个 正 整 数 ,如 果 对 所 有 的 素 数
p n ,都 有 p |n ,则 n 是 素 数 .
证 ： 反 证 法 （ 素 数 满 足 条 件 ， 排 除 合 数 可 能 ） .假 设 n 为 合 数 ， 题 设 和 定 理 1.1.6相 矛 盾 .因 为 根 据 定 理 1.1.6, 它 的 大 于 1的 最 小 正 因 数 p'(p'|n)是 素 数 ， 且 p'n.因 此 ， n为 素 数 ， 且 满 足 假 设 条 件 .

信息安全数学基础环和域基础知识
1、战鼓一响，法律无声。——英国 2、任何法律的根本；不，不成文法本 身就是 讲道理 ……法 律，也 ----即 明示道 理。— —爱·科 克
3、法律是最保险的头盔。——爱·科 克 4、一个国家如果纲纪不正，其国风一 定颓败 。—— 塞内加 5、法律不能使人人平等，但是在法律 面前人 人是平 等的。 ——波 洛克
谢谢你的阅读
❖ 知识就是财富 ❖ 丰富你的人生
71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。——康德 72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。——西塞罗 73、坚漫其修道远，吾将上下而求索。——屈原 75、内外相应，言行相称。——韩非

根据定理5.1.1，ordm (a) | d ordm (ad ).从而
ordm (a) (ordm (a), d )
| ordm (ad )
d (ordm (a), d )
因为( ordm (a) ， d
) 1，根据定理1.4.1的推论，
(ordm (a), d ) (ordm (a), d )
定理5.1.3设m1是整数，a 是与m互素的整数. 则
ad ak(modm) 的充分必要条件是
dk(mod ordm(a)) (recall RSA算法)
证 根据定理1.1.9(欧几里得除法),存在整数 q,r和q',r' 使得
d ordm(a)qr, k ordm(a)q'r', 又aordm(a) 1(modm)，故
ad 1(modm) 的充分必要条件是
ordm(a) |d
证 从右到左. 设 ordm (a) | d，那么存在整数 k 使得 d k ordm (a). 因此，我们有
ad (aordm (a) )k 1 ( mod m )
从左到右.(反证法)我们有ad 1 (mod m)，若ordm (a) | d不成立， 则由定理1.1.9(欧几里得除法), 存在整数 q，r 使得
证根据定理2.4.1(欧拉定理)，有 a(m) 1(modm)
由定理5.1.1，有ordm(a) ห้องสมุดไป่ตู้(m)，证毕.
注： 求ordm(a)可以通过分解(m)，检验(m)的因子.
(见教材例7，p110)
推论2设p是奇素数，且(p1) 2也是素数.如果a是一个
不被p整除的整数，且也不是模p二次单位根，则
0r ordm(a) 0 r' ordm(a)