信息安全数学基础第6章 近世代数基础-PPT文档资料

– 剩余类的加法和乘法运算
a b a b ,(m m )o a b d a b(m m )o
10.01.2021
编辑ppt
18
2.2 多项式剩余类环和域
1.域上多项式的定义
– 多项式与码字的关系：桥梁；
• 多项式的系数表示
；
• x的幂次表示
；
– 域上的多项式
• 针对系数定义；
• 例如二进制系数多项式，称为二元域GF(2)上的 多项式。
编辑ppt
28
(1) 常数总是多项式的因子。
(2) 一个多项式 f(x) 是否为既约多项式 与所定义的域有关。
(3) 一个多项式既约的充要条件：多项 式Pl(x) 不能分解成两个次数低于Pl(x) 的多项式的乘积。
(4) 完全分解：n次多项式最多能分解成 n个一次多项式的乘积，被称为完全分 解。
(5) 一次多项式一定是既约的。
（3）加法和乘法之间满足如下分配率 (distributive) ：
a(bc) abac
(bc)a baca
则称F是一个域。
10.01.2021
编辑ppt
6
（1）域的阶（针对群中元素的个数），记 为q。
（2）有限域或伽逻华（Galois）域，表示为：
GF(q)。
–域将
10.01.2021
和
编辑ppt
联系在一起？
7
例2-3
– F1：有理数全体、实数全体对加法和乘法都 分别构成域，分别称为有理数域和实数域。
– F2：0、1两个元素模2加构成域；由于该域 中只有两个元素，记为GF(2)。
10.01.2021
编辑ppt
8
• 定理：
– 设p为质数，则整数全体关于p模的剩余类： 0，1，2，…，p-1，在模p的运算下（p模相 加和相乘），构成p阶有限域GF(p)。

近世代数
导言
参考文献： 参考文献： 1）贾中平，张焕国，信息安全数学基础，清华大学 ）贾中平，张焕国，信息安全数学基础， 出版社， 出版社，2006。 。 2）冯登国，信息安全中的数学方法与技术，清华大 ）冯登国，信息安全中的数学方法与技术， 学出本社， 学出本社，2009.
导言
(1) 代数运算 (2) 群 (3) 环与域 (4) 整环中的因子分解 (5) 扩域
= a + (b + c) = a + b + c = a + (b + c ),
所以结合律成立．
§2.1 群的概念 (3) 对任意的 a , b ∈ Z m ,
a + b = a + b = b + a = b + a,
所以交换律成立． (4) 对任意的 a ∈ Zm ，
a + 0 = a + 0 = a,
每个元素都有逆元, 律 , G 中有单位元并且 G 中 每个元素都有逆元 , 则 是一个群. 称 (G, ⋅ ) 是一个群.
Company Logo
§2.2 群的性质
性质3 性质3
为群， 设 G为群，则有
−1 −1
(1) 对任意的 a ∈ G ，有 ( a )
=a ；
(2) 对任意的 a, b ∈ G ，有 ( ab) −1 = b −1 a −1 ； (3) 在群中消去律成立，即设 a , b, c ∈ G ， 如果 ab = ac ，或 ba = ca ，则 b = c ．
§2.2 群的性质 (3) 因为 a 是 a 的逆元，所以 a a = aa
−1 −1
−1 −1 −1
= e.
a 是a −1的逆元．又由逆元的 从而由逆元的定义知，

P. Samuel 著 ✓“Primality and Cryptography”E. Kranakis 著 ✓《椭圆曲线密码学导论》张焕国 等译
2
计
4
课件邮箱
邮箱：infosecmath@ 密码：123456
2
计
5
信息安全数学基础
第1章：整数的可除性
2
计
6
整数论是研究整数的学科
章
方
剩
余
原 根 与 指 标 第 章
素 性连 检分 测数 第第
章
章
代数(群、环、域) --新第8章
(第8,9,10,11,12章)
椭圆曲线 --新第9章
(第13章)
(7) ( 6+14 )
(5)
(4) (3) (2) (1)
2
计
3
➢选用教材：《信息安全数学基础》陈恭亮 著 ➢参考书目：
✓《初等数论》 潘承洞 潘承彪 著 ✓《代数学引论》 第2版 聂灵沼 丁石孙 著 ✓“Commutative Algebra”第1、2卷 O. Zariski &
➢ 计算机只能处理有限数和有限个数，计算机的计算 模型，硬件体系结构的设计与实现，代数编码，软 件设计与实现，计算机通信及密码学等，都广泛使 用了整数理论
➢ 而数学可以处理无穷大
2020/4/24
计算机科学与技术学院
10
数论特点
➢任意两个整数可以相加，相减，相乘， 结果仍是整数
➢但两个整数不一定能在整数的范围内相 除，这是整数系统的特点
➢若未特别指明，凡出现的数都是指整数
2020/4/24
计算机科学与技术学院
12
本章主要内容：
➢整除的概念 ➢欧几里得算法(*) ➢整数的表示 ➢最大公因子与广义欧几里得算法(*) ➢最小公倍数 ➢素数与算数基本定理(*) ➢素数定理

再见
RSA算法中的数学编程问题
素数的概念，最大公约数 欧几里得算法(Euclid)可以计算GCD(a, b) 扩展欧几里得算法(Extended-Euclid)，可以 计算 ax + by = gcd(a, b)中的x, y 大整数的运算 素数的判定 随机数的产生
大素数的查找 整数的模幂，即计算 am mod p
求a x + by = 1的解， 即 a ^ -1 mod b
扩展Euclid 算法
extended_euclid(a, b) { if(b == 0) return(a, 1, 0); else{ let a = kb + r; (d, x, y) = extended_euclid(b, r); return (d, y, x-ky); } }
多次选择a。如果witness(a, n) 返回true， 则n一定不是素数。如果返回false，则n 不是素数的概率小于 ½ 只要测试的次数足够大，则可以相信该 数为素数 Rabin-Miller算法是Nist 推荐的素数检测 算法
梅森素数(Mersenne)素数
p 为素数， Mp = 2p -1，如果Mp也是素数， 则称Mp 为梅森素数 如 p = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127等都是梅森素数 但 p = 23时不是
素数的分布（大约的）
1´1 6 0 800 000
600 000
400 000
200 000
200 000
400 000
600 000
800 000
1´1 0
6
n位十进制数的密度为1/nln10。N=100 时，1/nln10 ≈ 1/230 估算100位的整数，要判定是否整数，要 做多少个除法运算