级信息安全数学基础试卷B答案

1、诚信应考，考试作弊将带来严重后果！华南理工大学期末考试信息安全数学基础试卷B-答案)题答不内线封密(题号-一一二二三三四总分得分评卷人注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3考试形式：闭卷；4.本试卷共四大题，满分100分，考试时间120分钟。.选择题：(每题2分，共20分)1.(1)。2.(4)。3.(3)o4.(2)。5.(2)。6.(3)。7.8.(4)。9.。10(3).填空题：(每题2分，共20分)线1.设m是正整数，a是满足a?m的整数，则一次同余式：ax?b(modm)有解的充分必要条件是(a,n)lb。当同余式ax?b(modm)有解时，其解数为

2、d=(a,m。2.设m是正整数，则m个数0,1,2,，m-1中与m互素的整数的个数叫做m的欧拉(Euler)函数，记做？(m)。3.整数2t+1和2t1的最大公因数(2t+1,2t1)=。4.设a,b是正整数，且有素因数分解aPJP22Pss,i0,i1,2,S，min(P11P22PsS,i0,i1,2,s，则pL_)min(2,2)min(s,s)P2Ps2,a,bpmax(1,1)p异2,2)I”pJs)。5.如果a对模m的指数是，贝Ua叫做模m的原根。6. 设m是一个正整数，a是满足(_a,m)=1的整数，则存在整数a?，Ka?vm，使得aa?=1(modm)。7. Wilson定理：

3、设p是一个素数，则(P-1)!三一1(modP)。8. (中国剩余定理)设m,m是k个两两互素的正整数，则对任意的整数4,bk同余式组x?b1(modm)x?bk(modm)有唯一解。令mi=mm,mi=mM,i=1,，k,则同余式组的解为:x三叫?叫+叫？Mbk(modm,其中M?M三1(modm)，i=1，2,k。9正整数n有标准因数分解式为npi1pkk，则n的欧拉函数1 111(n)n(1)n(1)(1一川|(1)。10设G和G?是两个群,f是G1到G?3的一个映射。如果对任意的a,bG,都有f(ab)=f(a)f(b),那么，f叫做G到G?的一个同态。三证明题(写出详细证明过程)：(

4、共30分)1证明：形如4k+3的素数有无穷多个。(6分)证明分两步证明。先证形如4k+3的正整数必含形如4k+3的素因数由于任一奇素数只能写成4n+1或4n+3的形式，而(4n+1)(4n?+1)16nn2+4n+4n?+1=4(4nn?+n+n?)+1,所以把形如4n+1的数相乘的积仍为4n+1形式的数。因此，把形如4k+3的整数分解成素数的乘积时，这些素因数不可能都是4n+1的形式的素数，一定含有4n+3形式的素数。其次，设N是任一正整数，并设p1,p2，ps是不超过N的形如4k+3的所有素数。令q4p1p2ps1。显然，每个pi(i1,2,s)都不是q的素因数，否则将会导致pi|1，得到

5、矛盾。如果q是素数，由于q4p1p2ps14(p1p2ps1)+3,即卩q也是形如4k+3的素数，并且显然q?pi(i1,2,s),从而q>N。即q是形如4k+3的大于N的素数。如果q不是素数，由第一步证明知q含有形如4k+3的素因数p,同样可证p?Pj(i=1,2,s)，从而p>N。即p是形如4k+3的大于N的素数。由于N是任意的正整数，因此证明了形如4k3的素数有无穷多个。2 .设a,b是两个整数，其中b>0。则存在唯对整数q,r使得a=bq+r，0?r<b。(6分)证明：存在性.考虑整数序列：,-3b,-2b,-b,0,b,2b,3b,序列的各项把实数轴划分成长度

6、为b的区间，a一定落在其中的一个区间中。因此，存在一个整数q使得qb?a<(q+1)b，即0?a-bq<b。令r=a-bq,则有a=bq+r,0?r<b。唯一性.假设还有一对整数q1,r1也满足：a=bq1+r1，0?r1<b。(2)(1) 和(2)两式相减得b(q-q1)=-(r-r1)。(3)当q?q1时，(3)式左边的绝对值大于等于b,而右边的绝对值小于b,得到矛盾。故q=q，r=r。3 .设p,q是两个不同的奇素数，n=pq,a是与pq互素的整数。整数e和d满足(e,?(n)=1,ed?1(mod?(n),1<e<?(n),1?d<?(n)。证

7、明：对任意整数c,1?c<n,若ae?c(modn)，则有cd?a(modn)。(12分)证明：因为(e,?(n)=1,根据2.3定理4,存在整数d,Kd<?(n),使得ed=1(mod?(n)因此，存在一个正整数k使得ed=1+k?(n)。由，a与n=pq互素知，(a,p)=1根据Euler定理，a?(p)=1(modp)两端作k(?(n)/?(p)次幕得，ak?(n)=1(modp)两端乘以a得到a1+k?(n)=a(modp)即aed=a(modp)同理，aed=a(modq)因为p和q是不同的素数，根据2.1定理12，edae=a(modn)因此，cd=(ae)d=a(mo

8、dn)4证明：设p和q是两个不相等的素数，证明：pq1qp11(modpq)。(6分)证明：因为p和q是两个不相等的素数，由Euler定理，qp11modp，pq11modq，所以pq1qp11modp,pq1qp11modq，而p,q1，因此pq1qp11modpq。四计算题(写出详细计算过程)：(共30分)1用模重复平方法计算12996227(mod37909)。(6分)设m=37909,b=12996,令a=1,将227写成二进制，227=1+2+25+26+27运用模重复平方法，我们依次计算如下:(1) n0=1,计算2a0=axb三12996,b1b2三11421(mod37909)

9、(2) n1=1,计算2a1=a°xb三13581,b?三%2三32281(mod37909)(3) n2=0,计算*21三13581,b3=b?2三20369(mod37909)(4) n3=0,计算*3习2三13581,三bg2三20065(mod37909)n4=0,计算*4=*3三13581,b5=bq2三10645(mod37909)n5=1,计算*5=*4乂三22728,三b§2三6024(mod37909)n6=1,计算2&6=a5xb6=24073,b?三bg=9663(mod37909)(8)n7=1,计算*7=*6b?三7775(mod37909

10、)最后，计算出22712996227三7775(mod37909)2.设a=1859,b=1573，运用广义欧几里得除法(8分)(1)计算(a,b)；(2)求整数s,t使得sa+tb=(a,b)737=1?635+102,102=7371?635635=6?102+23,23=6356?1102=4?23+10,10=1024?2323=2?10+3,3=232?1010=3?3+1,1=103?31=103?3=(1024?23)3(232?10)=1027?23+6?10=1027?23+6(1024?23)=7?10231?23=7?10231?(6356?103)=193?10231?

11、635=193?(7371?635)31?635=193?737224?635所以s=193,t=224,使得193?737+(224)?635=1。3.运用中国剩余定理和欧拉定理计算21000000(mod77)。(16分)利用2.4定理1(Euler定理)及中国剩余定理计算。令x=21000000,因为77=711，所以，计算x=210°°°°°(mod77)等价于求解同余式组21000000b1(mod7)x=210°°°°°三b2(mod11)因为Euler定理给出2?(7)三26三1(mod7),以及1000000=1666666+4,所以b1三21000000三(26)16666624三2(mod7)类似地，因为2?(11)三210三1(mod11),1000000=1000001