1、裝訂線信息安全數學基礎期末考試試卷及答案（A卷）得分一、 填空題（本大題共8小題，每空2分，共24分）1. 兩個整數a，b，其最大公因數和最小公倍數的關系為 _。2. 給定一個正整數m，兩個整數a,b叫做模m同余，如果_，記作；否則，叫做模m不同余，記作_。3. 設m，n是互素的兩個正整數，則_。4. 設是整數，a是與m互素的正整數。則使得成立的最小正整數叫做a對模m的指數，記做_。如果a對模m的指數是，則a叫做模m的_。5. 設n是一個奇合數，設整數b與n互素，如果整數n和b滿足條件_，則n叫做對于基b的擬素數。6. 設是兩個群，f是到的一個映射。如果對任意的，都有_，那么f叫做到的一個同態(tài)

2、。7. 加群Z的每個子群H都是_群，并且有或_。8. 我們稱交換環(huán)R為一個域，如果R對于加法構成一個_群，對于乘法構成一個_群。得分二、計算題（本大題共 3小題，每小題8分，共24分）1. 令 。用廣義歐幾里德算法求整數，使得 。2. 求同余方程的解數。3. 計算3模19的指數。得分三、解同余方程（本大題共2小題，每小題10分，共20分）1. 求解一次同余方程。2. 解同余方程組得分四、證明題（本大題共3小題，每小題7分，共21分）1. 證明：如果是整數，則能夠被6整除。2. 是群到的一個同態(tài)，其中是的單位元。證明：是的正規(guī)子群。3. 證明：如果和是不同的素數，則。得分五、應用題（共11分）R

3、SA公鑰加密算法的密鑰生成步驟如下：選擇 兩個大的素數p和q，計算n=pq。選擇兩個正整數e和d，滿足：ed=1(mod)。Bob的公鑰是（n，e），對外公布。Bob的私鑰是d ，自己私藏。如果攻擊者分解n得到p=47，q=23，并且已知e=257，試求出Bob的私鑰d。答案 一、填空題（每空2分，共24分）1. 兩個整數a，b，其最大公因數和最小公倍數的關系為。2. 給定一個正整數m，兩個整數a,b叫做模m同余，如果，記作；否則，叫做模m不同余，記作。3. 設m，n是互素的兩個正整數，則。4. 設是整數，a是與m互素的正整數。則使得成立的最小正整數叫做a對模m的指數，記做。如果a對模m的指數

4、是，則a叫做模m的 原根 。5. 設n是一個奇合數，設整數b與n互素，如果整數n和b滿足條件，則n叫做對于基b的擬素數。6. 設是兩個群，f是到的一個映射。如果對任意的，都有，那么f叫做到的一個同態(tài)。7. 加群Z的每個子群H都是 循環(huán) 群，并且有或。8. 我們稱交換環(huán)R為一個域，如果R對于加法構成一個 交換 群，對于乘法構成一個 交換 群。二、計算題(每題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*

5、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. 解：因為（-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是6

6、7的平方剩余 所以x2-2(mod67)有2個解。3. 解：因為(19)=18,所以只需對18的因數d=1,2,3,6,9,18計算ad(mod19) 因為313, 329, 338, 367, 39-1, 2181(mod19) 所以3模19的指數為18；三、解同余方程（每題10分，共20分）1. 解：因為（17，21）=1 | 14 故原同余式有解。 又17x1（mod21，所以 特解x05（mod21）。 同余式17x14（mod21）的一個特解為x014*x0=14*57（mod21） 所有解為：x7（mod21）2. 解：令， ，。 分別求解同余式（i=1,2,3） 得到，。故同余式

7、的解為四、證明題（每題7分，共21分）1. 證明：因為a3-a=(a-1)a(a+1) 當a=3k，kZ 3|a 則3|a3-a 當a=3k-1，kZ 3|a+1 則3|a3-a 當a=3k+1，kZ 3|a-1 則3|a3-a 所以a3-a能被3整除。 又因為(a-1)，a，(a+1)是3個連續(xù)的整數，所以至少有一個是偶數， 從而 2|a3-a。因此，a3-a能夠被6整除。2. 證明：因為(p,q)=1 p,q都為素數 所以(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. 證明：對任意，有，從而，。因此，是群的子群。 對任意,我們有