信息安全数学基础试题及答案.docxVIP

信息安全数学基础试题

一、选择题（每题3分，共15分）

下列整数中，属于素数的是（）

A.2B.9C.15D.21

若整数a、b满足a≡bmod5，则下列等式一定成立的是（）

A.5|(a+b)B.5|(a-b)C.a=b+5D.a=5b

模7的乘法群Z_7^*的阶是（）

A.5B.6C.7D.8

离散对数问题的核心是在有限域中，已知a、b和m（a与m互素），求解整数x使得（）

A.a+x≡bmodmB.ax≡bmodmC.a^x≡bmodmD.x^a≡bmodm

在RSA密码体制中，公钥e的选择需要满足的条件是（）

A.e与n互素（n为大素数乘积）B.e与φ(n)互素（φ为欧拉函数）

C.enD.e为素数

二、填空题（每题3分，共15分）

欧拉函数φ(18)的值为______。

整数24和36的最大公约数gcd(24,36)=______。

同余方程3x≡6mod9的所有解为______（用模9的剩余类表示）。

模11的一个原根是______。

满足同余方程组\begin{cases}x≡1mod3\\x≡2mod5\end{cases}的最小正整数解为______。

三、计算题（每题10分，共40分）

用欧几里得算法求gcd(45,12)，并将其表示为45和12的整数线性组合。

计算13^{20}mod7的值。

求解同余方程组：\begin{cases}x≡2mod4\\x≡3mod5\end{cases}

求整数23模35的乘法逆元（若存在，写出具体值；若不存在，说明理由）。

四、证明题（每题10分，共20分）

证明：素数有无穷多个。

证明：若整数a、b互素（即gcd(a,b)=1），且a整除bc，则a整除c。

五、应用题（10分）

在信息安全领域，常利用欧拉定理简化模幂运算。

利用欧拉定理计算7^{100}mod15的值；

若某RSA加密系统中，选择两个素数p=11，q=13，求对应的公钥（e,n）和私钥（d,n）（要求e取最小的大于1且满足条件的整数）。

信息安全数学基础试题答案

一、选择题（每题3分，共15分）

A（解析：素数是大于1且除1和自身外无其他正约数的整数，2是唯一的偶素数；9=3×3，15=3×5，21=3×7，均为合数）

B（解析：同余定义为m|(a-b)时，a≡bmodm，故5|(a-b)）

B（解析：Z_m^*表示模m的简化剩余系，元素为与m互素的剩余类，模7的简化剩余系为{1,2,3,4,5,6}，共6个元素，群的阶等于元素个数）

C（解析：离散对数问题核心是已知底数a、结果b和模m，求指数x满足a^x≡bmodm）

B（解析：RSA中e需满足1eφ(n)且gcd(e,φ(n))=1，确保e存在模φ(n)的逆元d）

二、填空题（每题3分，共15分）

6（解析：18=2×3^2，欧拉函数φ(n)=n×\prod_{p|n}(1-\frac{1}{p})，故φ(18)=18×(1-1/2)×(1-1/3)=18×1/2×2/3=6）

12（解析：用欧几里得算法：36=1×24+12，24=2×12+0，故gcd(24,36)=12）

x≡2,5,8mod9（解析：方程两边同除以gcd(3,9)=3，得x≡2mod3，模9的解为2,5,8）

2（解析：φ(11)=10，2的阶：2^1=2≠1，2^2=4≠1，2^5=32≡10≠1，2^{10}≡1mod11，阶为10=φ(11)，故2是模11的原根，答案不唯一，3、6等也可）

7（解析：设x=3k+1，代入x≡2mod5得3k+1≡2mod5→3k≡1mod5→k≡2mod5（因3×2=6≡1mod5），故k=5m+2，x=3(5m+2)+1=15m+7，最小正整数解为7）

三、计算题（每题10分，共40分）

解：用欧几里得算法求gcd(45,12)：

反向推导求线性组合：

45=3×12+9（第一步：被除数=商×除数+余数）

12=1×9+3（第二步）

9=3×3+0（余数为0，停止）