06本科信安上a卷答案

《06本科信安上a卷答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、武汉大学计算机学院2007-2008学年第一学期“信息安全数学基础（上）”(A卷)答案一计算题（每题10分，共60分）。1求整数s和t，使得793s+2769t=(793,2769)。解：因为2769=793*3+390，793=390*2+13，390=13*30，即(793,2769)=13，而13=793-390*2=793-(2769-793*3)*2=793*7-2769*2即s=7,t=-2;(注意，此题答案不唯一)23148413mod113。解因为，48413=112*432+29，所以3148413mod113=3129mod113，(29

2、)10=(11101)2，于是m0=1,a0=31,b0=31,m1=0,a1=57,b1=31,m2=1,a2=85,b2=36,m3=1,a3=106,b3=87,m4=1,a4=49,b4=82所以3148413mod113=823求解同余式x3+5x2+9≡0（mod27）。解对于，有，直接验算，知同余式有两个解。因为，所以，对于，依次求出对应的同余式的解：，；其次，计算，，最后，计算。因此，对应于的同余式的解为；对于，因为，所以都是同余式的解。进一步，对于，因为，所以没有对应的解；对于，因为，所以都是同余式对应于的解；对于，因为，所以都是同余式对应

3、于的解。即同余式的解为。4判断同余式x2≡37(mod101)是否有解？有解时求出其所有解。解因为101为奇素数，且，故同余式有解，解数为2。因为，且101-1=100=2*2*25所以容易由公式计算出该同余式的解为。5求模31的所有原根，并且求解如下高次剩余x6≡2(mod31)。解由原根的判断方法计算，26mod31=2,210mod31=1，36mod31=16,310mod31=25，315mod31=30,所以模31的最小原根为3，其他的所有原根分别为3，17，13，24，22，12，11，21。因为324mod31=2，令，则有，所以，于是所以。

4、6（1）求相邻的四个整数，它们依次可被4，9，25，49整除；（2）求13的倍数，使得该数被3，5，7，11除的余数是2。`解（1）设最小的一个数为x，则，由中国剩余定理易解得；（2）设这个数为13x，则，，，，由中国剩余定理易解得。二.证明题（每题10分，共20分）（1）设a,b为异奇偶的正整数，且(a,b)=1，证明(a2+b2,a+b)=1;证明：因为a2+b2=(a+b)a+b(b-a)，所以(a2+b2,a+b)=(a+b,b(b-a))，又因为a+b=b+a，所以(a+b,b)=(b,a)=(a,b)=1,从而(a2+b2,a+b)=(a+b,b

5、(b-a))=(a+b,a-b)=(a+b,2b)=(a+b,2)=1.(最后一步用到了a,b异奇偶的条件)（2）设是正整数，，记集合。现对集合中的每个数涂上黑色或白色，要满足以下条件：（1）要涂上同一种颜色；（2）当时，要涂上同一种颜色。证明：所有的数一定都涂上同一种颜色。证我们的想法是把要涂色的集合扩充到全体整数，除已知两条外另外满足：（3）属于模的同一个剩余类中的数涂上相同的颜色；（4）要涂上同一种颜色。这样就可以对全体整数涂色，这样的涂色应该满足如下性质：①对任意的整数，一定涂相同的颜色。因为对于任意的整数，必存在整数，使得，由（3）知同色；而，所以

6、由（3）知同色，从而由（1）和（4）知同色。②对任意的整数，同色，从而属于模的同一个剩余类中的数涂上相同的颜色。因为对于任意的整数，必存在整数，使得，由（3）知同色，而由（2）知同色，进而由①知，同色，进而推出同色；由条件（3）知，属于模的同一个剩余类中的数同色，因为，所以，因此同色，从而同色。由①和②知，对于任意的整数，同色，其中为任意的整数。由条件知，存在整数，使得，所以同色，即所有整数同色。三.解首先令为14，，则，，，所以。