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

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

《信息安全数学基础期末考试试卷及答案(A卷).doc》由会员分享，可在线阅读，更多相关《信息安全数学基础期末考试试卷及答案(A卷).doc（8页珍藏版）》请在冰点文库上搜索。

装订线

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

得分

一、填空题（本大题共8小题，每空2分，共24分）

1.两个整数a，b，其最大公因数和最小公倍数的关系为________________。

2.给定一个正整数m，两个整数a,b叫做模m同余，如果______________，记作；否则，叫做模m不同余，记作_____________。

3.设m，n是互素的两个正整数，则________________。

4.设是整数，a是与m互素的正整数。

则使得成立的最小正整数叫做a对模m的指数，记做__________。

如果a对模m的指数是，则a叫做模m的____________。

5.设n是一个奇合数，设整数b与n互素，如果整数n和b满足条件________________，则n叫做对于基b的拟素数。

6.设是两个群，f是到的一个映射。

如果对任意的，都有_______________，那么f叫做到的一个同态。

7.加群Z的每个子群H都是________群，并且有或______________。

8.我们称交换环R为一个域，如果R对于加法构成一个______群，对于乘法构成一个_______群。

得分

二、计算题（本大题共3小题，每小题8分，共24分）

1.令。

用广义欧几里德算法求整数，使得。

2.求同余方程的解数。

3.计算3模19的指数。

得分

三、解同余方程（本大题共2小题，每小题10分，共20分）

1.求解一次同余方程。

2.解同余方程组

得分

四、证明题（本大题共3小题，每小题7分，共21分）

1.证明：

如果是整数，则能够被6整除。

2.是群到的一个同态，，其中是的单位元。

证明：

是的正规子群。

3.证明：

如果和是不同的素数，则。

得分

五、应用题（共11分）RSA公钥加密算法的密钥生成步骤如下：

选择两个大的素数p和q，计算n=pq。

选择两个正整数e和d，满足：

ed=1（mod）。

Bob的公钥是（n，e），对外公布。

Bob的私钥是d，自己私藏。

如果攻击者分解n得到p=47，q=23，并且已知e=257，试求出Bob的私钥d。

答案

一、填空题（每空2分，共24分）

1.两个整数a，b，其最大公因数和最小公倍数的关系为。

2.给定一个正整数m，两个整数a,b叫做模m同余，如果，记作；否则，叫做模m不同余，记作。

3.设m，n是互素的两个正整数，则。

4.设是整数，a是与m互素的正整数。

则使得成立的最小正整数叫做a对模m的指数，记做。

如果a对模m的指数是，则a叫做模m的原根。

5.设n是一个奇合数，设整数b与n互素，如果整数n和b满足条件，则n叫做对于基b的拟素数。

6.设是两个群，f是到的一个映射。

如果对任意的，都有，那么f叫做到的一个同态。

7.加群Z的每个子群H都是循环群，并且有或。

8.我们称交换环R为一个域，如果R对于加法构成一个交换群，对于乘法构成一个交换群。

二、计算题（每题8分，共24分）

1.解：

3589=2*1613+363

1613=4*363+161

363=2*161+41

161=3*41+38

41=1*38+3

38=12*3+2

3=1*2+1

2=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）

=-14*161+55*（363-2*161）

=55*363+（-124）*（1613-4*363）

=（-124）*1613+551*（3589-2*1613）

=551*3589+（-1226）*1613

所以s=-1226t=551

2.解：

因为（-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.解：

令，，

。

分别求解同余式（i=1,2,3）

得到，，。

故同余式的解为

四、证明题（每题7分，共21分）

1.证明：

因为a3-a=（a-1）a（a+1）

当a=3k，kZ3|a则3|a3-a

当a=3k-1，kZ3|a+1则3|a3-a

当a=3k+1，kZ3|a-1则3|a3-a

所以a3-a能被3整除。

又因为（a-1），a，（a+1）是3个连续的整数，所以至少有一个是偶数，

从而2|a3-a。

因此，a3-a能够被6整除。

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.证明：

对任意，有，从而，

。

因此，，是群的子群。

对任意,,我们有

。

这说明。

从而，是群的正规子群。

五（11分）

解：

p=47，q=23，n=pq=1081.所以，

。

要求Bob的私钥d，即解同余式257d=1（mod）.

利用欧几里得算法解得该同余式的解为949。

故Bob的私钥是d=949.

8