信息安全数学基础第一阶段知识总结

信息安全数学基础第一阶段知识总结第一章整数得可除性一整除得概念与欧几里得除法1 整除得概念定义1 设a、b就是两个整数，其中b≠0如果存在一个整数q 使得等式a=bｑ成立，就称b整除a或者ａ被ｂ整除，记作b|a ,并把b 叫作a得因数,把a叫作b得倍数、这时，q也就是a得因数,我们常常将ｑ写成a/b或否则,就称b不能整除a或者a不能被b整除,记作a b、2整除得基本性质(1)当b遍历整数a得所有因数时,－b也遍历整数a得所有因数、（2)当ｂ遍历整数a得所有因数时,a/b也遍历整数a得所有因数、（3)设b，c都就是非零整数，(i）若b|a,则|b|｜|ａ|、(ｉｉ)若ｂ｜a,则ｂｃ|aｃ、(iii)若b|a,则1〈|b｜≤|ａ|、3整除得相关定理（1)设a,ｂ≠0,c≠０就是三个整数、若c｜b,b|a,则ｃ|a、(２)设a，b，c≠０就是三个整数,若ｃ|ａ,ｃ|b,则ｃ｜a±b(3）设a，b,c就是三个整数、若c｜a，ｃ|b则对任意整数s，t,有c|ｓa+tb、(４）若整数a１, …,aｎ都就是整数c≠0得倍数，则对任意n个整数s１,…,ｓｎ，整数就是c得倍数（5）设a，b都就是非零整数、若a|b,ｂ|a,则a=±b(6)设a,ｂ，c就是三个整数,且b≠0,c ≠0,如果(a , c）=1,则(ab , ｃ)＝（ｂ，c）(7) 设ａ，b , c就是三个整数,且ｃ≠0，如果c｜ａb，（a , ｃ）＝1, 则c｜b、（8）设ｐ就是素数，若ｐ|ab ,则p |a或p|b（9）设a1，…,a n就是n个整数，p就是素数,若ｐ｜a1…a n，则p一定整除某一个ａk二整数得表示主要掌握二进制、十进制、十六进制等得相互转化、三最大公因数与最小公倍数（一)最大公因数1．最大公因数得概念定义:设就是个整数,若使得 ,则称为得一个因数。

公因数中最大得一个称为得最大公因数。

记作、若，则称互素。

若,则称两两互素。

信息安全数学基础复习笔记
12.3复习笔记
第⼀章、整数的可除性
1.1 整数的概念、欧⼏⾥得除法
1.2 最⼤公因数与⼴义欧⼏⾥得除法
1.3 整除的进⼀步性质及最⼩公倍数
1.4 整数分解
1.5 素数的算术基本定理
第⼆章、同余
2.1 同余的概念及基本性质
2.2 剩余类及完全剩余系
2.3 简化剩余系与欧拉函数
2.4 欧拉定理、费马⼩定理、Wilson定理
2.5 模重复平⽅算法
12.5复习笔记
第三章、同余式
3.1 基本概念及⼀次同余式
3.2 中国剩余定理
3.3 ⾼次同余式的解法及解数
3.4 素数模的同余式
第四章、⼆次同余式与平⽅剩余4.1 ⼀般⼆次同余式
4.2 模为奇素数的平⽅剩余与平⽅剩余4.3 勒让得符号
4.4 ⼆次互反律
4.5 雅可⽐符号
第五章、原根与指标
5.1 指数及基本性质
5.2 原根
5.3 指标及n次同余式。

信息安全数学基础导言信息安全是在当前信息时代中广泛关注的一个重要领域。

它涉及到保护数据的机密性、完整性和可用性，以及防止未经授权的访问、修改或破坏数据的行为。

在信息安全领域，数学起着至关重要的作用。

数学提供了许多基础概念和技术，用于保护信息和数据。

本文将介绍信息安全的一些数学基础知识。

1. 整数论整数论是信息安全中不可或缺的一部分，其主要研究整数及其性质。

在信息安全中，整数论常用于加密算法和密钥生成。

其中，最常见的整数论问题是素数的应用。

素数是只能被1和自身整除的整数。

在信息安全中，素数被广泛应用于加密算法，如RSA算法。

RSA算法的基本原理是利用两个大素数的乘积作为公钥的模数，并求解其积的欧拉函数值。

因此，整数论中研究素数的性质和生成方法对于实现安全的RSA加密算法非常重要。

除了素数，整数论还涉及到很多其他概念和技术，如模运算、同余和剩余类等。

这些概念和技术在信息安全中的密码算法和密钥生成中起着至关重要的作用。

2. 离散数学离散数学是信息安全中的另一个重要基础。

离散数学研究的是离散结构，如集合、图论、布尔代数等。

在信息安全中，离散数学的概念和技术被广泛应用于密码学和网络安全。

密码学是关于信息加密和解密的科学，其中离散数学起着关键作用。

密码学使用离散数学的技术来设计和分析密码算法。

例如，离散数学的图论技术可以用于构建网络拓扑图，以评估网络的安全性。

布尔代数被广泛应用于逻辑门电路的设计和分析，用于实现对信息的逻辑操作和处理。

离散数学的另一个重要应用是在密码学中的离散对数问题。

离散对数问题是指已知一个数的底数和模数，求解指数的问题。

这个问题在公钥密码学中扮演着重要角色，如Diffie-Hellman密钥交换协议和椭圆曲线密码算法。

3. 概率论与统计学概率论和统计学是信息安全中的另一对重要基础。

它们被用于分析密码算法的安全性、测量信息系统的可靠性，并为风险评估和安全决策提供支持。

在密码学中，概率论和统计学的概念被广泛应用于对密码算法的攻击和破解。

《信息安全数学基础》课后作业及答案第1章课后作业答案 (2)第2章课后作业答案 (6)第3章课后作业答案 (13)第4章课后作业答案 (21)第5章课后作业答案 (24)第6章课后作业答案 (27)第7章课后作业答案 (33)第8章课后作业答案 (36)第9章课后作业答案 (40)第10章课后作业答案 (44)第11章课后作业答案 (46)第12章课后作业答案 (49)第13章课后作业答案 (52)第1章课后作业答案习题1：2, 3, 8(1), 11, 17, 21, 24, 25, 312. 证明：存在整数k，使得5 | 2k + 1，并尝试给出整数k的一般形式。

证明k = 2时，满足5 | 2k + 1。

5 | 2k + 1，当且仅当存2k + 1 = 5q。

k, q为整数。

即k = (5q– 1)/2。

只要q为奇数上式即成立，即q = 2t + 1，t为整数即，k = 5t + 2，t为整数。

3. 证明：3 3k + 2，其中k为整数。

证明因为3 | 3k，如果3 | 3k + 2，则得到3 | 2，矛盾。

所以，3 3k + 2。

8. 使用辗转相除法计算整数x, y，使得xa + yb = (a, b)：(1) (489, 357)。

解489 = 357×1 + 132,357 =132 × 2 + 93,132 = 93 × 1 + 39,93 = 39 × 2 + 15,39 = 15 × 2 + 9,15 = 9 × 1 + 6,9 = 6 × 1 + 3,6 = 3 × 2 + 0,所以，(489, 357) = 3。

132 = 489 – 357×1,93 = 357 – 132 × 2 = 357 – (489 – 357×1) × 2 = 3 × 357 – 2 ×489,39 = 132 – 93 × 1 = (489 – 357×1) – (3 × 357 – 2 ×489) × 1 = 3 ×489 – 4× 357,15 = 93 – 39 × 2 = (3 × 357 – 2 × 489) – (3 ×489 – 4× 357) × 2 = 11× 357 – 8 × 489,9 = 39 – 15 × 2 = (3 ×489 – 4× 357) – (11× 357 – 8 × 489) × 2 = 19 × 489 – 26× 357,6 = 15 – 9 × 1 = (11× 357 –8 × 489) – (19 × 489 – 26× 357) = 37 ×357 – 27 × 489,3 = 9 – 6 × 1 = (19 × 489 – 26× 357) – (37 × 357 – 27 × 489) = 46 ×489 – 63 × 357。

信息安全数学基础第一阶段知识总结第一章 整数的可除性一 整除的概念和欧几里得除法 整除的概念定义 设♋、♌是两个整数，其中♌≠ 如果存在一个整数 ❑ 使得等式 ♋♌❑ 成立，就称♌整除♋或者♋被♌整除，记作♌♋ ，并把♌叫作♋的因数，把♋叫作♌的倍数 这时，❑也是♋的因数，我们常常将❑写成♋／♌或 否则，就称♌不能整除♋或者♋不能被♌整除，记作♋ ♌整除的基本性质☎✆当♌遍历整数♋的所有因数时， ♌也遍历整数♋的所有因数☎✆当♌遍历整数♋的所有因数时，♋♌也遍历整数♋的所有因数☎✆设♌，♍都是非零整数，☎♓✆若♌♋，则 ♌♋ ☎♓♓✆若♌♋，则♌♍♋♍☎♓♓♓✆若♌♋，则 ♌≤ ♋ 整除的相关定理☎✆ 设♋，♌≠ ，♍≠ 是三个整数 若♍♌，♌♋，ab则♍♋☎✆ 设♋，♌，♍≠ 是三个整数，若♍♋，♍♌，则♍♋±♌☎✆ 设♋，♌，♍是三个整数 若♍♋，♍♌则对任意整数♦，♦，有♍♦♋♦♌☎✆ 若整数♋  ⑤♋⏹都是整数♍≠ 的倍数，则对任意⏹个整数♦，⑤，♦⏹，整数是♍的倍数☎✆ 设♋，♌都是非零整数 若♋♌，♌♋，则♋±♌ ☎✆ 设♋ ♌  ♍是三个整数，且♌≠ ，♍ ≠ ，如果☎♋  ♍✆则 ☎♋♌  ♍✆☎♌  ♍✆☎✆ 设♋  ♌  ♍是三个整数，且♍≠ ，如果♍｜♋♌  ☎♋  ♍✆   则♍  ♌☎✆ 设☐ 是素数，若☐ ♋♌  则☐ ♋或☐♌☎✆ 设♋  ⑤♋⏹是⏹个整数，☐是素数，若☐ ♋ ⑤♋⏹ 则☐一定整除某一个♋ 二 整数的表示主要掌握二进制、十进制、十六进制等的相互转化 三 最大公因数和最小公倍数 ☎一✆最大公因数 ．最大公因数的概念nn a s a s ++ 11定义：设是个整数，若使得 ，则称为的一个因数．公因数中最大的一个称为的最大公因数．记作若 则称 互素．若 则称两两互素．思考： ．由两两互素，能否导出．由 能否导出两两互素？．最大公因数的存在性☎✆若 不全为零，则最大公因数存在并且☎✆若全为零，则任何整数都是它的公因数．这时，它们没有最大公因数．．求两个正整数的最大公因数．定理 ：设任意三个不全为零的整数，且 则辗转相除法由带余除法 得☎✆⑤⑤因为每进行一次带余除法，余数至少减少 ，且是有限整数，故经过有限次带余除法后，总可以得到一个余数是零的情况，即由☎✆知，定理 ：任意两个正整数 则是☎✆中最后一个不等于零的余数．定理 ：任意两个正整数的任意公因数都是的因数． ．性质定理 ：任意两个正整数，则存在整数，使得成立定理 ：设是不全为零的整数．☎♓✆若则☎♓♓✆若则☎♓♓♓✆若是任意整数，则从上面定理我们很容易得到下面几个常用结论：♊♋ 且♌♍．求两个以上正整数的最大公因数设则有下面的定理：定理 ：若 是个正整数，则只需证♊是的一个公因数．♋ 是的公因数中最大一个例 求解：．求两个正整数的最大公因数的线性组合（重点掌握）方法一 运用辗转相除法求最大公因数的逆过程；方法二 补充的方法方法三 运用列表法求解☎二✆ 最小公倍数．最小公倍数的定义定义： 是 个整数，如果对于整数，有那么叫做的一个公倍数．在 的一切公倍数中最小一个正整数，叫做最小公倍数．记作 ．．最小公倍数的性质．定理 ：设是任给的两个正整数，则☎♓✆的所有公倍数都是的倍数．☎♓♓✆定理 ：设正整数是的一个公倍数，则．求两个以上整数的最小公倍数定理 ：设是个正整数 若则只需证：♊是 的一个公倍数，即♋设是的任一公倍数 则例 求解：又四 素数 算术基本定理．素数、合数的概念定义：一个大于 的整数，如果它的正因数只有 和它的本身，我们就称它为素数，否则就称为合数．．性质定理 ：设是大于 的整数，则至少有一个素因数，并且当是合数时，若是它大于 的最小正因数，则p ，都有定理 设⏹是一个正整数，如果对所有地素数n☐ ⏹则⏹一定是素数求素数的基本方法：爱拉托斯散筛法。

信息安全的数学基础
信息安全的数学基础可以总结为以下几个方面：
1. 密码学：涉及到各种加密算法和解密算法，主要是数论、代
数和概率论方面的知识。

对称加密算法（如DES、AES等）和非对称加
密算法（如RSA、ECC等）都是基于数学原理的。

2. 数字签名：数字签名是数字证书体系的基础。

数字签名涉及
到哈希函数、公钥密码体制等数学算法，这些算法在数字认证、电子
邮件、电子商务等领域得到广泛应用。

3. 随机数生成：随机数生成是很多加密算法中不可或缺的功能。

在信息安全中，随机数的产生要具有不可预测性，这可以通过伪随机
序列算法和真随机序列算法来实现。

其中，真随机序列算法主要依赖
于物理随机事件的产生，如收音机收音噪声和光学噪声等，这也需要
数学中的统计学和概率论知识。

4. 数字证书：数字证书是数字身份证明的一种方式，它包括了
某个实体的公钥以及相关的信息，可以用于数字证明的验证。

数字证
书一般采用了基于数学算法的公钥密码体制，如RSA和ECC等。

此外，数字证书的设计和实现还要涉及证书格式、证书吊销等方面的数学知识。

总之，信息安全中的数学基础是十分广泛和深奥的，需要掌握多
种数学知识才能确保信息安全。

第一章参考答案（1）5,4,1,5.（2）100=22*52, 3288=23*3*137.（4）a,b可以表示成多个素因子的乘积a=p1p2––p r, b=q1q2––q s,又因为(a, b)=1，表明a, b没有公共(相同)素因子. 同样可以将a n, b n表示为多个素因子相乘a n=(p1p2––p r)n, b n=(q1q2––q s)n明显a n, b n也没有公共(相同)素因子.（5）同样将a, b可以表示成多个素因子的乘积a=p1p2––p r, b=q1q2––q s,a n=(p1p2––p r)n,b n=(q1q2––q s)n,因为a n| b n所以对任意的i有, p i的n次方| b n, 所以b n中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b. （6）因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p1p2––p r, b=q1q2––q s, ab=p1p2––p r q1q2––q s, 又因为a, b, c互素, 所以a, b, c中没有公共(相同)素因子, 明显ab和c也没有公共(相同)素因子.所以(ab, c)= (a, b)(a, c).（7）2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107, 109, 113, 127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199. （11）对两式进行变形有21=0(mod m), 1001=0(mod m),可以看出要求满足的m 即使求21和1001的公约数, 为7和1.（12）(70!)/(61!)= 62*63*––*70=(-9)*(-8)*––*(-1)=-9!=-362880=1(mod 71). 明显61!与71互素, 所以两边同乘以61!, 所以70!=61!(mod 71).（13）当n为奇数时2n=(-1)n=-1=2(mod 3), 两边同时加上1有2n+1=0(mod 3), 所以结论成立.当n为偶数时2n=(-1)n=1(mod 3), 两边同时加上1有2n+1=2(mod 3), 所以结论成立.（14）第一个问：因为(c,m)=d, m/d为整数.假设ac=k1m+r, bc=k2m+r,有ac=k1d(m/d)+r, bc=k2d(m/d)+r所以ac=bc(mod m/d),因为(c,m/d)=1,所以两边可以同除以一个c, 所以结论成立.第二个问题：因为a=b(mod m), 所以a-b=k i*m i，a-b是任意m i的倍数，所以a-b是m i公倍数，所以[m i]|a-b.(利用式子：最小公倍数=每个数的乘积/最大公约数, 是错误的, 该式子在两个数时才成立)（15）将整数每位数的值相加, 和能被3整除则整数能被3整除, 和能被9整除则整数能被9整除, (1)能被3整除, 不能被9整除，(2)都不能，(3)都不能，(4)都不能第二章答案（5）证明：显然在群中单位元e满足方程x2=x, 假设存在一个元素a满足方程x2=x, 则有a2=a, 两边同乘以a-1有a=e. 所以在群中只有单位元满足方程x2=x. （6）证明：因为群G中每个元素都满足方程x2=e, 所以对群中任意元素a,b 有aa=e, bb=e, (ab)2=abab=e. 对abab=e, 方程两边左乘以a, 右乘以b有aababb=(aa)ba(bb)=ba=aeb=ab, 有ab=ba, 所以G是交换群.（7）证明：充分性：因为在群中对任意元素a,b有(ab)2=a2b2即abab=aabb, 方程两边左乘以a的逆元右乘以b的逆元, 有a-1ababb-1= a-1aabbb-1, 有ab=ba, 所以G是交换群.必要性：因为群G是交换群, 所以对任意元素a,b有ab=ba, 方程两边左乘以a右乘以b有abab=aabb, 有(ab)2=a2b2.（8）证明：因为xaaba=xbc，所以x-1xaxbaa-1b-1=x-1xbca-1b-1，所以存在唯一解x=a-1bca-1b-1使得方程成立。