《信息安全原理与技术》(第2版)习题答案 下载本文

1 2 3 4 5 6 7 8 3 4 1 1 1 1 1 4 0 1 -4 5 -9 14 -23 37 1 -3 13 -16 29 -45 74 -119 550 119 74 45 29 16 13 3 1 -4 5 -9 14 -23 37 -171 -3 13 -16 29 -45 74 -119 550 119 74 45 29 16 13 3 1 根据扩展欧几里德算法逆元是550

2.9、用快速指数模运算方法计算200837 mod 77和319971 mod 77

解:由于gcd(2008,77)?1,且77?7?11,?(7)?6,?(11)?10,[?(7),?(11)]?3037?7mod30,由欧拉定理可知200837?20087mod77,设a为指数,计算过程如下:a?6时,2008?6mod77a?3时,20082?36mod77a?2时,6?36?216?62mod77a?1时,362?64mod77a?0时,64?62?3968?41mod77,所以200837?20087mod77?41mod77解:由于gcd(3,77)?1,且77?7?11,?(7)?6,?(11)?10,[?(7),?(11)]?3019971?21mod30,由欧拉定理知319971?321mod77,由21??10101?2得32?9, 31?90?3(mod77)9?4,3?4?12(mod77)42?16,12?160?12(mod77)162?25,12?251?69(mod77).即319971?69mod77

2.10、用费马定理求3201 (mod 11)

21

解:由于gcd(3,11)?1,那么由费马定理得310=311-1?1mod11,那么3201?3?3200mod11?3?(310mod11)?(310mod11)?........(310mod11)mod11

???????????????????共20个?3mod11?3

2.11、计算下面欧拉函数;

(1) ?(41) 、?(27)、?(231) 、?(440)

解:(?41)=41-1=40?(27)=?(33)=33?32?18

?(231)??(3?7?11)??(3)??(7)??(11)?(3?1)?(7?1)?(11?1)?120?(440)??(23?5?11)?(23?22)?(5?1)?(11?1)?160

5

(2) φ(2)φ(6)和φ(3)φ(4),哪一个等于φ(12)。

解:?(2)?(6)??(2)??(2)??(3)?1?1?2?2?(3)?(4)??(3)?(22)?2?(22?2)?4?(12)??(3?2)??(3)?(2)?2?(2?2)?4显然?(3)?(4)??(12)222

2.12、求解下列一次同余方程 (1)3x≡10(mod 29)

解 因为(3,29)=1,所以方程有惟一解。利用辗转相除法求得使3x+29y=1成立的x、y为x=10,y=-1。于是3·10+29·(-1)=1,3·100+29·(-10)=10,所以x≡100≡13(mod 29)。 (2)40x≡191(mod 6191)

解 因为(40,6191)=1,所以方程有惟一解。利用辗转相除法求得使40x+6191y=1成立的x、y为x=1393,y=-9。于是40·1393+6191·(-9)=1,40·1393·191+6191·(-9·191)=191,所以x≡1393·191≡6041(mod 6191) (3)258x≡131(mod 348)

解 因为(258, 348)=6,而6 131,所以方程无解。

2.13、证明下面结论

设a、b、c、d为整数,m为正整数,若a≡b(mod m),c≡d(mod m),则: (1)ax+cy≡bx+dy(mod m),x、y为任意整数; (2)ac≡bd(mod m);

(3)an≡bn(mod m),n>0;

(4)f(a)≡f(b)(mod m),f(x)为任一整系数多项式。

证明 (1)因为a≡b(mod m),c≡d(mod m),所以m|(a-b),m|(c-d),于是m|((a-b)x+(c-d)y),即m|((ax+cy)-(bx+dy)),故ax+cy≡bx+dy(mod m)。

(2)因为a≡b(mod m),c≡d(mod m),所以m|(a-b),m|(c-d),于是m|((a-b)c+(c-d)b),即m|(ac-bd),故ac≡bd(mod m)。

(3)因为a≡b(mod m),则存在整数q使得a-b=mq。于是:

an-bn=(b+mq)n-bn=(bn+bn-1(mq)1+…+b1(mq)n-1+(mq)n)-bn=mp,其中p是一整数。

所以an≡bn(mod m)。 (4)由(1)和(3)可证。

2.14、求满足下面同余方程的解

x≡1(mod 5),x≡5(mod 6),x≡4(mod 7),x≡10(mod 11)

解:令m1=5,m2=6,m3=7,m4=11,b1=1,b2=5,b3=4,b4=10。则m=2310,M1=462,M2=385,M3=330,M4=210。

利用辗转相除法求得M1?=-2,M2?=1,M3?=1,M4?=1。 所以,x≡1·(-2)·462+5·1·385+ 4·1·330+10·1·210≡4421≡2111(mod 2310)

2.15、求Z5中各非零元素的乘法逆元。 解:1-1=1,2-1=3,3-1=2,4-1=4

6

2.16、类似于表2.2,用表列出有限域GF(5)中的加法和乘法运算 解:表如下: 0 1 2 加法 0 1 2 3 4 乘法 0 1 2 3 4 a 0 1 2 3 4 -a 0 4 3 2 1 a-1 -- 1 3 2 4 0 1 2 3 4 0 0 0 0 0 0 1 2 3 4 0 1 0 1 2 3 4 2 0 2 4 1 3 2 3 4 0 1 3 3 4 0 1 2 3 0 3 1 4 2 4 4 0 1 2 3 4 0 4 3 2 1 2.17、对于系数在Z10上的取值的多项式运算,分别计算

a?、x+2)-(x2+5)=-x2+7x-3mod(10x2+10x+10)=9x2+7x+7

b、(6x2?x?3)?(5x2?2)?(30x4?5x3?27x2?2x?6)mod(10x4?5x3?27x2?2x?6)?5x3?7x2?2x?6

2.18、假设f(x)=x3+x+1在GF(2n)中是一个不可约多项式,a(x)=2x2+x+2,b(x)=2x2+2x+2,求a(x)b(x)

解:a(x)?b(x)=a(x)b(x)modf(x)?(2x2+x+2)(2x2+2x+2)mod(x3+x+1)=6x+6x+2x+432

2.19、编程实现模n的快速指数运算。 #include \#include #include

int main(int argc, char* argv[]) { int m,e,n; printf(\ cin>>e;

7

printf(\ cin>>m; printf(\ cin>>n; int a=e,b=m,c=1; for(a=e;a>0; ) { if(a%2==1) { a-=1; c=(c*b)%n; if(a==0) cout<

2.20、编写实现扩展欧几里德算法求最大公因子和乘法逆元。#include \#include

int main(int argc, char* argv[]) { int m,d; cout<<\ first number:\ cin>>m; cout<<\ cin>>d; int a[3]={1,0,m},b[3]={0,1,d}; int Q; if(b[2]%a[2]>=0) { Q=b[2]/a[2]; for(int i=0;i<=2;i++) { int t[3]; t[i]=a[i]-Q*b[i]; a[i]=b[i]; b[i]=t[i];

8