信息安全数学基础期末考试试卷及答案(A卷)

1装订线信息安全数学基础期末考试试卷及答案（A卷）一、填空题（本大题共8小题，每空2分，共24分）1.两个整数a，b，其最大公因数和最小公倍数的关系为________________。2.给定一个正整数m，两个整数a,b叫做模m同余，如果______________，记作(mod)abm；否则，叫做模m不同余，记作_____________。3.设m，n是互素的两个正整数，则()mn________________。4.设1m是整数，a是与m互素的正整数。则使得1(mod)eam成立的最小正整数e叫做a对模m的指数，记做__________。如果a对模m的指数是()m，则a叫做模m的____________。5.设n是一个奇合数，设整数b与n互素，如果整数n和b满足条件________________，则n叫做对于基b的拟素数。6.设,GG是两个群，f是G到G的一个映射。如果对任意的,abG，都有_______________，那么f叫做G到G的一个同态。7.加群Z的每个子群H都是________群，并且有0H或H______________。8.我们称交换环R为一个域，如果R对于加法构成一个______群，*\{0}RR对于乘法构成一个_______群。二、计算题（本大题共3小题，每小题8分，共24分）1.令1613,a3589b。用广义欧几里德算法求整数,st，使得(,)satbab。得分得分2装订线2.求同余方程22(mod67)x的解数。3.计算3模19的指数19ord(3)。三、解同余方程（本大题共2小题，每小题10分，共20分）1.求解一次同余方程1714(mod21)x。得分3装订线2.解同余方程组2(mod3)3(mod5)2(mod7)xxx四、证明题（本大题共3小题，每小题7分，共21分）1.证明：如果a是整数，则3aa能够被6整除。得分4装订线2.f是群G到G的一个同态，ker|,()faaGfae，其中e是G的单位元。证明：kerf是G的正规子群。3.证明：如果p和q是不同的素数，则111(mod)qppqpq。5装订线五、应用题（共11分）RSA公钥加密算法的密钥生成步骤如下：选择两个大的素数p和q，计算n=pq。选择两个正整数e和d，满足：ed=1(mod()n)。Bob的公钥是（n，e），对外公布。Bob的私钥是d，自己私藏。如果攻击者分解n得到p=47，q=23，并且已知e=257，试求出Bob的私钥d。得分6装订线答案一、填空题（每空2分，共24分）1.两个整数a，b，其最大公因数和最小公倍数的关系为[,](,)ababab。2.给定一个正整数m，两个整数a,b叫做模m同余，如果|mab，记作(mod)abm；否则，叫做模m不同余，记作a(mod)bm。3.设m，n是互素的两个正整数，则()mn()()mn。4.设1m是整数，a是与m互素的正整数。则使得1(mod)eam成立的最小正整数e叫做a对模m的指数，记做()morda。如果a对模m的指数是()m，则a叫做模m的原根。5.设n是一个奇合数，设整数b与n互素，如果整数n和b满足条件11(mod)nbn，则n叫做对于基b的拟素数。6.设,GG是两个群，f是G到G的一个映射。如果对任意的,abG，都有()()()fabfafb，那么f叫做G到G的一个同态。7.加群Z的每个子群H都是循环群，并且有0H或H()mmZ或。8.我们称交换环R为一个域，如果R对于加法构成一个交换群，*\{0}RR对于乘法构成一个交换群。二、计算题(每题8分，共24分)1.解：3589=2*1613+3631613=4*363+161363=2*161+41161=3*41+3841=1*38+338=12*3+23=1*2+12=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)7装订线=-14*161+55*(363-2*161)=55*363+(-124)*(1613-4*363)=(-124)*1613+551*(3589-2*1613)=551*3589+(-1226)*1613所以s=-1226t=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是67的平方剩余所以x2≡-2(mod67)有2个解。3.解：因为(19)=18,所以只需对18的因数d=1,2,3,6,9,18计算ad(mod19)因为31≡3,32≡9,33≡8,36≡7,39≡-1,218≡1(mod19)所以3模19的指数为18；三、解同余方程（每题10分，共20分）1.解：因为（17，21）=1|14故原同余式有解。又17x≡1（mod21，所以特解x0'≡5（mod21）。同余式17x≡14（mod21）的一个特解为x0≡14*x0'=14*5≡7（mod21）所有解为：x≡7（mod21）2.解：令1233,5,7mmm，3*5*7105m，1235*735,3*721,3*515MMM。分别求解同余式1(mod)iiiMMm（i=1,2,3）得到12M，21M，31M。故同余式的解为112233*2*3*2(mod105)2*35*21*21*31*15*2(mod105)23(mod105)xMMMMMM四、证明题（每题7分，共21分）1.证明：因为a3-a=(a-1)a(a+1)当a=3k，kZ3|a则3|a3-a当a=3k-1，kZ3|a+1则3|a3-a当a=3k+1，kZ3|a-1则3|a3-a所以a3-a能被3整除。又因为(a-1)，a，(a+1)是3个连续的整数，所以至少有一个是偶数，从而2|a3-a。因此，a3-a能够被6整除。8装订线2.证明：因为(p,q)=1p,q都为素数所以(p)=p-1,(q)=q-1由Euler定理知：p(q)≡1(modq)q(p)≡1(modp)即pq-1≡1(modq)qp-1≡1(modp)又qp-1≡0(modq)pq-1≡0(modp)所以pq-1+qp-1≡1(modq)qp-1+pq-1≡1(modp)又[p,q]=pq所以pq-1+qp-1≡1(modpq)3.证明：对任意,kerabf，有(),()faefbe，从而，1111()()()()()()()fabfafbfafbfafae。因此，kerbf，kerf是群G的子群。对任意aG,kerbf,我们有1111()()()()()()()()fabafafbfafaefafafae。这说明1kerabaf。从而，kerf是群G的正规子群。五(11分)解：p=47，q=23，n=pq=1081.所以，()(4723)(47)(23)46221012n。要求Bob的私钥d，即解同余式257d=1(mod1012).利用欧几里得算法解得该同余式的解为949。故Bob的私钥是d=949.