教 师 教 案
( 2009—2010 学年第 一 学期 )
课 程 名 称：信息安全数学基础 授 课 学 时：40学时
授 课 班 级：信息安全专业，28063010～60班 任 课 教 师：禹勇 教 师 职 称：讲师
教师所在学院：计算机科学与工程学院
电子科技大学
课程名称 课程编号 信息安全数学基础 必修课 授课专业班级 28063010 ~ 28063060 年级 修课人数 大二 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, 3772
11. 证明:若(a,4)=2，(b,4)=2，则(a+b,4)=4。 12. 求出下列各对数的最小公倍数。 (1) 8, 60
13. 求出下列各对数的最大公因数和最小公倍数 (1) 4711791111011001, 4111831111011000 六、 本章参考资料
1. 信息安全数学基础，李继国等，武汉大学出版社，2006年。 2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。
七、 教学后记
第二章 群
授课时数：6 一、 教学内容及要求
1. 群的概念及基本性质，掌握 2. 子群的概念与判定，掌握 3. 群的同态和同构，掌握 4. 变换群，掌握 5. 置换群，掌握 二、 教学重点与难点
本章教学重点为群、子群、群同态、同构和变换群与置换群等的定义，子群的判定、群同态和同构以及同态核；本章教学难点为群、子群和同态的定义。 三、 内容的深化和拓宽
在内容的深化和拓宽方面，引入公钥密码学，说明群理论在公钥密码学中的重要应用。
四、 教学方式（手段）及教学过程中应注意的问题
1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。 2. 通过实际的例子来解释群、子群、变换群和置换群的定义。 3. 举例说明解释群同构与同态的区别和联系。 五、 作业
1．下面各集合对相应定义的运算“?”，哪些构成群？哪些不构成群？并说明理由：
1）实数集R，对运算a?b = 2(a+b)；
2）G = {1，?1}，对数的普通乘法； 3）非零实数集R*，对运算a?b = 2ab； 4）非零实数集R*，对运算a?b = |ab|； 5）所有实数对集合{(a，b) | a，b?R}，对运算
(a，b) ? (c，d) = (a+c，b?d)；
6）整数集Z，对运算a?b = a+b?1； 7）G＝{???a??bb??| a，ba??为实数且a2+b2?0}，对矩阵的普通乘法；
8）非空集合M的所有子集的集合P(M)，对运算
A?B = A∩B，(A，B?M)；
9）上述集合P(M)，对运算
A?B = A∪B，(A，B?M)；
10）G = {pmqn | m，n?Z}，其中p，q是两个固定的不同素数，对数的普通乘法．
2．全体整数的集合Z对于普通减法是否是一个群？ 3．完成2.1例6的验证．
4．对于集合A = { a1，a2，…}可以建立如下的乘法表．表中
aij = aiaj．
乘法表可以方便地判断一个集合是否是群．
1）建立通过乘法表判断是否群或交换群的规则．（提示：如果表中aij = aji，则交换律满足．）
a1 a2 … ai … a1 a11 a21 ai1 a2 a12 a22 ai2 … … … aj a1j a2j aij … … … 2）通过上面建立的规则判断G是否是群，如果是群，是否是交换群．
G = {e，a，b}，
其乘法表如下：
e a b e e a b a a b e b b e a 5．证明：在群中只有单位元满足方程
x2 = x．
6．如果群G中的每一个元都满足方程
x2 = e，
那么G是交换群．
7．设G是一个群，证明G是交换群的充分必要条件是，对于G任意元素a，b都有
(ab) 2 = a2b2．
8．设G是一个群，a，b，c是G中任意三个元素，证明：方程
xaxba = xbc
在G中有且仅有一解．
9．证明：如果a，b是群中的任意元素，则
(ab) –1 = b?1a?1．
10．证明：在任意群中，下列各组中的元素有相同的阶： 1）a与a?1； 2）a与cac?1； 3）ab与ba； 4）abc，bca，cab．
11．设G是n阶有限群．证明对于任意元a?G，都有an = e． 12．详细验证2.2例1．
13．证明：群G的两个子群的交集也是G的子群． 14．证明f(ab) = f(a)f(b)将一个群映射成另一个群． 15．证明群的同构是等价关系．
16．证明：群G为一交换群当且仅当a?a?1是一同构映射． 17．证明：一个变换群的单位元一定是恒等变换． 18．构造与整数加法群Z同构的变换群．
19．M = R\\{0，1}即M是除去0，1以外的全体实数的集合，G是M的以下6个变换的集合：
?1(x)?x，?2(x)??4(x)?1x?11xx?1x，?3(x)?1?x， ，?6(x)?xx?1，?5(x)?．
证明G是一个变换群．
20．R是实数集合．证明：R上的所以如下变换
x?ax+b，a，b是有理数，a?0
是一个变换群．这个群是不是交换群？
21．参考题4，建立三次对称群S3的乘法表．从乘法表观察S3是否阿贝尔群．
22．求出三次对称群S3的所有子群．
23．把三次对称群S3的所有元素写成不相交的循环乘积． 24．证明2.4定理4．
2?25．设G = {1，?，?}，其中? = e同构．
2
3i．证明G与三次对称群S3的一个子群
26．设计26个英文字母的一个置换，用这个置换对一段文字进行加密，并观察加密后的密文．（置换是应用了上千年的基本密码技术．这里置换表称为密钥．）
27．把置换(456)(567)(671)(123)(234)(345)写为不相交循环乘积． 28．设
? = (327)(26)(14)，? = (134)(57)
求????1 和??1??．
28．将题26的置换用不相交的循环乘积表示． 29．将上题中的每个循环用对换的乘积表示． 30．证明：对于K－循环?，有?k = I．（I—恒等变换）． 31．证明K－循环满足：
(i1 i2…ik) ?1 = (ik ik?1…i1)．
32．求交错群A4．
33．证明n次对称群Sn有阶1!，2!，3!，…n!的子群．
六、 本章参考资料
1. 信息安全数学基础，谢敏等，西安电子科技大学出版社，2006年。
2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。 七、 教学后记
第三章 循环群、群的结构
授课时数：6 一、 教学内容及要求 1. 循环群的概念，掌握
2. 欧拉函数的定义与相关计算，掌握 3. 剩余类群的概念，理解 4. 子群的陪集，掌握 5. 正规子群与商群，掌握 二、 教学重点与难点
本章教学重点为循环群的概念与应用、循环群的性质、剩余类群及其性质和正规子群的判定；本章教学难点拉格朗日定理、正规子群的判定和性质。 三、 内容的深化和拓宽
在内容的深化和拓宽方面，重点引入基于循环群建立的公钥密码算法，让学生深刻掌握循环群在公钥密码算法中的重要地位。 四、 教学方式（手段）及教学过程中应注意的问题
1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。 2. 通过实际的例子来讲解循环群、正规子群和商群。 五、 作业
1．在G到G’的一个同态映射之下：a?a’，a和a’的阶是否一定相同？ 2．证明：
1）在一个有限群里阶大于2的元的个数一定是偶数．
2）假设G是一个阶为偶数的有限群，则G中阶为2的元素个数一定为奇
数．
3．求三次对称群S3的所有元素的阶．
4．求出三次对称群S3的所有元素生成的循环子群．
5．假设a生成一个阶为n的循环群G．证明：如果(m，n) = 1（即m与n互素），am也生成G．
6．假设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的子群． 13．a，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、例3．
2．R = {0，a，b，c}，加法和乘法分别由以下两个表给出，证明R是一个环．
+ 0 a b c 0 a b c
? 0 a b c
0 a b c a 0 c b b c 0 a c b a 0 0 0 0 0 0 a 0 0 a a b 0 0 b b c 0 0 c c 3．求复数环中元素a+ib的逆元．
4．Z为整数环，在集合Z?Z上定义加法和乘法分别如下：
(a，b) + (c，d) = (a+c，b＋d)， (a，b) ? (c，d) = (ac+bd，ad+bc)．
证明Z?Z是一个具有单位元的环．
5．在整数集合Z上重新定义加法?和乘法⊙如下：
a?b = ab，a⊙b = a+b．
Z在新运算下是否构成环？
6．Z为整数环，Q为有理数环．以下集合对普通加法和乘法是否构成环？如果是环，是否有单位元？是否是交换环？
1）5Z = {5n?n?Z}；
2）Z[5] = {a+b5?a，b?Z }； 3）Q[5] = {a+b5?a，b?Q}； 4）Z+ = { a?a?Z，a?0}．
7．证明一个环的一个子集S构成一个子环的条件是：对于任意a，b?S，有
a?b?S，ab?S．
8．奇数集合是否构成整数环Z的子环？
9．设环R = {z，a，b，c}的运算表如下：
+ z a b c
? z a b c z z z z z a z a z a b z b z b c z c z c z z a b c a a z c b b b c z a c c b a z 试证：{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是一个环，a?R，证明S = {x?x?R，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节中例3．
19．证明：一个无零因子且有两个以上元素的有限环是除环．
20．证明：有限整环是域．
六、 本章参考资料
1. 信息安全数学基础，谢敏，西安电子科技大学出版社，2006年。
2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。 七、 教学后记
第五章 多项式与有限域
授课时数：6 一、 教学内容及要求 1. 多项式环的定义，掌握 2. 多项式的欧几里德算法，掌握 3. 多项式剩余类环，掌握 4. 有限域，掌握 二、 教学重点与难点
本章教学重点为多项式环、多项式剩余类环、有限域的定义，有限域的本原元及其特征；本章教学难点为有限域的构造。 三、 内容的深化和拓宽
在内容的深化和拓宽方面，引入公钥密码学，说明有限域在公钥密码学中的重要应用。
四、 教学方式（手段）及教学过程中应注意的问题
1. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。 2. 通过实际的例子来讲解有限域构造。 五、 作业
1．证明F[x]无零因子．
2．计算域GF(7)上两个多项式的和与乘积：
f(x) = x6+5x4+ x2+6x+1，g(x) = x7+3x+1．
3．证明在GF(2)[x]上有(f(x)+g(x))2 = (f(x))2+(g(x))2． 4．验证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定理1．
10．证明在特征为p的域里，有
(a+b)p = ap +bp．
11．计算有限域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. 证明：当m>2时，02,12…,(m-1)2一定不是模m的完全剩余系。 3. 2003年5月9日是星期五，问第220080509天是星期几？ 4. 证明：如果ai≡bi (mod m),1?i?k，则 (1)a1???ak(2)
?b1???bk(modm);
a1?ak?b1?bk(modm);
5. 设p是素数，证明：如果a2≡b2 (mod p)，则p|a-b或p|a+b。 6. 设n=pq，其中p，q是素数，证明：如果a2≡b2 (mod n)，n!|a-b, n!|a+b, 则(n,a-b)>1, (n, a+b)>1。
7. 设整数a,b,c(c>0)，满足a≡b (mod c)，求证：(a,c)=(b,c)。 8. 下列哪些整数能被3整除，其中又有哪些能被9整除？ (1)1843581 (2)184234081 (3)8937752744 (4)4153768912246 9. 利用模9同余式来求出下式中的未知数字：
89878?58965?5299?56270
10. 我们可以通过下面的方法来判断乘法c=ab是否成立：对于任意模m是否都有c≡ab (mod m)成立？如果我们找到一个m使得c≠ab (mod m)，那么就有c≠ab，当我们取m＝9时，利用十进制与其各位数字之和同余于模9的事实来判断下列等式是否成立：
(1)875961?2753?2410520633, (2)14789?23567?348532367, (3)24789?43717?1092700713, (4) 所有的这种判断是否简单明了？
11. 运用Wilson定理，求8?9?10?11?12?13(mod7)。 12. 证明：如果c1,c2?c?(m)是模
m的简化剩余系，那么
c1?c2???c?(m)?0(modm)13. 证明：如果m是正整数，a是与m互素的整数，那么
1?a?a???a2?(m)?1?0(modm)
14. 证明：如果a是整数，那么a7≡a (mod 63)。
15. 证明：如果a是与32760互素整数，那么a12≡1 (mod 32760)。 16. 证明：如果p和q是不同的素数，则
pq?1?pp?1?1(modpq)
17. 证明：如果m和n是互素的整数，则
m?(n)?n?(m)?1(modmn)
六、 本章参考资料
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. 计算下列勒让德符号：
?17??151??191(1)?(2)(3)?????37??373??3977??911??37???(4)(5)(6)?????????2003??200723??20040803?
4. 求下列同余方程的解数：
(1) x2≡-2 (mod 67) (2) x2≡2 (mod 67) (3) x2≡-2 (mod 37) (4) x2≡2 (mod 37)
5. 设p是奇素数，证明：
(1) 模p的所有二次剩余的乘积对模p的剩余是(-1)(p+1)/2。 (2) 模p的所有二次非剩余的乘积对模p的剩余是(-1)(p+1)/2。 (3) 模p的所有二次剩余之和对模p的剩余是：1，当p=3;0,当p>3。
(4) 所有二次非剩余之和对模p的剩余是多少? 6. 判断下列同余方程是否有解：
(1) x2≡7 (mod 227) (2) x2≡11 (mod 511) (3) 11x2≡-6 (mod 91) (4) 5x2≡-14 (mod 6193)
7. 证明：23|211-1,47|223-1,503|2251-1。 六 本章参考资料
1.信息安全数学基础，谢敏，西安电子科技大学出版社，2006年。 2.信息安全数学基础，覃中平等，清华大学出版社，2006年。 七 教学后记
第八章 原根与指标
授课时数：6 一 教学内容及要求
5. 指数及其基本性质，掌握 6. 原根存在的条件，掌握 7. 指标及n次剩余，掌握 二 教学重点与难点
本章教学重点为原根、指数、指标等的定义，原根判别法则以及原根的求解；本章教学难点为n次剩余。 三 内容的深化和拓宽
在内容的深化和拓宽方面，引入离散对数问题，加强学生对指数的理解。
四 教学方式（手段）及教学过程中应注意的问题
3. 在讲述本章内容时，主要采用口头讲解，PPT演示的方式。 4. 通过实际的例子来阐述原根的求解方法。 五 作业
1. 计算2，5，10模13的指数。 2. 计算3，7，10模19的指数。
3. 设m>1是整数，a是与m互素的整数。假如ordm(a)=st，那么ordm(as)=t。
4. 设n是一个整数，d是?(n)的一个正因数。问是否存在整数使得ordn(a)=d?
5. 设p是一个奇素数，并且素的正整数。如果
p?12也是一个奇素数，设a是与p互
p?1a?1,a?1,a22?1(modp)
则a是模p的原根。
6. 设n是正整数，如果存在一个整数a使得
an?1?1(modn)
以及
n?1aq?1(modn)
对n-1的所有素因数q，则n是一个素数。 7. 求解同余式
x22?5(mod41)
8. 求解同余式
x22?29(mod41)
六 本章参考资料
1. 信息安全数学基础，谢敏，西安电子科技大学大学出版社，2006年。
2. 信息安全数学基础，覃中平等，清华大学出版社，2006年。 七 教学后记