06本科信安上b卷答案

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

1、武汉大学计算机学院2007-2008学年第一学期“信息安全数学基础（上）”(B卷)答案一．计算题（每小题10分，共60分）。1求整数s和t，使得s987+t2668=(987,2668)。解：因为2668=987*2+694，987=694+293，694=293*2+108，293=108*2+77，108=77+31，77=31*2+15，31=15*2+1；所以1=31-15*2=31*5-77*2=108*5-77*7=108*19-293*7=694*19-293*45=694*64-987*45=26

2、68*64-987*173即s=-173,t=64,(a,b)=1.(注意，此题答案不唯一)2求解同余式x5≡5（mod16）。解首先求出同余式x5≡5（mod2）的解为同余式x≡1（mod2），依次求出同余式x5≡5（mod4）的解为x≡1（mod4），同余式x5≡5（mod8）的解为x≡5（mod8），同余式x5≡5（mod16）的解为x≡5（mod16）。3求解同余式x2+x+7≡0（mod27）。解因为（4，27）=1，所以由同余式的性质可以得到4x2+4x+28≡0（mod27），即4x2+4x+1≡0

3、（mod27），于是（2x+1）2≡0（mod27），因此2x+1≡0（mod9）,利用一次同余式的求解方法得x≡4（mod9）,所以原同余式的解为x≡4，13，22（mod27）。4求模37的所有原根，并且求解如下高次剩余x4≡34(mod37)。解因为，所以只需验证模37是否为1即可，逐个计算可得：，故2是模37的原根。当时，是模37的原根，所以模37的所有原根为2，32，17，13，15，18，35，5，20，24，22，19。令因为，于是，，所以。5求乘法逆元素（1）；（2）解（1）因为37=7*5+2，

4、7=2*3+1，所以1=7-2*3=7-（37-7*5）*3=7*16-37*3，于是；（2）因为401=113*4-51，113=51*2+11，51=11*5-4，11=4*3-1，所以1=4*3-11=11*14-51*3=113*14-51*31=401*31-113*110，于是。6分别用模4和模5的完全剩余系和简化剩余系来表示模20的完全剩余系和简化剩余系。解取模4的一组完全剩余系为0,1,2,3，取模5的一组完全剩余系为0,1,2,3,4，则有模20的一组完全剩余系为0,4,8,12,16,5,9,

5、13,17,21,10,14,18,22,26,15,19,23,27,31。取模4的一组简化剩余系为1,3，取模5的一组简化剩余系为1,2,3,4，则得模20的一组简化剩余系为9,13,17,21,19,23,27,31。二.证明题（每题10分，共20分）(1)证明：对于任意素数而言，若或，则就是该同余式的解，否则，因为，且，，均为1或-1，所以，，三个数中一定有一个为1，不妨设为，即2为模的平方剩余，因此同余式有解，即同余式有解，因此同余式（x2-2）(x2-17)(x2-34)≡0(modp)有解。(2)证

6、设是模的平方剩余，则同余式的解等价于同余式组的解，上述同余式组的解为，，，，利用中国剩余定理，很容易求出上述一次同余式组的解分别为其中，，这些就是同余式的四个解。因为和中一定有一个是模的平方剩余，和中一定有一个是模的二次剩余，又因为，，所以中有且仅有一个既是模的平方剩余，又是模的平方剩余，即为模的原平方根。三.证明题（共一题，20分）解算法1Miller-Rabin概率素性测试MILLER-RABIN(n,t)输入：奇数和安全参数。输出：对于问题“是素数？”，回答“素数”或“合数”。(1)写出，其中是奇数。(2)

7、对从1到，执行如下操作：(2.1)随机选择一个整数，；(2.2)计算；(2.3)若且，则作如下操作：；当和时，作如下操作：计算；若，则返回“合数”；；若，则返回“合数”；(3)返回“素数”。算法11-2Lehmann方法(1)选择一个小于的随机数；(2)计算；(3)如果，那么肯定不是素数；(4)如果或，那么不是素数的可能性至多是1/2；算法3Solovay-Strassen概率素性测试SOLOVAY-STRASSEN输入：奇数，安全参数。输出：对于问题“是素数？”回答“素数”或“合数”。(1)对从1到作如下操作：

8、(1.1)随机选择一个整数，。(1.2)计算。(1.3)若且，则返回“合数”。(1.4)计算雅可比符号。(1.5)若，则返回“合数”。(2)返回“素数”。