信安数学练习题

1、已知a=66,b=75，求正整数x,y ，使ax-by=(a,b)成立 .（知识点：最大公约数、欧几里德除法、线性表达）（进一步：计算方法-）算法-〉程序）

2、计算5模11的逆元

3、解方程567x ≡21(mod 1225)

4、15的完系和缩系，（进一步：全奇或全偶），1 mod5写成x mod15，计算x （剩余类分解）

5、计算15的欧拉函数

6、化简：115x 15+278x 3+12 (mod 12)，x=20

7、已知a=5,b=42,n=435, 求a b mod n

8、求如下同余式组的解

x ≡1(mod 5)

x ≡3(mod 7)

x ≡2(mod 9)

9、写出模19的所有二次剩余

10、5是模31的二次剩余吗？

11、（13/283）（知识点：勒让德符号、二次互反）

12、求x 2≡13（mod 113）的解

13、找出模13的所有原根，有多少个？并据此求出1-12每个数的阶

14、1841是强伪素数吗？

16、（Z ，*）是群吗？其中*定义为 a*b=a+b-4（进一步：3律3元）

17、（Z 12,+12）的各子群

18、群的阶与元素的阶，如Z 14的的每个元素的阶、所有生成元和所有子群

19、置换，理解含义，会计算

20、多项式环上的运算，如Z2上的多项式环中：（1）f(x)=x 2+x+1，可约吗？（2）加法：f(x)=x 2+x+1，g(x)=x 3+1，f(x+g(x)（3）除法：f(x)= x 4+x+1,g(x)=x+1,f(x)/g(x)（注意：有商有余）（4）求两个多项式的最大公约数

21、构造一个八元域

22、扩成域：由GF(2)上的既约多项式p(x)= x 4+x+1扩成GF(24)

23、CRC 计算：生成多项式为f(x)=x 4+x+1，传送的信息为10110100110，请给出接收方收到的信息，并进行校验

24、RSA ：RSA 加解密运算，防范攻击的措施

注意：重点题目而不是数字。

考试题目类型：基础题（指要求结果，部要求运算过程，10分，5个）；计算题（过程给分，60分，7个），证明题（1个，10分），应用题（2个，15分），分析题（1个，10分）

)142(23144321=???

? ??

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

信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 1 整除的概念 定义1 设a 、b 是两个整数，其中b ≠0如果存在一个整数 q 使得等式 a=bq 成立，就称b 整除a 或者a 被b 整除，记作b|a ，并把b 叫作a 的因数，把a 叫作b 的倍数.这时，q 也是a 的因数，我们常常将q 写成a ／b 或 否则，就称b 不能整除a 或者a 不能被b 整除，记作a b. 2整除的基本性质 (1)当b 遍历整数a 的所有因数时，-b 也遍历整数a 的所有因数. (2)当b 遍历整数a 的所有因数时，a/b 也遍历整数a 的所有因数. (3)设b ，c 都是非零整数， (i)若b|a ，则|b|||a|. (ii)若b|a ，则bc|ac. (iii)若b|a ，则1<|b|≤|a|. 3整除的相关定理 (1) 设a ，b ≠0，c ≠0是三个整数.若c|b ，b|a ，则c|a. (2) 设a ，b ，c ≠0是三个整数，若c|a ，c|b ，则c|a ±b (3) 设a ，b ，c 是三个整数.若c|a ，c|b 则对任意整数s ，t ，有c|sa+tb. (4) 若整数a 1 , …,a n 都是整数c ≠0的倍数，则对任意n 个整数s 1，…， a b n n a s a s ++ 11

s n，整数是c的倍数 (5) 设a，b都是非零整数.若a|b，b|a，则a=±b (6) 设a, b , c是三个整数，且b≠0，c ≠0，如果(a , c)=1,则(ab , c)=(b , c) (7) 设a , b , c是三个整数，且c≠0，如果c｜ab , (a , c) = 1, 则c | b. (8) 设p 是素数，若p |ab , 则p |a或p|b (9) 设a1 , …,a n是n个整数，p是素数，若p| a1…a n,则p一定整除某一个a k 二整数的表示 主要掌握二进制、十进制、十六进制等的相互转化. 三最大公因数和最小公倍数 (一)最大公因数 1．最大公因数的概念 定义：设是个整数，若使得，则称为的一个因数．公因数中最大的一个称为的最大公因数．记作. 若,则称互素． 若,则称两两互素． 思考：1．由两两互素，能否导出 2．由能否导出两两互素？ 2．最大公因数的存在性 (1)若不全为零，则最大公因数存在并且

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

信息安全数学基础第一阶段知识总结 第一章 整数的可除性 一 整除的概念和欧几里得除法 1 整除的概念 定义1 设a 、b 是两个整数，其中b ≠0如果存在一个整数 q 使得等式 a=bq 成立，就称b 整除a 或者a 被b 整除，记作b|a ，并把b 叫作a 的因数，把a 叫作b 的倍数.这时，q 也是a 的因数， 我们常常将q 写成a ／b 或 否则，就称b 不能整除a 或者a 不能被b 整除，记作a b. 2整除的基本性质 (1)当b 遍历整数a 的所有因数时，-b 也遍历整数a 的所有因数. (2)当b 遍历整数a 的所有因数时，a/b 也遍历整数a 的所有因数. (3)设b ，c 都是非零整数， (i)若b|a ，则|b|||a|. (ii)若b|a ，则bc|ac. (iii)若b|a ，则1<|b|≤|a|. 3整除的相关定理 (1) 设a ，b ≠0，c ≠0是三个整数.若c|b ，b|a ，则c|a. (2) 设a ，b ，c ≠0是三个整数，若c|a ，c|b ，则c|a ±b (3) 设a ，b ，c 是三个整数.若c|a ，c|b 则对任意整数s ，t ， a b

有c|sa+tb. (4) 若整数a 1 , …,a n 都是整数c ≠0的倍数，则对任意n 个整数s 1，…，s n ，整数 是c 的倍数 (5) 设a ，b 都是非零整数.若a|b ，b|a ，则a=±b (6) 设a, b , c 是三个整数，且b ≠0，c ≠0，如果(a , c)=1,则 (ab , c)=(b , c) (7) 设a , b , c 是三个整数，且c ≠0，如果c ｜ab , (a , c) = 1, 则c | b. (8) 设p 是素数，若p |ab , 则p |a 或p|b (9) 设a 1 , …,a n 是n 个整数，p 是素数，若p| a 1 …a n ,则p 一定整除某一个a k 二 整数的表示 主要掌握二进制、十进制、十六进制等的相互转化. 三 最大公因数和最小公倍数 (一)最大公因数 1．最大公因数的概念 定义：设是 个整数，若 使得 ， 则称 为 的一个因数．公因数中最大的一个称为 的最大公因数．记作 . 若 ,则称 互素． 若 ,则称 两两互素． n n a s a s ++ 11

信息安全数学基础(A)答案

贵州大学2007-2008学年第二学期考试试卷（标准答案） A 信息安全数学基础 注意事项： 1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。 2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。 3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。 4. 满分100分，考试时间为120分钟。 一、设a,b 是任意两个不全为零的整数，证明：若m 是任一整数，则 [am,bm]=[a,b]m.(共10分) 解： 2 2[,](3(,)(3(,)(2( ,) [,](2abm am bm am bm abm a b m abm a b a b m = == =分） 分） 分） 分） = = 二、设 n=pq,其中p,q 是素数.证明：如果 2 2 =(mod ),,,a b n n a b n a b -+宎宎 则(,)1,(,)1n a b n a b ->+>（共10分） 证明：由2 2 2 2 =(mod ),|-,|()()a b n n a b n a b a b +-得即a a (2分） 又n pq =，则|()(),|()|(),pq a b a b p p a b p a b +-+-因为是素数，于是或a a a (2分） 同理，|()|()q a b q a b +-或a a (2分） 由于,n a b n a b -+宎 ，所以如果|()p a b +a ，则|()q a b -a ，反之亦然. (2分） 由|()p a b +a 得(,)1n a b p +=> (1分） 由|()q a b -a 得(,)1n a b q -=> (1分）

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

信息安全数学基础第一阶段知识总结 第一章整数得可除性 一整除得概念与欧几里得除法 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．最大公因数得概念 定义:设就是个整数,若使得 ,则称为得一个因数。公因数中最大得一个称为得最大公因数。记作、 若，则称互素。 若,则称两两互素。?思考:１.由两两互素，能否导出 2。由能否导出两两互素？ ２。最大公因数得存在性 （1)若不全为零,则最大公因数存在并且 (2)若全为零,则任何整数都就是它得公因数。这时,它们没有最大公因数． 3.求两个正整数得最大公因数。 定理1：设任意三个不全为零得整数，且则

信息安全数学基础教学大纲

西北师范大学网络与信息安全方向课程教学大纲 信息安全数学基础 一、说明 （一）课程性质 专业课、必修课 （二）教学目的 信息安全数学基础是网络与信息安全方向的一门核心数学基础课，是一门理论性较强的课程。本课程的目的是为了适应信息安全专业培养目标的要求，使学生学习掌握如何应用信息安全数学中的理论和方法来分析研究信息安全中的实际问题。 （三）教学内容 向学生系统介绍信息安全数学基础的理论和方法，使学生认识信息安全数学在信息安全中的作用，领会其基本思想和分析与解决问题的思路。要求掌握整除与欧几里得除法、不定方程、同余、同余方程、二次同余式与平方剩余、原根与指标，近世代数（群与群的结构、环论、域的结构、有限域等）等内容。 （四）教学时数 学时数为：72学时 （五）教学方式<宋体小四加粗> 教学方法为课堂教学 二、各章教学内容和要求 第1章整数的可除性 教学要点： 掌握整除的基本概念和性质，最大公因数的概念和广义欧几里得除法的使用，最小公倍数以及素数的基本定理。重点为整除的概念、广义欧几里得除法。从基本的整除理论入手，阐明本课程与其他学科的关系，让学生对整个理论框架有个初步的认识，同时也尽量培养学习兴趣。 教学时数： 11学时 教学内容： 1.1 整除的概念欧几里得除法（4学时） 介绍整数的一些基本概念和性质 1.2 整数的表示（1学时） 介绍整数的各种表示形式 1.3 最大公因数与广义欧几里得除法（1学时） 介绍最大公因数与广义欧几里得除法 1.4 整除的进一步性质及最小公倍数（1学时） 介绍最小公倍数的定义和相关性质 1.5 素数算术基本定理（1学时） 介绍算术基本定理和素数的性质 1.6 素数定理（1学时） 介绍素数的判定算法

信息安全数学基础课后答案完整版Word版

第一章参考答案 （1） 5,4,1,5. （2） 100=22*52, 3288=23*3*137. （4） a,b可以表示成多个素因子的乘积a=p 1p 2 ––p r , b=q 1 q 2 ––q s ,又因为(a, b)=1，表明a, b没有公共(相同)素因子. 同样可以将a n, b n表示为多个素因子 相乘a n=(p 1p 2 ––p r )n, b n=(q 1 q 2 ––q s )n明显a n, b n也没有公共(相同)素因子. （5）同样将a, b可以表示成多个素因子的乘积a=p 1p 2 ––p r , b=q 1 q 2 ––q s , a n=(p 1p 2 ––p r )n, b n=(q 1 q 2 ––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=p 1p 2 ––p r , b=q 1q 2 ––q s , ab=p 1 p 2 ––p r q 1 q 2 ––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,9 7,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=k 1m+r, bc=k 2 m+r,有 ac=k 1d(m/d)+r, bc=k 2 d(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)

信息安全数学基础2018(A卷)

广州大学2017-2018学年第一学期考试卷课程信息安全数学基础2 考试形式（闭卷，考试） 学院_________系_____专业班级______学号___________姓名_________ 或开除学籍处分并且被取消相应课程本次考试成绩的，不授予学士学位。” 一、简答题（每小题5分，共25分） 1．什么是正规子群？ 2．试写出群同态基本定理的内容。 3．试说明什么整环？

4．试解释什么是多项式的分裂域。 5. 试说明有限域中的本原元是什么？ 二、判断题（每小题2分，共10分） 1. 两个偶置换的乘积一定是偶置换( ) 2. 循环群一定是交换群( ) 3. 两个子群的交可集能不是子群( ) 4. E/K是代数扩张，K/F是代数扩张，则E/F也是代数扩张( ) 5. n次分圆多项式Q n(x)的次数一定是n ( ) 三、计算题（每题10分，共50分） 1. 在S4中，令K={(1),(12)(34),(13)(24),(14)(23)}，求K的所有左陪集。

2. 验证集合H={[0],[4],[8],[12],[16],[20]}是加法群(Z ,+)的正规子群，并 24 /H，该商群中有几个元素？ 计算商群Z 24 3. 设Z[i]={a+bi|a,b∈Z,i2=-1}，令I=(2+i)为主理想。求剩余类环Z[i]/I。 4. 在高斯整数环Z[i]={a+bi|a,b∈Z}中，试将11+13i分解为不可约元之积。

5. 找出F 2[x]中的一个4次本原多项式。 四、证明题（每题5分，共15分） 1. 假定G 是群，a,b ∈G ，如果o(a)=3, o(b)=4，并且ab=ba ，证明o(ab)=1 2. 2. 试证明() 32)3,2(+=Q Q .

信息安全数学基础习题答案

信息安全数学基础习题答案 第一章整数的可除性 1．证明：因为2|n 所以n=2k , k∈Z 5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1，k1∈Z 7|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|n 2．证明：因为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为素数。 由737=11*67 ,747=3*249 知737与747都为合数。 8．解：存在。eg：a=6,b=2,c=9 10．证明：p1 p2 p3|n，则n= p1 p2 p3k，k∈N+ 又p1≤p2≤p3，所以n= p1 p2 p3k≥p13 即p13≤n1/3 p1为素数则p1≥2，又p1≤p2≤p3，所以n= p1 p2 p3k≥2 p2 p3≥2p22 即p2≤(n/2)1/2得证。 11．解：小于等于5001/2的所有素数为2，3，5，7，11，13，17，19，依次删除这些素数的倍数可得所求素数： 12．证明：反证法 假设3k+1没有相同形式的素因数，则它一定只能表示成若干形如3k-1的素数相 乘。 (3 k1+1)(3 k2+1)=[( 3 k1+1) k2+ k1]*3+1 显然若干个3k+1的素数相乘，得

信息安全数学基础答案第一二三四五六七八章2

第一章 （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|n 所以n=2k , k∈Z 5|n 所以5|2k ，又（5，2）=1，所以5|k 即k=5 k1 ，k1∈Z 7|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|n 2．证明：因为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

信安数学基础答案

信安数学基础答案 【篇一：信息安全数学基础课后答案完整版】 1） 5,4,1,5. （2） 100=22*52, 3288=23*3*137. （4） a,b可以表示成多个素因子的乘积a=p1p2––pr, b=q1q2––qs,又因为(a, b)=1，表明a, b没有公共(相同)素因子. 同样可以将an, bn表示为多个素因子相乘an=(p1p2––pr)n, bn=(q1q2––qs)n明显an, bn也没有公共(相同)素因子. （5）同样将a, b可以表示成多个素因子的乘积a=p1p2––pr, b=q1q2––qs, an=(p1p2––pr)n, bn=(q1q2––qs)n,因为an| bn所以对任意的i有, pi的n次方| bn, 所以bn中必然含有a的所有素因子, 所以b中必然含有a的所有素因子, 所以a|b. （6）因为非零a, b, c互素,所以(a, b)=(a, c)=1,又因为a=p1p2––pr, b=q1q2––qs, ab=p1p2––prq1q2––qs, 又因为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,1 99. （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, 所以结论成立.

信息安全数学基础课后答案完整版.doc

第一章参考答案 （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, 方程两边左

信息安全数学基础知识点

第六章 素性检验 6.1 拟素数 引例：根据Fermat 小定理，我们知道：如果n 是一个素数，则对任 意整数b,(b,n)=1,有 )(mod 11n b n ≡- 由此，我们得到：如果一个整数b,(b,n)=1,使得 ) (mod 11n b n ≡/-，则n 是一个合数。 定义1：设n 是一个奇合数，如果整数b,(b,n)=1使得同余式 )(mod 11n b n ≡-成立，则n 叫做对于基b 的拟素数。 引理：设d,n 都是正整数，如果d 能整除n 则 12-d 能整除12-n 定理1：存在无穷多个对于基2的拟素数。 定理2：设n 是一个奇合数，则 (i)n 是对于基b,((b,n)=1),的拟素数当且仅当b 模n 的指数整除n-1。 (ii)如果n 是对于基1b ((1b ,n)=1),和基2b ，((2b ,n)=1),的拟素数，则 n 是对于基21b b 的拟素数。 (iii)如果n 是对于基b,((b,n)=1),的拟素数，则n 是对于基1-b 的拟素数。 (iv)如果有一个整数b ，((b,n)=1),使得同余式 )(mod 11n b n ≡-不成立，则模n 的简化剩余系中至少有一半的数使得该同余式不成立。 //////////////////////////////////////////////////////////////////////////////////////////////////////////

Fermat 素性检验 给定奇整数3≥n 和安全参数t 。 1.随即选取整数 b ,22-≤≤n b ； 2.计算()n b r n mod 1-=; 3.如果1≠r ，则n 是合数； 4.上述过程重复t 次； 定义2：合数n 称为Carmichael 数，如果对所有的正整数b ，(b,n)=1, 都有同余式 ()n b n mod 11≡-成立 定理3：设n 是一个奇合数。 (i)如果n 被一个大于1平方数整除，则n 不是Carmichael 数。 (ii)如果k p p n Λ1=是一个无平方数，则n 是Carmichael 数的充要条件是 11--n p i ，k i ≤≤1 定理4：每个Carmichael 数是至少三个不同素数的乘积 注：1.存在无穷多个Carmichael 数 2.当n 充分大时，区间[]n ,2内的Carmichael 数的个数大于等于72n 6.2 Euler 拟素数 引例：设n 是奇素数，根据定理，我们有同余式 )(mod 21n n b b n ?? ? ??≡- 对任意整数b 成立 因此，如果存在整数b ，(b,n)=1,使得

信息安全数学

School of Mathematics and Applied Statistics INFO412 Mathematics and Cryptography Section1:Elementary Theorems

De?nition1.1 (i)An integer n is divisible by an integer k if there exists an integer l such that n=lk. We write k|n and we say that k divides n or that k is a factor of n. (ii)An integer n>1is prime if n is only divisible by itself and1. (iii)An integer n>1is composite if it is not prime. Note1.2 The number1is neither prime nor composite. Example1.3 Since6=2×3,we have3|6and6is divisible by3(or3divides6,or3is a factor of6). The?rst few primes are 2,3,5,7,11,13,17,19,23,....

Theorem1.4 There are in?nitely many primes. Proof. Assume there are only?nitely many primes,say p1,p2,...,p k.Consider the number n=p1p2···p k+1. If p i|n then p i|(n?p1p2···p k),that is,p i|1. This is impossible,and so p i does not divide n. Thus n has no prime factors,a contradiction. Hence there must be an in?nite number of primes. Remark1.5 Here,we used the fact that each integer n>1 has at least one prime factor.This is a theorem in its own right,and requires proof.(Can you prove it?You will need to use mathematical induction,or something equivalent.)

信息安全数学基础课后答案完整版.doc

第一章参考答案 (1)5,4,1,5. (2)100=22*52,3288=23*3*137. (4)a,b可以表示成多个素因子的乘积a=pip2—p r? b=q】q2—q、,又因为(a, b)=l, 表明a, b没有公共(相同)素因子.同样可以将a) 9表示为多个素因子相乘a n=(pip2一py, b n=(qiq2一q s)n明显a n, b n也没有公共(相同)素因子. (5 ) 同样将a, b可以表示成多个素因子的乘积a=pip2一p r, b=qiq2—q s, a n=(PiP2—Pr)L b'-(qiq2—s)L因为a n| b“所以对任意的i有,pi的n次方| b n,所以中必然含有a 的所有素因子，所以b中必然含有a的所有素因子，所以a|b. (6)因为非零a, b, c 互素，所以(a, b)=(a, c)=l,又因为a=pip2一Pr, b=qiq2— ab=p)p2—Prqiq?― 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)*—*(-l)=?9!=?362880=l(mod 71).明显61!与71互素，所以两边同乘以61!,所以70!=61!(mod71). (13)当n为奇数时2n=(.l)n=.l=2(mod 3),两边同时加上1有2n+l=0(mod 3), 所以结论成立. 当n为偶数时2n=(-l)n=l(mod 3),两边同时加上1有2n+l=2(mod 3),所以结论成立. (14 ) 第一个问：因为(c,m)=d, m/d 为整数.假设ac=k]m+r, bc=k2m+r,有ac=k|d(m/d)+r, bc=k2d(m/d)+r 所以ac=bc(mod m/d),因为(c,m/d)=l,所以两边可以同除以一个c,所以结论成立. 第二个问题：因为a=b(mod m),所以a.b=ki*m“ a-b是任意mi的倍数，所以a.b是mi公倍数，所以[mj]|a.b.(利用式子：最小公倍数=每个数的乘积/最大公约数，是错误的，该式子在两个数时才成立) (15) 将整数每位数的值相加，和能被3整除则整数能被3整除，和能被9整除则整数能被9整除,(1)能被3整除，不能被9整除，(2)都不能，(3)都不能，(4) 都不能 第二章答案 (5)证明：显然在群中单位元c满足方程x2=x,假设存在一?个元素a满足方程x2=x，则有a2=a，两边同乘以广有3『.所以在群中只有单位元满足方程x2=x. (6)证明：因为群G中每个元素都满足方程x2=e,所以对群中任意元素a,b 有aa=e, bb=e, (ab)?=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-l ababb_,= a_,aabbb-1,有ab=ba,所以G是交换群.

信息安全数学基础 (一)

信息安全数学基础第一章——第三章 知识点梳理 内容：整数的可除性、同余、同余式（概念、定理/性质、教材典型例题）

练习题： 1. a =24871与b =3468的最大公因数，运用广义欧几里得除法计算(a , b )并求整数s 和t ，使得sa ＋tb ＝(a , b )。 2. 求1008与1134的最大公因数和最小公倍数。 3. 证明3个相邻整数的乘积是3的倍数。 4. 试证对任意的整数n ，数23 326 n n n ++是整数。（通分，利用3题结论） 5. 任意一个n 位数121n n a a a a -与其按逆字码排列得到的数 11 1n n a a a a -的差是9的倍数。（说明12121111010n n n n n n a a a a a a a ----=?+?++） 6. 证明当0n >时，()1n n +不可能是平方数。（提示：反正法，假设 ()21,0n n m m +=>）

7. 设{}1,2, ,2001A =则不存在集合A 的划分123A A A A A =???，其中集合i A 中各数字的和组成等差数列。（反正法，假设存在()14i A i ≤≤各数字之和分别为,,2,3a a d a d a d +++） 8. 设 a 和b 是整数，n 是正整数，证明 (a ×b ) (mod n )＝ ((a mod n ) × (b mod n )) mod n 。 9. 求使21n +能被3整除的一切自然数n 。 10. 证明：如果m 和n 是互素的大于1的整数，则 ()()() 1 mod n m m n mn ??≡＋。（欧拉定理） 11. 对任意整数a ，5a 与a 的个位数相同。（费马定理） 12. 证明：如果a k ≡ b k (mod m )，a k +1 ≡ b k +1 (mod m ) ，a ，b ，k ，m 是整数，k > 0，并且(a ，m ) ＝1，那么a ≡ b (mod m )。 13. 求出一次同余数式()63mod9x ≡的所有解。 14. 求解同余式组8(mod 23)4(mod 29) x x ≡??≡?. 15. （应用题）设p ，q 是两个不同的奇素数，n ＝pq ，a 是与pq 互素的整数。整数e 和d 满足(e , ? (n ))＝1，ed ≡ 1 (mod ? (n ))，1 < e < ? (n )，1 ≤ d< ? (n )。 证明：对任意整数c ，1 ≤ c < n ，若a e ≡ c (mod n )，则有c d ≡ a (mod n )。