信息安全数学基础教案(禹勇)

教 师 教 案( 20092010 学年第 一 学期 )课 程 名 称：信息安全数学基础授 课 学 时：40学时授 课 班 级：信息安全专业，60班任 课 教 师：禹勇教 师 职 称：讲师教师所在学院：计算机科学与工程学院电子科技大学课程名称信息安全数学基础授课专业班级 年级大二课程编号修课人数78课程类型必修课普通教育课程( )；学科基础课 (* ) ； 专业方向课 ( )选修课公选课 ( )；学科基础选修课 ( ) ； 专业选修 () 授课方式理论课 (* ) ；实践课 ()考核方式考 试 ( * )考 查 ( )是否采用多媒体是是否采用双语否学时分配课堂讲授 40 学时； 实践课 0 学时名称作者出版社及出版时间教材信息安全数学基础许春香电子科技大学出版社2008参考书目信息安全数学基础信息安全数学基础谢敏覃中平等西安电子科技大学出版社 2006清华大学出版社 2006授课时间2009.9-2010.1第一章 整除与同余授课时数：6一、 教学内容及要求1. 整除的概念及欧几里得除法，理解2. 整数的表示，理解3. 最大公因数及广义欧几里得除法，掌握4. 整除的进一步性质及最小公倍式，掌握5. 素数和算术基本定理，掌握6. 同余的概念，掌握二、 教学重点与难点本章的内容较多，难点较少，教学重点在于以下方面：1. 欧几里得除法和广义欧几里得除法。2. 最大公因数和最小公倍数。3. 整数的标准分解式。4. 同余的概念三、 内容的深化和拓宽在内容的深化和拓宽方面，介绍如何运用欧几里得除法求整数的二进制、十进制和十六进制，使学生对欧几里得除法有更深的理解。四、 教学方式（手段）及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2. 讲述证明整除方面的定理的常用方法。3. 通过举例阐述重要定理的内容和含义。五、 作业1. 证明：若2|n, 5|n, 7|n,那么70|n。2. 证明：如果a是整数，则a3-a被3整除。3. 证明：每个奇整数的平方具有形式8k+1。4. 证明：任意三个连续整数的乘积都被6整除。5. 证明：对于任给的正整数k，必有k个连续正整数都是合数。6. 证明：191，547都是素数，737，747都是合数。7. 利用爱拉托斯筛法求出500以内的全部素数。8. 求如下整数对的最大公因数：(1) (55, 85) (2) (202, 282)9. 求如下整数对的最大公因数：(1) (2t+1, 2t-1) (2) (2n, 2(n+1)10. 运用广义欧几里得除法求整数s, t，使得sa+tb=(a,b)。(1) 1613, 3589 (2)2947, 377211. 证明:若(a,4)=2，(b,4)=2，则(a+b,4)=4。 12. 求出下列各对数的最小公倍数。(1) 8, 6013. 求出下列各对数的最大公因数和最小公倍数(1) 11001, 11000六、 本章参考资料1. 信息安全数学基础，李继国等，武汉大学出版社，2006年。2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。七、 教学后记第二章 群授课时数：6一、 教学内容及要求1. 群的概念及基本性质，掌握2. 子群的概念与判定，掌握3. 群的同态和同构，掌握4. 变换群，掌握5. 置换群，掌握二、 教学重点与难点本章教学重点为群、子群、群同态、同构和变换群与置换群等的定义，子群的判定、群同态和同构以及同态核；本章教学难点为群、子群和同态的定义。三、 内容的深化和拓宽在内容的深化和拓宽方面，引入公钥密码学，说明群理论在公钥密码学中的重要应用。四、 教学方式（手段）及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2. 通过实际的例子来解释群、子群、变换群和置换群的定义。3. 举例说明解释群同构与同态的区别和联系。五、 作业1下面各集合对相应定义的运算“”，哪些构成群？哪些不构成群？并说明理由：1）实数集R，对运算ab = 2(a+b)；2）G = 1，-1，对数的普通乘法；3）非零实数集R*，对运算ab = 2ab；4）非零实数集R*，对运算ab = |ab|；5）所有实数对集合(a，b) | a，bR，对运算(a，b) (c，d) = (a+c，b-d)；6）整数集Z，对运算ab = a+b-1；7）G| a，b为实数且a2+b20，对矩阵的普通乘法；8）非空集合M的所有子集的集合P(M)，对运算AB = AB，(A，BM)；9）上述集合P(M)，对运算AB = AB，(A，BM)；10）G = pmqn | m，nZ，其中p，q是两个固定的不同素数，对数的普通乘法2全体整数的集合Z对于普通减法是否是一个群？3完成2.1例6的验证4对于集合A = a1，a2，可以建立如下的乘法表表中aij = aiaj乘法表可以方便地判断一个集合是否是群1）建立通过乘法表判断是否群或交换群的规则（提示：如果表中aij = aji，则交换律满足）a1a2aja1a11a12a1ja2a21a22a2jaiai1ai2aij2）通过上面建立的规则判断G是否是群，如果是群，是否是交换群G = e，a，b，其乘法表如下：eabeeabaabebbea5证明：在群中只有单位元满足方程x2 = x6如果群G中的每一个元都满足方程x2 = e，那么G是交换群7设G是一个群，证明G是交换群的充分必要条件是，对于G任意元素a，b都有(ab) 2 = a2b28设G是一个群，a，b，c是G中任意三个元素，证明：方程xaxba = xbc在G中有且仅有一解9证明：如果a，b是群中的任意元素，则(ab) 1 = b-1a-110证明：在任意群中，下列各组中的元素有相同的阶：1）a与a-1；2）a与cac-1；3）ab与ba；4）abc，bca，cab11设G是n阶有限群证明对于任意元aG，都有an = e12详细验证2.2例113证明：群G的两个子群的交集也是G的子群14证明f(ab) = f(a)f(b)将一个群映射成另一个群15证明群的同构是等价关系16证明：群G为一交换群当且仅当aa-1是一同构映射17证明：一个变换群的单位元一定是恒等变换18构造与整数加法群Z同构的变换群19M = R0，1即M是除去0，1以外的全体实数的集合，G是M的以下6个变换的集合：，证明G是一个变换群20R是实数集合证明：R上的所以如下变换xax+b，a，b是有理数，a0是一个变换群这个群是不是交换群？21参考题4，建立三次对称群S3的乘法表从乘法表观察S3是否阿贝尔群22求出三次对称群S3的所有子群 23把三次对称群S3的所有元素写成不相交的循环乘积24证明2.4定理425设G = 1，e，e2，其中e = 证明G与三次对称群S3的一个子群同构26设计26个英文字母的一个置换，用这个置换对一段文字进行加密，并观察加密后的密文（置换是应用了上千年的基本密码技术这里置换表称为密钥）27把置换(456)(567)(671)(123)(234)(345)写为不相交循环乘积 28设t = (327)(26)(14)，s = (134)(57)求sts-1 和s-1ts 28将题26的置换用不相交的循环乘积表示29将上题中的每个循环用对换的乘积表示30证明：对于K循环d，有dk = I（I恒等变换）31证明K循环满足：(i1 i2ik) -1 = (ik ik-1i1)32求交错群A433证明n次对称群Sn有阶1!，2!，3!，n!的子群六、 本章参考资料1. 信息安全数学基础，谢敏等，西安电子科技大学出版社，2006年。2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。七、 教学后记第三章 循环群、群的结构授课时数：6一、 教学内容及要求1. 循环群的概念，掌握2. 欧拉函数的定义与相关计算，掌握3. 剩余类群的概念，理解4. 子群的陪集，掌握5. 正规子群与商群，掌握二、 教学重点与难点本章教学重点为循环群的概念与应用、循环群的性质、剩余类群及其性质和正规子群的判定；本章教学难点拉格朗日定理、正规子群的判定和性质。三、 内容的深化和拓宽在内容的深化和拓宽方面，重点引入基于循环群建立的公钥密码算法，让学生深刻掌握循环群在公钥密码算法中的重要地位。四、 教学方式（手段）及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2. 通过实际的例子来讲解循环群、正规子群和商群。五、 作业1在G到G的一个同态映射之下：aa，a和a的阶是否一定相同？2证明：1）在一个有限群里阶大于2的元的个数一定是偶数 2）假设G是一个阶为偶数的有限群，则G中阶为2的元素个数一定为奇数3求三次对称群S3的所有元素的阶4求出三次对称群S3的所有元素生成的循环子群 5假设a生成一个阶为n的循环群G证明：如果(m，n) = 1（即m与n互素），am也生成G6假设G是循环群，并且G与G同态证明G也是循环群7假设G是无限阶循环群，G是任意循环群证明G与G同态(提示：将G分为无限循环群和有限循环群分别证明)8分别求出13，16阶循环群各个元素的阶，指出其中的生成元9分别求15，20阶循环群的真子群10参考第2章题4，建立模8剩余类群的运算表11证明：设p是一个素数，任意两个p阶群都同构12证明：设p是一个素数，则阶是pm的群一定有一个阶为p的子群 13a，b是一个群G的元素，并且ab = ba，又假设a的阶为m，b的阶为n，且(m，n) = 1，证明ab的阶是mn 14四次对称群S4的一个4阶子群如下：H = (1)，(12)(34)，(13)(24)，(14)(23)求出H的全部左陪集 15证明：两个正规子群的交还是正规子群16证明：指数是2的子群一定是正规子群17假设H是G的子群，N是G的正规子群，证明HN是G的子群18基于加法和加法群对第2章和本章内容进行归纳总结加法群中的单位元用0表示，元素a的逆元用-a表示（通过该练习可以加深巩固对群论的熟悉和理解，建议初学的读者完成好该练习）六、 本章参考资料1. 信息安全数学基础，谢敏，西安电子科技大学出版社，2006年。2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。七、 教学后记第四章 环授课时数：6一、 教学内容及要求1. 环与子环的概念，理解2. 整环、除环和域的概念，掌握3. 环的同态与理想，掌握4. 商环、素理想和最大理想，掌握二、 教学重点与难点本章教学重点为环、除环、商环和域等的定义，环的同态与理想；本章教学难点为环的同态与理想。三、 内容的深化和拓宽在内容的深化和拓宽方面，引入公钥密码学，说明环在公钥密码学中的重要应用。四、 教学方式（手段）及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2. 通过实际的例子来阐述环、除环、商环和域的定义。3. 举例说明环的同态与理想的定义。五、 作业1利用环的定义验证4.1节中的例1、例2、例32R = 0，a，b，c，加法和乘法分别由以下两个表给出，证明R是一个环+0abc00abcaa0cbbbc0accba00abc00000a0000b0abcc0abc3求复数环中元素a+ib的逆元4Z为整数环，在集合ZZ上定义加法和乘法分别如下：(a，b) + (c，d) = (a+c，bd)，(a，b) (c，d) = (ac+bd，ad+bc)证明ZZ是一个具有单位元的环5在整数集合Z上重新定义加法和乘法如下：ab = ab，ab = a+bZ在新运算下是否构成环？6Z为整数环，Q为有理数环以下集合对普通加法和乘法是否构成环？如果是环，是否有单位元？是否是交换环？1）5Z = 5nnZ；2）Z = a+ba，bZ ；3）Q = a+ba，bQ；4）Z+ = aaZ，a07证明一个环的一个子集S构成一个子环的条件是：对于任意a，bS，有a-bS，abS8奇数集合是否构成整数环Z的子环？9设环R = z，a，b，c的运算表如下：+zabczzabcaazcbbbczaccbazzabczzzzzazabcbzzzzczabc试证：z，a，z，b，z，R都是R的子环10给出一个环的例子，使该环R有一个子环T，而且1）R有单位元，T没有单位元；2）R没有单位元，T有单位元；3）R，T有相同的单位元；4）R，T都有单位元，但不同；5）R不可交换但T可交换11设R是一个环，aR，证明S = xxR，ax = 0是R的子环12设R是一个环，且|R| 2，证明R的单位元1 0（该题隐含当|R| = 1时R的单位元1 = 0）13找出题2中的左、右零因子和零因子14有理数环、实数环、复数环有无零因子？15求模100剩余类环的所有零因子16画出环、交换环、有单位元环、无零因子环、整环、除环、域的关系图17验证：全体有理数、全体实数和全体复数对于普通的加法和乘法都是域18验证4.2节中例319证明：一个无零因子且有两个以上元素的有限环是除环 20证明：有限整环是域六、 本章参考资料1. 信息安全数学基础，谢敏，西安电子科技大学出版社，2006年。2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。七、 教学后记第五章 多项式与有限域授课时数：6一、 教学内容及要求1. 多项式环的定义，掌握2. 多项式的欧几里德算法，掌握3. 多项式剩余类环，掌握4. 有限域，掌握二、 教学重点与难点本章教学重点为多项式环、多项式剩余类环、有限域的定义，有限域的本原元及其特征；本章教学难点为有限域的构造。三、 内容的深化和拓宽在内容的深化和拓宽方面，引入公钥密码学，说明有限域在公钥密码学中的重要应用。四、 教学方式（手段）及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2. 通过实际的例子来讲解有限域构造。五、 作业1证明Fx无零因子2计算域GF(7)上两个多项式的和与乘积：f(x) = x6+5x4+ x2+6x+1，g(x) = x7+3x+13证明在GF(2)x上有(f(x)+g(x)2 = (f(x)2+(g(x)24验证x5+x4+x2+x+1，x5+x4+x3+x+1不可约5求GF(3)x上多项式x6+x3+1，x2+x+1的最大公因式6对整数环和多项式环进行比较7设GF(2)上两个多项式为：f(x) = x5+x4+ x3+ x2+x+1，g(x) = x3+x+1求f(x) mod g(x)8计算GF(2)x mod(x2+1)的加法和乘法运算表9证明5.2定理110证明在特征为p的域里，有(a+b)p = ap +bp11计算有限域GF(23)：GF(2)x mod(x3+x+1) 的加法和乘法运算表六、 本章参考资料1. 信息安全数学基础，李继国等，武汉大学出版社，2006年。2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。七、 教学后记第六章 同余式授课时数：6一、 教学内容及要求6. 同余的概念及基本性质，掌握7. 剩余类及完全剩余系，掌握8. 简化剩余系与欧拉函数，掌握9. 欧拉定理与费马小定理，掌握10. 模重复平方计算法，理解二、 教学重点与难点本章教学重点为同余、剩余类、完全剩余系和简化剩余系等的定义，欧拉定理、费马小定理以及模重复平方法；本章教学难点为剩余类、完全剩余系和简化剩余系的定义。三、 内容的深化和拓宽在内容的深化和拓宽方面，引入公钥密码学，说明同余理论在公钥密码学中的重要应用。四、 教学方式（手段）及教学过程中应注意的问题1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2. 通过实际的例子来阐述剩余类、完全剩余系和简化剩余系的定义和区别。3. 举例说明欧拉定理、费马小定理的应用。五 作业1. (1)写出模9的一个完全剩余系，它的每个数是奇数。(2) 写出模9的一个完全剩余系，它的每个数是偶数。(3)(1)或(2)中的要求对模10的完全剩余系能实现吗？2. 证明：当m2时，02,12,(m-1)2一定不是模m的完全剩余系。3. 2003年5月9日是星期五，问第天是星期几？4. 证明：如果aibi (mod m),1ik，则(1)(2) 5. 设p是素数，证明：如果a2b2 (mod p)，则p|a-b或p|a+b。6. 设n=pq，其中p，q是素数，证明：如果a2b2 (mod n)，n!|a-b, n!|a+b, 则(n,a-b)1, (n, a+b)1。7. 设整数a,b,c(c0)，满足ab (mod c)，求证：(a,c)=(b,c)。8. 下列哪些整数能被3整除，其中又有哪些能被9整除？(1) (2) (3) (4)469. 利用模9同余式来求出下式中的未知数字：10. 我们可以通过下面的方法来判断乘法c=ab是否成立：对于任意模m是否都有cab (mod m)成立？如果我们找到一个m使得cab (mod m)，那么就有cab，当我们取m9时，利用十进制与其各位数字之和同余于模9的事实来判断下列等式是否成立：(1) (2) (3) (4) 所有的这种判断是否简单明了？11. 运用Wilson定理，求。12. 证明：如果是模m的简化剩余系，那么13. 证明：如果m是正整数，a是与m互素的整数，那么14. 证明：如果a是整数，那么a7a (mod 63)。15. 证明：如果a是与32760互素整数，那么a121 (mod 32760)。16. 证明：如果p和q是不同的素数，则17. 证明：如果m和n是互素的整数，则六、 本章参考资料1信息安全数学基础，谢敏，西安电子科技大学出版社，2006年。2 信息安全数学基础，覃中平等，清华大学出版社，2006年。七、 教学后记第七章 平方剩余授课时数：6一 教学内容及要求5. 一般二次同余式，理解6. 模为奇素数的平方剩余与平方非剩余，掌握7. 勒让德符号，掌握8. 二次互反律，理解9. 雅可比符号，理解10. 模p平方根，掌握11. 合数的情形，理解12. 素数的平方表示，理解二 教学重点与难点本章教学重点为二次同余式和平方剩余等的定义，勒让德符号和雅可比符号以及求模 p 平方根；本章教学难点为二次互反律的证明。三 内容的深化和拓宽在内容的深化和拓宽方面，引入公钥密码学，说明平方剩余在公钥密码学中的重要应用。四 教学方式（手段）及教学过程中应注意的问题1 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。2通过实际的例子来阐述平方剩余的定义。3举例说明勒让德符号和雅可比符号的定义和区别。五 作业1. 求满足方程E:y2=x3-3x+1 (mod 7)的所有点。2. 求满足方程E:y2=x3+x+1 (mod 17)的所有点。3. 计算下列勒让德符号：4. 求下列同余方程的解数：(1) x2-2 (mod 67) (2) x22 (mod 67)(3) x2-2 (mod 37) (4) x22 (mod 37)5. 设p是奇素数，证明：(1) 模