密码学——第4章-数论与有限域基础
- 格式：pptx
- 大小：3.61 MB
- 文档页数：10
下载文档原格式
合集下载
数论在密码学中的应用
数论在数字签名中的应用
01 数字签名算法的基本原理
用私钥对信息进行签名，公钥验证签名的方 法
02 数论如何保证数字签名的安全性
数论算法保证数字签名的唯一性和不可伪造 性
03
● 02
第2章 质数和素数
质数的定义和性 质
质数是指只能被1和 自身整除的正整数。 在密码学中，质数被 广泛运用于加密算法 中，其特性决定了加 密过程的安全性。费 马小定理是一个重要 的数论定理，在密码 学中也有着重要的应 用。Fra bibliotek欧拉函数
欧拉函数的定义和 性质
欧拉函数是小于等于n的正 整数中与n互质的数目。 欧拉函数的计算涉及较多 数论知识。
欧拉定理及其证明
欧拉定理是一个与欧拉函 数相关的重要定理。 其证明需要一定的数论知 识和技巧。
欧 拉 函 数 在 RSA 加 密算法中的应用
RSA加密算法中的密钥生 成依赖于欧拉函数的性质。 欧拉函数在RSA算法的加 密和解密过程中起到关键 作用。
费马大定理
费马大定理 的概念及历
史
介绍费马大定理 的由来和发展
费马大定理 在密码学中
的应用
探讨费马大定理 在密码学领域的
具体应用
费马大定理 的证明
讨论费马大定理 的证明过程
模运算
模运算是一种数学运 算，常用于密码学中 的加密算法。它具有 独特的性质和应用， 在数据传输和信息加 密过程中发挥重要作 用。模逆元的计算方 法是模运算中的重要 计算方式之一。
03 医疗健康领域的数字签名
保护病历和医疗数据的隐私性
数字签名的技术 原理
数字签名使用非对称 加密技术保障数据传 输的安全性和完整性， 发送者使用私钥对信 息进行签名，接收者 使用公钥进行验证。 这种加密方式基于数 论的难解性原理，确 保签名不可伪造。
密码学——第4章 数论与有限域基础 ppt课件
一般地，由 c = gcd(a, b)可得： 对每一素数p， cp = min(ap, bp)
PPT课件
数论基础
第8页/共131页
►素数与互素
如果 gcd(a, b) = 1，则称 a 和 b 互素 整数 a, b 互素是指除 1 之外它们没有其它公因子，
例如：8 与15 互素
8 的因子：1, 2, 4, 8 15 的因子：1, 3, 5, 15 1 是 8 与15 唯一的公因子
PPT课件
数论基础
第6页/共131页
►素数与互素
称 c 是两个整数 a、b 的最大公因子，当且仅当： ① c 是 a 的因子也是 b 的因子， 即 c 是 a、b 的公因子 ② a 和 b 的任一公因子，也是 c 的因子
表示为 c = gcd(a, b)
PPT课件
数论基础
第7页/共131页
#: if Y3=妨0设thbe<na）re，tu即rn存X在3x=(gxc<da()f，, d使)；得nbox≡i1nvmeordsea;。 if Y►3=扩1展thEenucrliedtu算r法n 可Y求3=出gcdgc(df,(ad,)b；)，Y当2=gdc-d1 (ma,obd) =f;1， Q=X3还/Y得3到；b 的逆元。 (T1, T2, T3)←(X1-QY1, X2-QY2, X3-QY3); (X1, X2, X3)←(Y1, Y2, Y3); (Y1, Y2, Y3)←(T1, T2, T3); goto #;
3
x4
都有54乘00法逆54 元20。74
0 4
4 1
0 6
4 3
667012345 606420642
770123456 707654321 PPT课件
PPT课件
数论基础
第8页/共131页
►素数与互素
如果 gcd(a, b) = 1，则称 a 和 b 互素 整数 a, b 互素是指除 1 之外它们没有其它公因子，
例如：8 与15 互素
8 的因子：1, 2, 4, 8 15 的因子：1, 3, 5, 15 1 是 8 与15 唯一的公因子
PPT课件
数论基础
第6页/共131页
►素数与互素
称 c 是两个整数 a、b 的最大公因子，当且仅当： ① c 是 a 的因子也是 b 的因子， 即 c 是 a、b 的公因子 ② a 和 b 的任一公因子，也是 c 的因子
表示为 c = gcd(a, b)
PPT课件
数论基础
第7页/共131页
#: if Y3=妨0设thbe<na）re，tu即rn存X在3x=(gxc<da()f，, d使)；得nbox≡i1nvmeordsea;。 if Y►3=扩1展thEenucrliedtu算r法n 可Y求3=出gcdgc(df,(ad,)b；)，Y当2=gdc-d1 (ma,obd) =f;1， Q=X3还/Y得3到；b 的逆元。 (T1, T2, T3)←(X1-QY1, X2-QY2, X3-QY3); (X1, X2, X3)←(Y1, Y2, Y3); (Y1, Y2, Y3)←(T1, T2, T3); goto #;
3
x4
都有54乘00法逆54 元20。74
0 4
4 1
0 6
4 3
667012345 606420642
770123456 707654321 PPT课件
密码学中的数论基础课件
02
RSA算法的安全性基于大数分解的难度，使得 加密和解密过程更加复杂。
03
RSA算法广泛应用于数据传输和网络安全领域 。
ElGamal算法
ElGamal算法是一种基于离散对数问题的公钥加密算法。 该算法利用了数论中的离散对数问题，使得加密和解密过程更加高效。
ElGamal算法在数字签名和密钥协商等领域也有广泛应用。
展望：量子密码学与后量子密码学的未来发展
后量子密码学
后量子密码学是指那些在量子计算机时代仍然具有优 势的密码系统。随着量子计算机的发展，许多传统的 加密算法可能会被破解，而后量子密码学则能够提供 更为安全的加密方式。未来，后量子密码学会得到越 来越广泛的应用和发展。
THANKS
和窃听的风险。
复杂性
为了实现更高级别的 安全性，密码学需要 处理复杂的数学问题 和计算难题。这使得 密码学在实际应用中 面临一定的复杂性挑
战。
可用性
密码学需要保证信息 的可用性和完整性。 在现实生活中，由于 各种原因，如网络延 迟、系统故障等，可 能会出现信息不可用
或损坏的情况。
隐私保护
随着大数据和人工智 能的发展，个人隐私 保护成为一个重要的 问题。密码学需要在 保证信息传输安全的 同时，确保个人信息 不被泄露和滥用。
圆曲线等。
第四部分
04
介绍密码学中的一些现代协议，如密钥交换协 议、数字签名方案和零知识证明等，并介绍其
原理、实现和应用。
02
数论基本概念
整数的性质
整数的分类
正整数、负整数和零。
整数的性质
加法、减法、乘法和除法等运算的封闭性、交换 律、结合律等。
整数的基本运算
加法、减法、乘法和除法等。
现代密码学--4.1 数论基础知识.ppt
推论：a的阶整除j(n)。
本原根：a的阶m等于j(n)，a为n的本原根。 如果a是n的本原根，a1,a2,...,a j(n)在模n下互不相
同且与n互素。
本原根不唯一。
并非所有元素都有本原根，仅有以下形式的整数 才有本原根：2，4，pa,2pa, p是奇素数
2019年8月25
感谢你的观看
15
是困难的，这就是离散对数问题。
2019年8月25
感谢你的观看
27
现代密码学
（3）多项式求根问题
有限域GF（p）上的一个多项式：
y f (x) xn an1xn1 a1x a0 mod p
已知 a0 , a1,..., an1 , p和x，求y是容易的，
而已知y,
a0,a1,..，., an求1 x则是困难的，这
⑥ 若a b mod n，c d mod n，则a+c b+d (mod n), ac bd (mod n)。
2019年8月25
感谢你的观看
8
现代密码学
模运算
一般的，定义Zn为小于n的所有非负整数集 合，即Zn={0, 1,…, n1}，称Zn为模n的同余 类集合。Zn中的加法（+）和乘法（）都为 模n运算，具有如下性质： ① 交换律 (w+x)mod n = (x+w) mod n (wx)mod n = (xw) mod n
感谢你的观看
7
现代密码学
同余及其性质
同余有如下性质：
① 若n|（ab），则a b mod n。
② 若a mod n b mod n，则a b mod n。
③ a a mod n。
④ 若a b mod n，则b a mod n。
本原根：a的阶m等于j(n)，a为n的本原根。 如果a是n的本原根，a1,a2,...,a j(n)在模n下互不相
同且与n互素。
本原根不唯一。
并非所有元素都有本原根，仅有以下形式的整数 才有本原根：2，4，pa,2pa, p是奇素数
2019年8月25
感谢你的观看
15
是困难的，这就是离散对数问题。
2019年8月25
感谢你的观看
27
现代密码学
（3）多项式求根问题
有限域GF（p）上的一个多项式：
y f (x) xn an1xn1 a1x a0 mod p
已知 a0 , a1,..., an1 , p和x，求y是容易的，
而已知y,
a0,a1,..，., an求1 x则是困难的，这
⑥ 若a b mod n，c d mod n，则a+c b+d (mod n), ac bd (mod n)。
2019年8月25
感谢你的观看
8
现代密码学
模运算
一般的，定义Zn为小于n的所有非负整数集 合，即Zn={0, 1,…, n1}，称Zn为模n的同余 类集合。Zn中的加法（+）和乘法（）都为 模n运算，具有如下性质： ① 交换律 (w+x)mod n = (x+w) mod n (wx)mod n = (xw) mod n
感谢你的观看
7
现代密码学
同余及其性质
同余有如下性质：
① 若n|（ab），则a b mod n。
② 若a mod n b mod n，则a b mod n。
③ a a mod n。
④ 若a b mod n，则b a mod n。
《密码学基础》课程教学大纲
《密码学基础》课程教学大纲（Fundamentals of Cryptography）课程编号: 1223527课程性质：专业课适用专业：计算机科学与技术先修课程：线性代数、概率论与数理统计、离散数学后续课程：总学分：2学分一、教学目的与要求1. 教学目的密码学包含两个密切相关的方面，其一是密码编码学，研究编写出好的密码系统的方法；其二是密码分析学，研究攻破一个密码系统的途径，恢复被隐蔽信息的本来面目。
通过本课程的学习使学生初步掌握密码编码学的知识、了解密码分析学的基本概念和方法。
2. 教学要求通过本课程的学习，要求学生能初步掌握密码学的主要内容，包括：公钥密码，分组密码，伪随机序列发生器，序列密码，数字签名等等。
要求重点掌握各种密码算法和密码协议及其设计原理，掌握密钥管理、数字签名、身份认证、散列函数等核心技术。
二、课时安排三、教学内容1. 密码学的基本概念(2学时)(1)教学基本要求了解：信息安全模型；信息安全与密码学的关系；密码学的发展方向。
理解：密码学的发展与分类；密码学的基本概念；现代密码学的理论基础。
(2)教学内容①对安全威胁的被动攻击（截获）与主动攻击（中断、篡改、伪造）；②信息安全的三个特性（保密性Confidentiality、完整性Integrity、可用性Availability）；③密码学的分类（密码编码学、密码分析学、密码密钥学）；④密码编码学的分类（对称密码与非对称密码）；⑤密码分析及对密码系统攻击能力等级。
2. 分组密码(4学时)(1)教学基本要求了解：DES；对DES的攻击方法；分组密码设计的一般原理；IDEA；Double-DES，Triple-DES；AES的产生背景。
理解：DES算法；分组密码(DES)的使用模式；IDEA的总体结构；AES算法；逆元的计算；分组密码的工作模式。
(2)教学内容①DES算法的整体结构(重点)；②初始置换、逆初始置换、乘积变换、16轮迭代、函数f、S-盒、P置换；③子密钥的生成及DES的解密过程；④DES的雪崩效应、DES的弱密钥及半弱密钥、对DES的攻击；⑤Double-DES与Triple-DES；⑥分组密码设计的一般原理及分组密码的工作模式（ECB、CBC、CFB、OFB）；⑦IDEA的总体结构，8轮迭代、输出变换、密钥调度、乘积运算；⑧逆元的计算；⑨DES，Double-DES，Triple-DES，IDEA的安全性；⑩AES分组密码算法（轮变换、加轮密钥、密钥调度、密钥扩展等）。
北交大 密码学课件 第4章_数论初步和有限域
模运算
设 n 是一正整数，a 是整数，如果用 n 除 a，得商为 q， 余数为 r，则 a=qn+r, 0≤r<n,
q a n
其中 x 为小于或等于 x 的最大整数。
a n a mod n a 用 a mod n 表示余数 r，则 n 。
算法中的变量有以下关系：
fT1+dT2=T3; fX1+dX2=X3; fY1+dY2=Y3
在算法Euclid (f, d)中，X等于前一轮循环中的Y， Y等于前一轮循环中的X mod Y。而在算法 Extended Euclid(f, d)中，X3等于前一轮循环中的 Y3，Y3等于前一轮循环中的X3-QY3，由于Q是Y3 除X3的商，因此Y3是前一轮循环中的Y3除X3的余 数，即X3 mod Y3，可见Extended Euclid(f, d)中 的X3、Y3与Euclid(f, d)中的X、Y作用相同，因此 可正确产生gcd(f, d)。
推广的Euclid算法先求出gcd(a, b)，当gcd(a,
b)=1时，则返回b的逆元。
Extended Euclid(f, d) （设 f >d） 1. (X1, X2, X3)←(1, 0, f); 2. if Y3=0 then return 3. if Y3=1 then return 4. Q X 3 / Y3 ； 5. (T1, T2, T3)←(X1-QY1, X2-QY2, X3-QY3); 6. (X1, X2, X3)←(Y1, Y2, Y3); 7. (Y1, Y2, Y3)←(T1, T2, T3); 8. goto 2。 (Y1, Y2, Y3)←(0, 1, d); X3=gcd(f, d)；no inverse; Y3=gcd(f, d)；Y2=d-1 mod f;
2084公钥密码基础
素数定理：
设(x)是小于x的素数的个数,则
(x)
x ,且当x lnx
,(xx)
1
lnx
在各种应用中，我们需要大的素数,如100位的素数
素数是构成整数的因子，每一个整数都是由一个或几个素数 的不同次幂相乘得来的。
6
3.最大公约数
a和b的最大公约数是能够同时整除a和b的最大正整 数，记为gcd(a,b)。 – 如：gcd(20,24)=4 , gcd (15,16)=1
20
离散对数（指标）
某素数p，有本原根a，且： X1=a1mod p，X2=a2mod p ，…，Xp-1=ap-1mod p， 则：x1≠x2≠…≠ xp-1 令：S={x1,x2,…, xp-1}，T={1,2,…,p-1} 则：S=T 对于任意整数b，有b≡r (mod p) (0≤r≤p-1) 所以，对于b和素数p的本原根a，有唯一的幂i，使得：
10
5.除法
设整数a，b，c，n(n ≠0)，且gcd(a,n)=1。 如果ab≡ac (mod n)，那么b≡c (mod n)
11
4.2.2 欧几里德算法(Euclid)
欧几里德算法又称辗转相除法，用于计算两个整数a，b的最 大公约数。
其计算原理依赖于下面的定理： gcd(a,b) = gcd(b,a mod b)
推论：给定两个素数p, q,两个整数 n,m，使得n=pq, 0<m<n ；则对于任意整数k ，下列关系成立： m kф(n)+1 ≡ m (mod n)
例如：p=2，q=3，n=6，m=4 ，ф(6)=2
(42×2+1 ＝ 45＝1024 )≡4 (mod 6)，k=2 18
4.2.6 离散对数
设(x)是小于x的素数的个数,则
(x)
x ,且当x lnx
,(xx)
1
lnx
在各种应用中，我们需要大的素数,如100位的素数
素数是构成整数的因子，每一个整数都是由一个或几个素数 的不同次幂相乘得来的。
6
3.最大公约数
a和b的最大公约数是能够同时整除a和b的最大正整 数，记为gcd(a,b)。 – 如：gcd(20,24)=4 , gcd (15,16)=1
20
离散对数（指标）
某素数p，有本原根a，且： X1=a1mod p，X2=a2mod p ，…，Xp-1=ap-1mod p， 则：x1≠x2≠…≠ xp-1 令：S={x1,x2,…, xp-1}，T={1,2,…,p-1} 则：S=T 对于任意整数b，有b≡r (mod p) (0≤r≤p-1) 所以，对于b和素数p的本原根a，有唯一的幂i，使得：
10
5.除法
设整数a，b，c，n(n ≠0)，且gcd(a,n)=1。 如果ab≡ac (mod n)，那么b≡c (mod n)
11
4.2.2 欧几里德算法(Euclid)
欧几里德算法又称辗转相除法，用于计算两个整数a，b的最 大公约数。
其计算原理依赖于下面的定理： gcd(a,b) = gcd(b,a mod b)
推论：给定两个素数p, q,两个整数 n,m，使得n=pq, 0<m<n ；则对于任意整数k ，下列关系成立： m kф(n)+1 ≡ m (mod n)
例如：p=2，q=3，n=6，m=4 ，ф(6)=2
(42×2+1 ＝ 45＝1024 )≡4 (mod 6)，k=2 18
4.2.6 离散对数
现代密码学理论与实践-有限域
– (A3) 单位元Identity element: G中存在一个元素e， 对于G中任意元素a，都有a•e=e•a=a成立
– (A4) 逆元Inverse element: 对于G中任意元素a, G中 都存在一个元素a’，使得a•a’=a’•a=e成立
2019/9/6
3/51
群、有限群和无限群
• 用Nn表示n个不同符号的集合，{1,2,…,n}. n个不同符号的一 个置换是一个Nn到Nn的一一映射。定义Sn为n个不同符号的所有 置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n}的 一个置换，容易验证Sn是一个群：
②对称性：若a=b mod n，则b=a mod n ③传递性: 若a=b mod n 且b=c mod n，则a=c mod n ④如果 a=b mod n且 c=d mod n，则
a+c=(b+d) mod n a-c=(b-d) mod n a•c=(b•d) mod n
⑤ (a+b) mod n = (a mod n + b mod n) mod n (a-b) mod n = (a mod n - b mod n) mod n (a•b) mod n = (a mod n • b mod n) mod n
现代密码学理论与实践
有限域
本章要点
• 域是一些元素的集合，其上定义了两个算术运算(加 法和乘法)，具有常规算术性质，如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。
• 模算术是一种整数算术，它将所有整数约减为一个固
定的集合[0,1,…,n-1]，n为某个整数。任何这个集 合外的整数通过除以n取余的方式约减到这个范围内。
模n。对于任意整数a，我们总可写出： a =⌊a/n」x n + (a mod n)
– (A4) 逆元Inverse element: 对于G中任意元素a, G中 都存在一个元素a’，使得a•a’=a’•a=e成立
2019/9/6
3/51
群、有限群和无限群
• 用Nn表示n个不同符号的集合，{1,2,…,n}. n个不同符号的一 个置换是一个Nn到Nn的一一映射。定义Sn为n个不同符号的所有 置换组成的集合。Sn中的每一个元素都代表集合{1,2,…,n}的 一个置换，容易验证Sn是一个群：
②对称性：若a=b mod n，则b=a mod n ③传递性: 若a=b mod n 且b=c mod n，则a=c mod n ④如果 a=b mod n且 c=d mod n，则
a+c=(b+d) mod n a-c=(b-d) mod n a•c=(b•d) mod n
⑤ (a+b) mod n = (a mod n + b mod n) mod n (a-b) mod n = (a mod n - b mod n) mod n (a•b) mod n = (a mod n • b mod n) mod n
现代密码学理论与实践
有限域
本章要点
• 域是一些元素的集合，其上定义了两个算术运算(加 法和乘法)，具有常规算术性质，如封闭性、结合律、 交换律、分配律、加法逆和乘法逆等。
• 模算术是一种整数算术，它将所有整数约减为一个固
定的集合[0,1,…,n-1]，n为某个整数。任何这个集 合外的整数通过除以n取余的方式约减到这个范围内。
模n。对于任意整数a，我们总可写出： a =⌊a/n」x n + (a mod n)
密码学中的数学方法
密码学中的数学方法密码学是保护信息安全的一门科学，涵盖了从数据加密、数据完整性到身份认证等多方面的技术与理论。
它依赖于复杂的数学原理与方法，以确保信息在传输与存储过程中的保密性、完整性和可用性。
在这篇文章中，我们将探讨一些实现密码学的重要数学方法，包括数论、代数结构、组合数学以及概率论等。
数论在密码学中的应用数论是研究整数及其性质的数学分支，在密码学中扮演着至关重要的角色。
很多现代密码算法都依赖于数论的一些基本概念。
质数与分解问题质数是大于1的自然数，除了1和它本身外没有其他因子。
利用质数构成的结构，诸如RSA加密算法得以实现。
RSA算法的安全性主要基于大数分解的困难性。
即当两个大质数相乘时，找到这两个质数几乎是不可能的。
这种性质在许多加密系统中得到了应用。
模运算与同余模运算是处理整数的一种方式，可以看作是在一个有限集合上进行的运算。
在密码学中，模运算被广泛用于构造加密算法，例如Diffie-Hellman密钥交换协议和RSA算法中都用到了模运算。
通过使用同余关系，密码学家能够设计出具有强安全性的加密系统。
离散对数问题离散对数问题是指给定一个素数p，一个整数g（生成元）和一个整数y，求解整数x，使得g^x ≡ y (mod p)。
该问题在现代密码学中非常重要，例如在Diffie-Hellman密钥交换和ElGamal加密中均有应用。
与大数分解问题类似，离散对数问题在某些情况下也是计算上不可行的，因此为相应加密方法提供了安全保障。
代数结构及其在密码学中的应用代数结构主要涉及群、环和场等概念，这些结构为密码算法提供了基础。
群理论群是一个集合及其上的一种二元运算，满足封闭性、结合律、单位元和逆元等条件。
在密码学中，多种算法都依赖于特定群的性质。
例如，在椭圆曲线密码学（ECC）中，点的加法形成了一个阿贝尔群，该群具备良好的数学性质，使得基于其结构构建的加密算法既高效又安全。
环与域环是一种比群更为强壮的代数结构，它允许我们进行加法和乘法两种操作。
05_密码学基础(四)_公开密钥密码算法
密钥分配
使用对称密码算法 保密通信双方需共享密钥：A&B，B&C，C&A N个用户集需要N(N-1)/2个共享密钥 共享密钥需要经常更换，更换方式有
A选择密钥并手工传递给B 第三方C选择密钥分别手工传递给A,B 用A,B原有共享密钥传送新密钥 与A,B分别有共享密钥的第三方C传送新密钥给A和/ 或B
数论简介
欧拉定理 表述1： 将Z/(n）表示为 Zn，其中n=pq; p,q为素数且相异。 若Z*n={g∈ Zn|gcd(g,n)=1}，易见Z*n为(n)阶的乘 法群，且有 g(n)1(mod n)，而 (n)=(p-1)(q-1)。 表述2： 若整数g和n互素，则g(n) ≡1(mod n)；其中(n)为比 n小，但与n互素的正整数个数, 称为(n)的欧拉函数 表述3： 给定两个素数p和q，以及两个整数m、n，使得n=pq ，且0<m<n，对于任意整数k下列关系成立，
公钥密码学的历史
76年Diffie和Hellman发表了“密码学的新方向 ”，奠定了公钥密码学的基础 公钥技术是二十世纪最伟大的思想之一
改变了密钥分发的方式 可以广泛用于数字签名和身份认证服务
78年，RSA算法 PKI
公钥加密模型
公开密钥的加密
公开密钥密码的重要特性 加密与解密由不同的密钥完成 加密: X –>Y：Y = EKU(X) 解密: Y –>X: X = DKR(Y) = DKR(EKU(X)) 知道加密算法，从加密密钥得到解密密钥在计算上是 不可行的； 两个密钥中任何一个都可以用作加密而另一个用作解 密 X = DKR(EKU(X)) = EKU(DKR(X))
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
2021/3/10
讲解：XX
数论基础
第12页/共131页
►模运算
▪ 性质①的证明：
设 (a mod n) = ra，(b mod n) = rb，则存在整数 j、k 使得 a = jn+ra，b = kn+rb， 因此：
(a+b) mod n = [(j+k)n+ra+rb] mod n = (ra+rb) mod n = [(a mod n)+(b mod n)] mod n
▪ 例 1, 2, 3, 4, 6, 8, 12, 24 整除 24 ▪ 整除具有以下性质：
► 如果 a|1，那么a=±1 ► 如果 a|b 且 b|a，则a=±b ► 对任一 b (b≠0)，b|0 ► 如果 b|g，b|h，则对任意整数 m、n 有 b|(mg+nh)
2021/3/10
讲解：XX
记为 a≡b mod n。
►与 a 模 n 同余的数的全体称为 a 的同余类，记为[a]， 称 a 为这个同余类的表示元素。
►注意： 如果 a≡0 (mod n)，则n|a。
2021/3/10
讲解：XX
数论基础
第10页/共131页
►模运算
▪ 同余有以下性质：
① 若 n|(a-b)，则 a≡b mod n ② a≡b mod n，则 b≡a mod n ③ a≡b mod n 且 b≡c mod n，则 a≡c mod n
第14页/共131页
►模运算
▪ 例：设 Z8 = {0, 1, …,7}，考虑 Z8 上的模加法和模 乘法，结果如下表所示：
讲解：XX
数论基础
第8页/共131页
►素数与互素
▪ 如果 gcd(a, b) = 1，则称 a 和 b 互素 ▪ 整数 a, b 互素是指除 1 之外它们没有其它公因子，
例如：8 与15 互素
8 的因子：1, 2, 4, 8 15 的因子：1, 3, 5, 15 1 是 8 与15 唯一的公因子
2021/3/10
2021/3/10
讲解：XX
数论基础
第6页/共131页
►素数与互素
▪ 称 c 是两个整数 a、b 的最大公因子，当且仅当： ① c 是 a 的因子也是 b 的因子， 即 c 是 a、b 的公因子 ② a 和 b 的任一公因子，也是 c 的因子
▪ 表示为 c = gcd(a, b)
2021/3/10
▪ 性质②、③的证明类似。
（证毕）
2021/3/10
讲解：XX
数论基础
第13页/共131页
►模运算
▪ 例：设 Z8 = {0, 1, …, 7}，考虑 Z8 上的模加法和 模乘法，结果如下表所示：
+8 0 1 2 3 4 5 6 7 ×8 0 1 2 3 4 5 6 7 001234567 000000000
112345670 101234567
223456701 202460246
334567012 303614725
445670123 404040404
556701234 505274163
667012345 606420642
770123456 707654321
2021/3/10
讲解：XX
数论基础
▪ 如果将 a，b 都表示为素数的乘积，则 gcd(a, b) 极易确定。例如：300=22×31×52；18=21×32， 所以 gcd(18, 300) = 21×31×50 = 6
▪ 一般地，由 c = gcd(a, b)可得： 对每一素数p， cp = min(ap, bp)
2021/3/10
讲解：XX
数论基础
第7页/共131页
ቤተ መጻሕፍቲ ባይዱ
►素数与互素
▪ 由于最大公因子为正，所以 gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b)
一般地 gcd(a, b) = gcd(|a|, |b|)
▪ 由任一非 0 整数能整除 0，可得 gcd(a, 0) = |a|
▪ 从以上性质易知，同余类中的每一元素都可作为 这个同余类的表示元素。
2021/3/10
讲解：XX
数论基础
第11页/共131页
►模运算
▪ 求余数的操作 a mod n 将整数 a 映射到集合 {0, 1, …, n-1}，在这个集合上的算术运算称为 模运算，模运算有以下性质：
① [(a mod n)+(b mod n)] mod n = (a+b) mod n ② [(a mod n)-(b mod n)] mod n = (a-b) mod n ③ [(a mod n)×(b mod n)] mod n = (a×b) mod n
2021/3/10
讲解：XX
数论基础
第5页/共131页
►素数与互素
▪ 该性质称为整数分解的惟一性，也可如下陈述： 设 P 是所有素数集合，则任意整数 a (a>1) 都能 惟一地写成以下形式：
a pap pP
其中 ap≥0，等号右边的乘积项取所有的素数，然 而大多指数项 ap 为 0。 ▪ 相应地，任一正整数可由非 0 指数列表表示。 例如：11011可表示为{a7=1, a11=2, a13=1}。
第一部分 第四章 数论与有限域基础
张权 2012年秋季
2021/3/10
讲解：XX
1
►数论基础 ►群、环、域 ►有限域基础
本章提纲
第2页/共131页
2021/3/10
讲解：XX
数论基础
第3页/共131页
►素数与互素
▪ 对整数 b!=0 及 a，如果存在整数 m 使得 a=mb， 称 b 整除 a，也称 b 是 a 的因子，记作 b|a
数论基础
第4页/共131页
►素数与互素
▪ 称整数 p(p>1) 是素数，如果 p 的因子 只有±1，±p
▪ 任一整数 a(a>1) 都能惟一地表示为以下形式：
a
p p 1 2 12
p t t
其中 p1 > p2 > … > pt 是素数，αi >0(i=1,…,t)。 例如：91=7×13，11011=7×112×13
讲解：XX
数论基础
第9页/共131页
►模运算
▪ 设 n 是一正整数，a 是整数，如果用 n 除 a，得 商为 q，余数为 r，则
a qn r; 0 r n, q an ►其中 x为小于或等于 x 的最大整数。 ►用 a mod n 表示余数 r，则 a an n a mod n ►如果 (a mod n) = (b mod n)，则称 a 和 b (模 n) 同余，