信息安全数学基本第一阶段知识归纳

信息安全数学基础第一阶段知识总结第一章整数得可除性一整除得概念与欧几里得除法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．最大公因数得概念定义:设就是个整数,若使得 ,则称为得一个因数。

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

记作、若，则称互素。

若,则称两两互素。

信息安全数学基础一、说明（一）课程性质本课程是继《高等数学》、《线性代数》课之后，为信息与计算科学专业计算方向开设的一门数学基础理论课程。

本课程主要介绍用算术的方法研究整数性质以及近世代数中群与群结构、环论和有限域等内容。

（二）教学目的通过本课程的学习，使学生能熟练掌握用算术的方法研究整数性质以及近世代数中群与群结构、环论和有限域等内容，并且能够掌握如何应用信息安全数学基础中的理论和方法来分析研究信息安全中的实际问题，从而为学习密码学、网络安全、信息安全等打下坚实的基础。

（二）教学内容正确理解并掌握整数的整除概念及性质，带余除法，欧几里得除法，同余及基本性质，欧拉函数和欧拉定理。

一次同余式和二次同余式的解法，平方剩余与平方非剩余，指数及基本性质。

了解群环域等基本概念。

要求基本会用数论知识解决某些代数编码问题。

要求基本会用所学知识解决某些代数编码以及密码学问题。

（三）教学时数54学时（四）教学方式课堂讲授为主。

二、本文第一章整数的可除性教学要点：1. 整除的概念及欧几里得除法2. 算术基本定理教学内容：§1 整除概念和带余除法§2 最大公因式与欧几里得除法§3 整除的性质及最小公倍数§4 素数和算术基本定理§5 素数定理教学时数 6 学时考核要求：1.熟练掌握整除概念及性质，掌握带余除法。

2.理解欧几里得除法，会求最大公因数和最小公倍数。

3.理解素数概念和算术基本定理。

第二章同余教学要点：1.同余及基本性质，2.剩余类及完全剩余系的概念和性质3.欧拉函数和欧拉定理教学内容：§1 同余概念及其基本性质§2 剩余类及完全剩余系§3 简化剩余系与欧拉函数§4 欧拉定理与费尔马定理§5 模重复平方计算法教学时数 6 学时考核要求:1．理解同余概念，掌握其基本性质2．理解剩余类及完全剩余系，了解简化剩余系，熟悉欧拉函数3．掌握欧拉定理和费尔马定理4．掌握模重复平方计算法第三章同余式教学要点：一次同余式和二次同余式的解法，中国剩余定理教学内容：§1 基本概念及一次同余式§2 中国剩余定理§3 高次同余式的解数及解法§4 素数模的同余式教学时数 6 学时考核要求:1. 理解同余式概念，会熟练求解一次同余式2. 理解中国剩余定理第四章二次同余式与平方剩余教学要点：1.平方剩余与平方非剩余，2.勒让德符号和雅可比符号3.合数模教学内容：§1 一般二次同余式§2 模为奇素数的平方剩余与平方非剩余§3 勒让德符号§4 二次互反律§5 雅可比符号§6 模p平方根§7 合数模§8 素数的平方表示教学时数 8学时考核要求:1.熟悉高次同余式的解法2.理解素数模的同余式和一般二次同余式3.理解模为奇素数的平方剩余与平方非剩余4.掌握勒让德符号和雅可比符号5.掌握二次互反律6.理解合数模的二次同余式及其解法第五章原根与指标教学要点：1.指数及其基本性质2.原根存在的条件以及原根求解教学内容：§1 指数及其基本性质§2 原根存在的条件§3 指标及n次剩余教学时数 6 学时考核要求:1.掌握指数及基本性质2.理解原根存在的条件，理解指标和n次剩余概念第六章群教学要点：1.陪集、正规子群和商群的概念2.同态、同构的概念教学内容：§1 群的基本概念§2 循环群§3 陪集和Lagrange定理§4 正规子群和商群教学时数 8学时考核要求:1.掌握群理论与同余理论之间的关系2.熟练群、循环群、同态、同构的概念第七章环和域教学要点：1．环和域的基本概念以及与同态、同构的概念2．理想、商环和多项式环教学内容：§1 环和域的基本概念§2 理想和商环§3 多项式环教学时数 6 学时考核要求:掌握环和域的基本概念以及与同态、同构的概念，理想、商环和多项式环的概念第八章有限域教学要点：1．有限域的概念2．有限域上的多项式教学内容：§1 域的有限扩张§2 有限域的性质§3 有限域的表示§4 有限域上的多项式教学时数 6 学时考核要求:1.掌握有限域的基本概念及定理2.掌握域的扩张的概念3.掌握有限域上多项式的性质三、参考书[1] 信息安全数学基础。

