級信息安全數(shù)學(xué)基礎(chǔ)試卷B答案

1、誠信應(yīng)考，考試作弊將帶來嚴重后果！華南理工大學(xué)期末考試信息安全數(shù)學(xué)基礎(chǔ)試卷B-答案)題答不內(nèi)線封密(題號-一一二二三三四總分得分評卷人注意事項：1.考前請將密封線內(nèi)填寫清楚；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.設(shè)m是正整數(shù)，a是滿足a?m的整數(shù)，則一次同余式：ax?b(modm)有解的充分必要條件是(a,n)lb。當(dāng)同余式ax?b(modm)有解時，其解數(shù)為

2、d=(a,m。2.設(shè)m是正整數(shù)，則m個數(shù)0,1,2,，m-1中與m互素的整數(shù)的個數(shù)叫做m的歐拉(Euler)函數(shù)，記做？(m)。3.整數(shù)2t+1和2t1的最大公因數(shù)(2t+1,2t1)=。4.設(shè)a,b是正整數(shù)，且有素因數(shù)分解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的指數(shù)是，貝Ua叫做模m的原根。6. 設(shè)m是一個正整數(shù)，a是滿足(_a,m)=1的整數(shù)，則存在整數(shù)a?，Ka?vm，使得aa?=1(modm)。7. Wilson定理：

3、設(shè)p是一個素數(shù)，則(P-1)!三一1(modP)。8. (中國剩余定理)設(shè)m,m是k個兩兩互素的正整數(shù)，則對任意的整數(shù)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正整數(shù)n有標準因數(shù)分解式為npi1pkk，則n的歐拉函數(shù)1 111(n)n(1)n(1)(1一川|(1)。10設(shè)G和G?是兩個群,f是G1到G?3的一個映射。如果對任意的a,bG,都有f(ab)=f(a)f(b),那么，f叫做G到G?的一個同態(tài)。三證明題(寫出詳細證明過程)：(

4、共30分)1證明：形如4k+3的素數(shù)有無窮多個。(6分)證明分兩步證明。先證形如4k+3的正整數(shù)必含形如4k+3的素因數(shù)由于任一奇素數(shù)只能寫成4n+1或4n+3的形式，而(4n+1)(4n?+1)16nn2+4n+4n?+1=4(4nn?+n+n?)+1,所以把形如4n+1的數(shù)相乘的積仍為4n+1形式的數(shù)。因此，把形如4k+3的整數(shù)分解成素數(shù)的乘積時，這些素因數(shù)不可能都是4n+1的形式的素數(shù)，一定含有4n+3形式的素數(shù)。其次，設(shè)N是任一正整數(shù)，并設(shè)p1,p2，ps是不超過N的形如4k+3的所有素數(shù)。令q4p1p2ps1。顯然，每個pi(i1,2,s)都不是q的素因數(shù)，否則將會導(dǎo)致pi|1，得到

5、矛盾。如果q是素數(shù)，由于q4p1p2ps14(p1p2ps1)+3,即卩q也是形如4k+3的素數(shù)，并且顯然q?pi(i1,2,s),從而q>N。即q是形如4k+3的大于N的素數(shù)。如果q不是素數(shù)，由第一步證明知q含有形如4k+3的素因數(shù)p,同樣可證p?Pj(i=1,2,s)，從而p>N。即p是形如4k+3的大于N的素數(shù)。由于N是任意的正整數(shù)，因此證明了形如4k3的素數(shù)有無窮多個。2 .設(shè)a,b是兩個整數(shù)，其中b>0。則存在唯對整數(shù)q,r使得a=bq+r，0?r<b。(6分)證明：存在性.考慮整數(shù)序列：,-3b,-2b,-b,0,b,2b,3b,序列的各項把實數(shù)軸劃分成長度

6、為b的區(qū)間，a一定落在其中的一個區(qū)間中。因此，存在一個整數(shù)q使得qb?a<(q+1)b，即0?a-bq<b。令r=a-bq,則有a=bq+r,0?r<b。唯一性.假設(shè)還有一對整數(shù)q1,r1也滿足：a=bq1+r1，0?r1<b。(2)(1) 和(2)兩式相減得b(q-q1)=-(r-r1)。(3)當(dāng)q?q1時，(3)式左邊的絕對值大于等于b,而右邊的絕對值小于b,得到矛盾。故q=q，r=r。3 .設(shè)p,q是兩個不同的奇素數(shù)，n=pq,a是與pq互素的整數(shù)。整數(shù)e和d滿足(e,?(n)=1,ed?1(mod?(n),1<e<?(n),1?d<?(n)。證

7、明：對任意整數(shù)c,1?c<n,若ae?c(modn)，則有cd?a(modn)。(12分)證明：因為(e,?(n)=1,根據(jù)2.3定理4,存在整數(shù)d,Kd<?(n),使得ed=1(mod?(n)因此，存在一個正整數(shù)k使得ed=1+k?(n)。由，a與n=pq互素知，(a,p)=1根據(jù)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是不同的素數(shù)，根據(jù)2.1定理12，edae=a(modn)因此，cd=(ae)d=a(mo

8、dn)4證明：設(shè)p和q是兩個不相等的素數(shù)，證明：pq1qp11(modpq)。(6分)證明：因為p和q是兩個不相等的素數(shù)，由Euler定理，qp11modp，pq11modq，所以pq1qp11modp,pq1qp11modq，而p,q1，因此pq1qp11modpq。四計算題(寫出詳細計算過程)：(共30分)1用模重復(fù)平方法計算12996227(mod37909)。(6分)設(shè)m=37909,b=12996,令a=1,將227寫成二進制，227=1+2+25+26+27運用模重復(fù)平方法，我們依次計算如下:(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習(xí)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.設(shè)a=1859,b=1573，運用廣義歐幾里得除法(8分)(1)計算(a,b)；(2)求整數(shù)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