信安数基复习笔记

往年期末考试题目

故A正确

简化剩余系：与模数互素且不同余

与15不互素：

故一个简化剩余系为

也可以写作

故C正确

B. 整数模素数剩余类环都是域，故B正确

C. 整环的定义是没有零因子，3*4=12是0，故C错误

原根存在的充要条件 或 ，其中 为素数，

故选D

A. pa=0，错误

B. 费马小定理是 ，错误

C. 正确

的原根数为

22

85=5*17

和 的解数之和

分别有两个解（分别是和）

故总共有四个解

是一个阶为16的有限域，则是一个阶为的循环群

在一个循环群中，任意元素的阶是的正约数。也就是说，中非零元素的可能乘法阶是的正约数

故可能取值为

第一步，计算所有模数的乘积

第二步，计算每个模数对应部分的乘积

第三步，计算在下的逆元

第四步，计算新的

通式：余数乘以模余乘以其逆

满足

故 或

故 ， 无解

1. 封闭性：如果，则；由于，且元素皆为有理数，因此

结合律：矩阵乘法满足结合律，即

单位元存在：单位矩阵，且对任意，有

逆元存在：对于，其逆矩阵，因为

证明是非交换群，找到反例即可

显然，故是非交换群

2. 定义，正规子群需要验证两点

是子群

封闭性：如果，则；由于，因此

结合律：矩阵乘法满足结合律，即

单位元：单位矩阵，因为

逆元：对于，其逆矩阵，因为

因此是子群

是正规子群

对任意

因此

故是的正规子群

(3)markdown学不会了（恼

1. 多项式 是不可约的，当前仅当它不可分解为两个低阶非常数多项式的积

拓欧算法

(a,b)=(b,a%b)

快速幂

CRT

二次剩余

原根

求原根：

1. 确定是否存在原根
2. 计算
3. 计算的所有素因子
4. 检验原根，当前仅当对的每个素因子都满足