信息安全数学基础-第二章-同余

这一章讲了初等数论的同余部分，时间有限，这篇文章是一些重点标记

“同余”是大自然的循环现象, 研究同余的优点在于:化无限为有限.

• 剩余类：将所有整数按照模m划分成了不同的类
• 完全剩余系：从每个剩余类中拿一个出来组成完全剩余系
• 简化剩余类：是m的完全剩余系中与m互素的数构成的子集
• 简化剩余系：从每个简化剩余类中拿一个出来组成简化剩余系

欧拉定理

Wilson定理

费马定理

欧拉函数及其计算方法

考点1：同余等价关系定义、三大性质（自反、对称、传递），利用乘法（降幂）计算较大数的mod运算
考点2：剩余类，完全剩余系、简化剩余系的定义
考点3：欧拉函数的定义以及利用标准因数分解式计算欧拉函数（易错）
考点4：欧拉定理、费马小定理
考点5：用模重复平方法求解大数的模

拓展定理：