信息安全數(shù)學(xué)基礎(chǔ)期末考試試卷及答案(A卷)

信息安全數(shù)學(xué)基礎(chǔ)期末考試試卷及答案（A卷）得分一、 填空題（本大題共8小題，每空2分，共24分）1. 兩個(gè)整數(shù)a，b，其最大公因數(shù)和最小公倍數(shù)的關(guān)系為 _。2. 給定一個(gè)正整數(shù)m，兩個(gè)整數(shù)a,b叫做模m同余，如果_，記作；否則，叫做模m不同余，記作_。3. 設(shè)m，n是互素的兩個(gè)正整數(shù)，則_。4. 設(shè)是整數(shù)，a是與m互素的正整數(shù)。則使得成立的最小正整數(shù)叫做a對(duì)模m的指數(shù)，記做_。如果a對(duì)模m的指數(shù)是，則a叫做模m的_。5. 設(shè)n是一個(gè)奇合數(shù)，設(shè)整數(shù)b與n互素，如果整數(shù)n和b滿足條件_，則n叫做對(duì)于基b的擬素?cái)?shù)。6. 設(shè)是兩個(gè)群，f是到的一個(gè)映射。如果對(duì)任意的，都有_，那么f叫做到的一個(gè)同態(tài)。7. 加群Z的每個(gè)子群H都是_群，并且有或_。8. 我們稱交換環(huán)R為一個(gè)域，如果R對(duì)于加法構(gòu)成一個(gè)_群，對(duì)于乘法構(gòu)成一個(gè)_群。得分二、計(jì)算題（本大題共 3小題，每小題8分，共24分）1. 令 。用廣義歐幾里德算法求整數(shù)，使得 。2. 求同余方程的解數(shù)。3. 計(jì)算3模19的指數(shù)。得分三、解同余方程（本大題共2小題，每小題10分，共20分）1. 求解一次同余方程。2. 解同余方程組得分四、證明題（本大題共3小題，每小題7分，共21分）1. 證明：如果是整數(shù)，則能夠被6整除。2. 是群到的一個(gè)同態(tài)，其中是的單位元。證明：是的正規(guī)子群。3. 證明：如果和是不同的素?cái)?shù)，則。得分五、應(yīng)用題（共11分）RSA公鑰加密算法的密鑰生成步驟如下：選擇 兩個(gè)大的素?cái)?shù)p和q，計(jì)算n=pq。選擇兩個(gè)正整數(shù)e和d，滿足：ed=1(mod)。Bob的公鑰是（n，e），對(duì)外公布。Bob的私鑰是d ，自己私藏。如果攻擊者分解n得到p=47，q=23，并且已知e=257，試求出Bob的私鑰d。答案 一、填空題（每空2分，共24分）1. 兩個(gè)整數(shù)a，b，其最大公因數(shù)和最小公倍數(shù)的關(guān)系為。2. 給定一個(gè)正整數(shù)m，兩個(gè)整數(shù)a,b叫做模m同余，如果，記作；否則，叫做模m不同余，記作。3. 設(shè)m，n是互素的兩個(gè)正整數(shù)，則。4. 設(shè)是整數(shù)，a是與m互素的正整數(shù)。則使得成立的最小正整數(shù)叫做a對(duì)模m的指數(shù)，記做。如果a對(duì)模m的指數(shù)是，則a叫做模m的 原根 。5. 設(shè)n是一個(gè)奇合數(shù)，設(shè)整數(shù)b與n互素，如果整數(shù)n和b滿足條件，則n叫做對(duì)于基b的擬素?cái)?shù)。6. 設(shè)是兩個(gè)群，f是到的一個(gè)映射。如果對(duì)任意的，都有，那么f叫做到的一個(gè)同態(tài)。7. 加群Z的每個(gè)子群H都是 循環(huán) 群，并且有或。8. 我們稱交換環(huán)R為一個(gè)域，如果R對(duì)于加法構(gòu)成一個(gè) 交換 群，對(duì)于乘法構(gòu)成一個(gè) 交換 群。二、計(jì)算題(每題8分，共24分)1. 解： 3589=2*1613+363 1613=4*363+161 363=2*161+41 161=3*41+38 41=1*38+3 38=12*3+2 3=1*2+1 2=2*1 (a,b)=1,從而 1=3-1*2 =3-1*(38-12*3) =-38+13*(41-1*38) =13*41-14*(161-3*41) =-14*161+55*(363-2*161) =55*363+(-124)*(1613-4*363) =(-124)*1613+551*(3589-2*1613) =551*3589+(-1226)*1613 所以s=-1226 t=5512. 解：因?yàn)椋?2/67）=(65/67) =(13/67)(5/67) =(-1)12*66/4(-1)4*66/4(2/13)(2/5) =1*1*(-1)(13*13-1)/8(-1)(5*5-1)/8 =-1*(-1)=1 所以-2是67的平方剩余 所以x2-2(mod67)有2個(gè)解。3. 解：因?yàn)?19)=18,所以只需對(duì)18的因數(shù)d=1,2,3,6,9,18計(jì)算ad(mod19) 因?yàn)?13, 329, 338, 367, 39-1, 2181(mod19) 所以3模19的指數(shù)為18；三、解同余方程（每題10分，共20分）1. 解：因?yàn)椋?7，21）=1 | 14 故原同余式有解。 又17x1（mod21，所以 特解x05（mod21）。 同余式17x14（mod21）的一個(gè)特解為x014*x0=14*57（mod21） 所有解為：x7（mod21）2. 解：令， ，。 分別求解同余式（i=1,2,3） 得到，。故同余式的解為四、證明題（每題7分，共21分）1. 證明：因?yàn)閍3-a=(a-1)a(a+1) 當(dāng)a=3k，kZ 3|a 則3|a3-a 當(dāng)a=3k-1，kZ 3|a+1 則3|a3-a 當(dāng)a=3k+1，kZ 3|a-1 則3|a3-a 所以a3-a能被3整除。 又因?yàn)?a-1)，a，(a+1)是3個(gè)連續(xù)的整數(shù)，所以至少有一個(gè)是偶數(shù)， 從而 2|a3-a。因此，a3-a能夠被6整除。2. 證明：因?yàn)?p,q)=1 p,q都為素?cái)?shù) 所以(p)=p-1, (q)=q-1 由Euler定理知：p(q)1(modq) q(p)1(modp) 即pq-11(modq) qp-11(modp) 又 qp-10(modq) pq-10(modp) 所以pq-1+qp-11(modq) qp-1+pq-11(modp) 又p,q=pq 所以pq-1+qp-11(modpq)3. 證明：對(duì)任意，有，從而，。因此，是群的子群。 對(duì)任意,我們