1. 整除、欧几里得除法的的定义
好像别的没啥好说的，就挑点自己记不太清的写上来.
1.1 Eratosthenes（厄拉托塞斯）筛法
该方法用于快速获得小于整数N的素数集合，工作原理如下：
- 对寻找小于整数N的素数，先求\(\sqrt{N}\)（没法取整就写成\(\sqrt{N}<[\sqrt{N}]+1\)的形式）,获取小于\(\sqrt{N}\)的素数\(P_0,P_1,...P_n\)。
- 对一个1~N的数集，从中去除\(P_0,P_1,...P_n\)的倍数，剩下的就是小于N的素数。
例：
有N=81,\(\sqrt{81}=9\)，所以P={2,3,5,7}.
有小于81的素数集为{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47...}
反正就是去除2，3，5，7的倍数，剩下的就是素数了。
1.2 欧几里得除法
1.2.1 欧几里得除法
对整数a，b，有唯一的q和r，与a，b有如下关系：
\(a = q *b+r,0\leq r \lt b\).
当a = 255，b = 15，有\(q = [\frac{255}{15}]=17,r=a-b*q=0\).
可用于判断某数是否为素数，有定理对整数N，对素数集P有\(P\leqq \sqrt{N},P_n\nmid\sqrt{N}\),可判定N为素数。
例：
对N=17，\(\sqrt{17}\lt5\),有P={2,3,5}.
有\(17=2*8+1,17=3*5+2,17=5*3+2,\therefore2\nmid17,3\nmid17,5\nmid17.\)
所以N为素数。
1.2.2 欧几里得除法拓展
也叫辗转相除法，对a，b，有：
\(记r_{-2} = a,r_{-1}=b\)
\(r_{-2} = q_0*r_{-1}+r_0\)
\(r_{-1} = q_1*r_{0}+r_1\)
\(r_{0} = q_2*r_{1}+r_2\)
......
\(r_{,-1} = q_{n+1}*r_{n}+r_{n+1},\ r_{n+1}=0\)
有\((a,b) = r_{n}\)
1.2.3 贝祖等式
懒了，直接贴图
2. 用广义欧几里得除法求给定整数的逆
这个过程使用到了广义欧几里得除法以及贝祖等式，首先，给定整数a，要求相对于模m的乘法逆元x，即求x使得有式子\(ax \equiv 1\ mod\ m\)成立。
计算过程如下：
- 对给定的a,m,先计算(a,m)，获得a与m的最大公因数，这个过程使用到了广义欧几里得除法。若a，m不互质，则x不存在。
- 若(a,m) = 1,逆推广义欧几里得除法，获得贝祖等式，\(s*a+m*t = 1\)。
- 对s做模m运算，获得结果即为所要求的乘法逆元x。
3. 简述剩余类、完全剩余系、简化剩余类、简化剩余系的定义与性质
3.1 剩余类
3.2 完全剩余系
3.3 简化剩余类与简化剩余系
4. 基于欧拉定理、费马小定理的证明
4.1 欧拉定理
4.1.1 欧拉函数
若数m为素数，有\(\Phi(m) = m-1\)
若有m,n互素，有\(\Phi(mn) = \phi(m)*\phi(n) = (m-1)*(n-1)\)
4.1.2 欧拉定理
4.2 费马小定理
4.3 Wilson定理
5. 使用中国剩余定理计算给定同余式组的解
5.1 求解一次同余式
5.2 中国剩余定理求解同余式组
一个可能出的题：
5.3 中国剩余定理求解二次同余式组
分解为多项同余式时，可以用勒让德符号检验是否有解，若无，整个同余式组无解。
6. 判断是否平方剩余
6.1 平方剩余的定义
例：
6.2 判断方法：勒让德符号
计算方法：
对a为素数，ap互素和a为1时有更方便计算的规则，还有勒让德的推广雅可比符号，以及一个高斯引理，但是懒得记了，就这样吧
6.3 二次互反定律
7. 计算模平方根
没啥好说的，自己去悟吧（
8. 简述指数与原根的定义
8.1 指数和原根的定义
8.2 原根的计算
\(a\lt m,从1开始逐个计算a^k \equiv 1\ (mod\ m)，若k=\varPhi(m)，则a就是m的原根，ord_m(a)=k\)
例：
8.3 原根/指数的一些性质
8.4 求模m原根
计算方法如图所示，这里解释其中一些点：
- \(\because\) 对于原根，有\(g^{\varPhi(m)}\equiv 1\ mod\ m\),且\(g^i\)应当没有重复。
- \(验证 g^{26} 和 g^4 是基于 \phi(m) 的质因子的选择。在模 m = 53 的情况下，我们有 \phi(53) = 52。分解 52 为质因子的乘积，得到 2^2*13。\)
- \(所以，验证 g^{26} 和 g^4 实际上是验证了 \frac{\phi(53)}{2} 和 \frac{\phi(53)}{13}。这是因为如果 g 是模 m 的原根，那么 g^{\frac{\phi(m)}{q_i}} 对所有的 \phi(m) 的质因子 q_i 都应该与 1 不同余。\)
- \(验证其他的位，例如 g^2, g^8, g^{10}, g^{12}, ...，也是可以的，但选取的位数通常是根据具体的计算方便和验证是否充分来选择的。在很多情况下，选取了涵盖质因子的指数，可以更有效地验证是否为原根。\)
9. 将给定的实数写成简单连分数的形式
例：
对\(\frac{-97}{73}\),有计算过程如下：
- \(a_0=[x]=-2,x_0=x-a_0=\frac{49}{73}\)
- \(a_1=[\frac{1}{x_0}]=1,x_1=\frac{1}{x_0}-a_1=\frac{24}{49}\)
- \(a_2=[\frac{1}{x_1}]=2,x_2=\frac{1}{x_1}-a_2=\frac{1}{24}\)
- \(a_3=[\frac{1}{x_2}]=24,x_3=\frac{1}{x_2}-a_3=0\)
所以\(\frac{-97}{73}\)的简单连分数为[-2,1,2,24]
标签：剩余,phi,frac,复习,原根,信息安全,笔记,素数,除法 From： https://www.cnblogs.com/H4RUH1RO/p/17865554.html