第一章（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使得方程成立。

信息安全基础知识信息安全基础知识1. 了解信息安全基本概念信息安全是指信息网络的硬件、软件及其系统中的数据受到保护，不受偶然的或者恶意的原因而遭到破坏、更改、泄露，系统连续可靠正常地运行，信息服务不中断。

信息安全是一门涉及计算机科学、网络技术、通信技术、密码技术、信息安全技术、应用数学、数论、信息论等多种学科的综合性学科。

2. 了解网络安全主要概念及意义网络的安全是指通过采用各种技术和管理措施，使网络系统正常运行，从而确保网络数据的可用性、完整性和保密性。

网络安全的具体含义会随着“角度”的变化而变化。

比如：从用户（个人、企业等）的角度来说，他们希望涉及个人隐私或商业利益的信息在网络上传输时受到机密性、完整性和真实性的保护。

网络安全是一个关系国家安全和主权、社会的稳定、民族文化的继承和发扬的重要问题。

其重要性，正随着全球信息化步伐的加快而变到越来越重要。

“家门就是国门”，安全问题刻不容缓。

3.了解安全隐患的产生原因、类型区别（被动攻击，主动攻击等）产生安全隐患的产生原因:1.网络通信协议的不安全2.计算机病毒的入侵3.黑客的攻击4操作系统和应用软件的安全漏洞5.防火墙自身带来的安全漏洞分类：分为主动攻击和被动攻击主动攻击包含攻击者访问他所需信息的故意行为。

比如远程登录到指定机器的端口25找出公司运行的邮件服务器的信息；伪造无效IP 地址去连接服务器，使接受到错误IP地址的系统浪费时间去连接哪个非法地址。

攻击者是在主动地做一些不利于你或你的公司系统的事情。

正因为如此，如果要寻找他们是很容易发现的。

主动攻击包括拒绝服务攻击、信息篡改、资源使用、欺骗等攻击方法。

被动攻击主要是收集信息而不是进行访问，数据的合法用户对这种活动一点也不会觉察到。

被动攻击包括嗅探、信息收集等攻击方法。

从攻击的目的来看，可以有拒绝服务攻击(Dos)、获取系统权限的攻击、获取敏感信息的攻击；从攻击的切入点来看，有缓冲区溢出攻击、系统设置漏洞的攻击等；从攻击的纵向实施过程来看，又有获取初级权限攻击、提升最高权限的攻击、后门攻击、跳板攻击等；从攻击的类型来看，包括对各种操作系统的攻击、对网络设备的攻击、对特定应用系统的攻击等4.了解安全分类（技术缺陷，配置缺陷，策略缺陷，人为缺陷等）技术缺陷：现有的各种网络安全技术都是针对网络安全问题的某一个或几个方面来设计的，它只能相应地在一定程度上解决这一个或几个方面的网络安全问题，无法防范和解决其他的问题，更不可能提供对整个网络的系统、有效的保护。

信息安全数学基础习题集一信息安全数学基础----习题集一一、填空题1、设a=18、b=12，c=27，求a、b、c的最小公倍数[a,b,c]= .2、求欧拉函数φ(3000)= .3、设m=9，则模m的最小非负简化剩余系={ }.4、设m=11，则模m的所有平方剩余= .5、设m=22，则模m的所有原根个数= .6. 设m，n是互素的两个正整数，则φ(mn)=________________。

7. 设m是正整数，a是满足m?a的整数，则一次同余式：ax≡b (mod m)有解的充分必要条件是_________________ 。

8. 设 m 是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m ，使得aa’≡1 (mod m)。

