06本科信安上B卷答案new.docVIP

武汉大学计算机学院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=2668*64-987*173 即s=-173,t=64,(a,b)=1.(注意，此题答案不唯一) 2 求解同余式x5≡5（mod 16）。 解 首先求出同余式x5≡5（mod 2）的解为同余式x≡1（mod 2），依次求出同余式x5≡5（mod 4）的解为x≡1（mod 4），同余式x5≡5（mod 8）的解为x≡5（mod 8），同余式x5≡5（mod 16）的解为x≡5（mod 16）。 求解同余式x2+x+7≡0（mod 27）。 解 因为（4，27）=1，所以由同余式的性质可以得到 4x2+4x+28≡0（mod 27），即4x2+4x+1≡0（mod 27），于是 （2x+1）2≡0（mod 27），因此2x+1≡0（mod 9）,利用一次同余式的求解方法得x≡4（mod 9）,所以原同余式的解为 x≡4，13，22（mod 27）。 4 求模37的所有原根，并且求解如下高次剩余x4≡34(mod 37)。 解 因为，所以只需验证 模是否为1即可，逐个计算可得 ， 故是模的原根。当时，是模的原根，所以模的所有原根为因为，于是，，所以。 5 求乘法逆元素（1）；（2） 解 （1）因为37=7*5+2，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,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(mod p)有解。 (2) 证 设是模的平方剩余，则同余式的解等价于同余式组 的解，上述同余式组的解为 ，， ，， 利用中国剩余定理，很容易求出上述一次同余式组的解分别为 其中，，这些就是同余式的四个解。 因为和中一定有一个是模的平方剩余，和中一定有一个是模的二次剩余，又因为，，所以中有且仅有一个既是模的平方剩余，又是模的平方剩余，即为模的原平方根。和安全参数。 输出：对于问题“是素数？”，回答“素数”或“合数”。 (1)写出，其中是奇数。 (2)对从1到，执行如下操作： (2.1) 随机选择一个整数，； (2.2) 计算； (2.3) 若且，则作如下操作： ； 当和时，作如下操作： 计算； 若，则返回“合数”； ； 若，则返回“合数”； (3)返回“素数”。 算法11-2 Lehmann方法 (1)选择一个小于的随机数； (2)计算； (3)如果，那么肯定不是素数； (4)如果或，那么不是素数的可能性至多是1/2； 算法3 Solovay-Strassen概率素性测试 SOLOVAY-STRASSEN 输入：奇数，安全参数。 输出：对于问题“是素数？”回答“素数”或“合数”。 (1)对从1到作如下操作： (1.1)随机选择一个整数，。 (1.2)计算。 (1.3)若且，则返回“合数”。 (1.4)计算雅可比符号。 (1.5)若，则返回“合数”。 (2)返回“素数”。