2025年大学《数理基础科学》专业题库—— 数论在密码学算法中的应用.docxVIP

2025年大学《数理基础科学》专业题库——数论在密码学算法中的应用

考试时间：______分钟总分：______分姓名：______

一、选择题（每小题3分，共15分。请将正确选项的字母填在括号内。）

1.设整数a,b,c。如果a|b且a|c，则a一定整除下列哪个式子？

(A)a+b

(B)a-b

(C)bc

(D)b+c

2.如果整数d是a,b的公因数，且d是a,b所有公因数中的最大者，那么d等于多少？

(A)gcd(a,b)

(B)lcm(a,b)

(C)φ(a)

(D)a+b

3.计算gcd(252,198)的过程如下：

252=1×198+54

198=3×54+36

54=1×36+18

36=2×18+0

则gcd(252,198)=18。这个过程使用了哪种算法？

(A)因数分解法

(B)更相减损术

(C)欧几里得算法

(D)二次剩余定理

4.对于整数a,b和正整数n，如果a≡b(modn)，那么下列哪个式子一定成立？

(A)a=b

(B)a+n=b

(C)a-b是n的倍数

(D)n|(a-b)

5.设n是两个不同奇素数p和q的乘积，即n=pq。计算φ(n)=n-(p+q-1)的值等于多少？

(A)1

(B)n-2

(C)(p-1)(q-1)

(D)pq-1

二、填空题（每小题4分，共20分。请将答案填在横线上。）

6.若整数a,b,c满足a|b，则gcd(a,c)与gcd(b,c)之间有怎样的关系？请填入适当符号。

gcd(a,c)______gcd(b,c)

7.模逆元a^(-1)modn是指满足什么条件的整数a？

a^(-1)modn是指存在一个整数a^(-1)，使得a×a^(-1)≡______(modn)。

8.根据欧拉定理，如果整数a与正整数n互质，那么a的欧拉函数φ(n)次方幂a^φ(n)除以n的余数是多少？

a^φ(n)≡______(modn)。

9.在RSA密码体制中，选择两个大奇素数p和q，计算n=pq。n的平方根√n在模n的意义下等于多少？

√n≡______(modn)。

10.设p是奇素数，a是整数，且a不是p的倍数。根据费马小定理，a的p-1次方幂a^(p-1)除以p的余数是多少？

a^(p-1)≡______(modp)。

三、计算题（每小题8分，共32分。请写出详细的计算过程。）

11.使用欧几里得算法计算gcd(3072,1085)，并求出整数x,y使得3072x+1085y=gcd(3072,1085)。

12.计算下列模幂运算：

(a)3^123mod7

(b)5^20mod13

13.设n=35，a=6。判断a是否与n互质。如果互质，求出a模n的逆元。

14.在RSA密码体制中，假设选择素数p=61，q=53。计算n和φ(n)的值。

四、简答题（每小题10分，共30分。请简洁明了地回答问题。）

15.简述欧几里得算法为什么能用于计算两个整数的最大公约数。

16.解释RSA密码体制中，为什么选择两个足够大的素数p和q来构造密钥n是重要的。

17.什么是离散对数问题？它与RSA密码体制的安全性有何关联？

---

试卷答案

一、选择题

1.(C)

2.(A)

3.(C)

4.(C)

5.(C)

二、填空题

6.≥

7.1

8.1

9.0

10.1

三、计算题

11.gcd(3072,1085)=17。

过程：

3072=2×1085+902

1085=1×902+183

902=4×183+150

183=1×150+33

150=4×33+18

33=1×18+15

18=1×15+3

15=5×3+0

所以gcd(3072,1085)=3。

回代求解x,y：

3=18-1×15