9. 设a∈Z,(a,m)=1, 如果同余方程x2≡a(mod m)__________, 则a 叫做模m的平方剩余.10. 设a,m∈Z,m>1,(a,m)=1, 则使得a e≡1(mo d m)成立的最小正整数e叫做a 对模m的__________.二、判断题（在题目后面的括号中，对的画“√”，错的画“×”）1、若k是任意正整数, 则(ak,bk)=(a,b). （）2、设a1,a2,…,a n是n个不全为零的整数，则a1,a2,…,a n与a1, |a2|, |a3|,…, |a n|的公因数相同（）3、设m是正整数, 若m│ab, 则m│a或m│b. （）4、设m为正整数, a,b为整数, a≡b(mod m), d│b且d>0, 则ad ≡bd(mod md).（）5、{1,-3,8,4,-10}是模5的一个完全剩余系. （）6、设m是素数, 模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等. （）7、设p=17为奇素数, 模p的平方剩余和平方非剩余的数量各为8. （）8、一次同余方程9x≡1(mod 24)有解. （）9、设p是素数, g是模p的原根, 若g x≡1(mod p), 则x是p?1的整数倍.（）10、设m>1,(a,m)=1, 则1=a0,a,a2, …, a ord m(a)?1构成模m 的简化剩余系.（）11. b≠0, 则(0,b)＝|b|. （）12. 设a,b是两个互素正整数, 那么a│m,b│m, 则ab│m. （）13. 设m是一个正整数, a,b,d都不为0，若ad≡bd(modm)。

《信息安全数学基础》课后作业及答案第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。

信息安全数学基础习题集一信息安全数学基础----习题集一一、填空题1、设a=18、b=12，c=27，求a、b、c的最小公倍数[a,b,c]= .2、求欧拉函数φ(3000)= .3、设m=9，则模m的最小非负简化剩余系={ }.4、设m=11，则模m的所有平方剩余= .5、设m=22，则模m的所有原根个数= .6. 设m，n是互素的两个正整数，则φ(mn)=________________。

7. 设m是正整数，a是满足 m∤a的整数，则一次同余式：ax≡b (mod m)有解的充分必要条件是_________________ 。

8. 设 m 是一个正整数，a是满足____________的整数，则存在整数a’，1≤a’＜m ，使得aa’≡1 (mod m)。

9. 设a∈Z,(a,m)=1, 如果同余方程x2≡a(mod m)__________, 则a 叫做模m的平方剩余.10. 设a,m∈Z,m>1,(a,m)=1, 则使得a e≡1(mod m)成立的最小正整数e叫做a对模m的__________.二、判断题（在题目后面的括号中，对的画“√”，错的画“×”）1、若k是任意正整数, 则(ak,bk)=(a,b). （）2、设a1,a2,…,a n是n个不全为零的整数，则a1,a2,…,a n与a1, |a2|, |a3|,…, |a n|的公因数相同（）3、设m是正整数, 若m│ab, 则m│a或m│b. （）4、设m为正整数, a,b为整数, a≡b(mod m), d│b且d>0, 则ad≡b d (mod md). （）5、{1,-3,8,4,-10}是模5的一个完全剩余系. （）6、设m是素数, 模m的最小非负完全剩余系和最小非负简化剩余系中元素个数相等. （ ）7、设p =17为奇素数, 模p 的平方剩余和平方非剩余的数量各为8.（ ） 8、一次同余方程9x ≡1(mod 24)有解. （ ）9、设p 是素数, g 是模p 的原根, 若g x ≡1(mod p), 则x 是p −1的整数倍.（）10、设m >1,(a,m)=1, 则1=a 0,a,a 2, …, a ord m (a )−1构成模m 的简化剩余系. （ ）11. b ≠0, 则(0,b)＝|b|. （ ）12. 设a,b 是两个互素正整数, 那么a│m,b│m , 则 ab│m . （ ）13. 设m 是一个正整数, a,b,d 都不为0，若ad ≡bd(modm)。

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

《信息安全数学基础》课程教学大纲课程性质：学科基础课课程代码：学时：72（讲课学时：72实验学时：0课内实践学时: 0）学分：4.5适用专业：通信工程一、课程教学基本要求《信息安全数学基础》是通信工程专业教学计划中的一门学科基础课，通过对本课程的学习，可以使学生系统地掌握本学科的数学基础，使得学生能够初步掌握和运用数学理论来分析和研究一些问题。

二、课程教学大纲说明信息安全学科是一门新兴的学科．它涉及通信学、计算机科学、信息学和数学等多个学科。

为了使学生系统的掌握信息安全理论基础和实际知识，需要专门开课讲授与信息安全相关的数学知识，特别是关于初等数论知识。

通过本课程的学习，使学生掌握信息安全学科涉及的数学基本概念、基本原理和实际应用，建立数学体系的完整概念，为后续专业课程的学习奠定基础。

本课程的教学内容主要以理论为主，介绍了整数的可除性、同余理论以及有关原根与指标等知识。

学好本课程内容的前提条件：高等数学和线性代数的基础知识。

教学方法与手段：本课程采用课堂理论教学为主要教学方法，习题课和批改作业为检查措施，期末笔试考试为检查手段，以确保本课程的教学质量。

三、各章教学结构及具体要求（一）第一章整数的可除性1.教学目的和要求。

通过对本章的学习，使学生加深对整数的性质、狭义和广义欧几里得除法和算术基本定理的了解，更深入地理解初等数论与现代密码学的关系。

2.教学内容和要点。

共讲授六个方面的内容：（1）整除的概念、欧几里得除法；（2）整数的表示（3）最大公因数与广义欧几里得除法（4）整除的进一步性质及最小公倍数（5）素数、算术基本定理（6）素数定理。

（二）第二章同余1. 教学目的和要求。

通过对本章的学习，使学生了解同余、剩余类和简化剩余类的概念，熟悉欧拉定理、费马小定理。

2.教学内容和要点。

共讲授五个知识点的内容：（1）同余的概念及基本性质（2）剩余类及完全剩余系（3）简化剩余系与欧拉函数（4）欧拉定理费马小定理（5）模重复平方计算法。

信息安全数学基础习题答案信息安全数学基础习题答案第⼀章整数的可除性1．证明：因为2|n 所以n=2k , k∈Z5|n 所以5|2k ，⼜（5，2）=1，所以5|k 即k=5 k1，k1∈Z7|n 所以7|2*5 k1 ,⼜（7，10）=1，所以7| k1即k1=7 k2，k2∈Z 所以n=2*5*7 k2即n=70 k2, k2∈Z 因此70|n2．证明：因为a3-a=(a-1)a(a+1)当a=3k，k∈Z 3|a 则3|a3-a当a=3k-1，k∈Z 3|a+1 则3|a3-a当a=3k+1，k∈Z 3|a-1 则3|a3-a所以a3-a能被3整除。

3．证明：任意奇整数可表⽰为2 k0+1，k0∈Z（2 k0+1）2＝4 k02+4 k0+1=4 k0 (k0+1)+1由于k0与k0+1为两连续整数，必有⼀个为偶数，所以k0 (k0+1)=2k所以（2 k0+1）2=8k+1 得证。

4．证明：设三个连续整数为a-1,a,a+1 则(a-1)a(a+1)= a3-a由第⼆题结论3|（a3-a）即3|(a-1)a(a+1)⼜三个连续整数中必有⾄少⼀个为偶数，则2|(a-1)a(a+1)⼜（3，2）=1 所以6|(a-1)a(a+1) 得证。

5．证明：构造下列k个连续正整数列：(k+1)！+2, (k+1)！+3, (k+1)！+4,……, (k+1)！+(k+1), k∈Z对数列中任⼀数 (k+1)！+i=i[(k+1)k…(i+1)(i-1)…2*1+1], i=2,3,4,…(k+1)所以i|(k+1)！+i 即(k+1)！+i为合数所以此k个连续正整数都是合数。

6．证明：因为1911/2＜14 ,⼩于14的素数有2，3，5，7，11，13经验算都不能整除191 所以191为素数。

因为5471/2＜24 ,⼩于24的素数有2，3，5，7，11，13，17，19，23经验算都不能整除547 所以547为素数。