信息安全数学基础
说明：此次笔记是为期末考试突击学习而产生
1 整除
1.1整除的概念
若整数b除以非零整数a，商为整数，且余数为零， 我们就说b能被a整除（或说a能整除b），b为被除数，a为除数，即a|b（“|”是整除符号），读作“a整除b”或“b能被a整除”。a叫做b的约数（或因数），b叫做a的倍数。整除属于除尽的一种特殊情况。
A|B 即A整除B
性质1：一个正合数，它的的因子中，大于1的最小正因数p一定是素数，且$$p \leq \sqrt{n}$$
如何快速筛选素数?
考点：
通过以上性质1可得Eratosthenes筛选法：
即求出不超过给定正整数$X(X \ge 1)$的所有素数，只要把2到$x$ 的所有合数都删去即可。因为不超过x的合数n必有一个素因子
$p \leq \sqrt{n}\leq \sqrt{x}$,所以只要求出$\sqrt{x}$以内的全部素数${p_i,1 \le i \le k }(k为\sqrt{x}以内的素数个数)$，然后把不超过x的$p_i$的倍数全部删除，即使全部素数
eg：求不超过64的所有素数
解：先求出不超过$\sqrt{64}=8$的所有素数$(2,3,5,7)$,然后从2~64的所有依次删除$2,3,5,7$的以外的2的倍数，3的倍数，5的倍数，7的倍数
性质2
素数有无穷个
性质3
设 $n $
1.2欧基里德算法(Euclid)
Q：算法是用来干嘛的?
A:用来求最大公因数的！
同样是求取最大公约数，在之前，有个简单的短除法！
eg：
现在是阿基里德算法
源起前置:
1.GCD(Greatest Common Divisor)
2.假设（A和B的最大公约数，也等于B和余数的最大公约数，以此类推）
3.**GCD(A,B) = N **代表了这个公式会给出A和B的最大公约数是N
4.$GCD(A,B) = GCD(B,A mod B)$ ,其中$A mod B$代表了余数，也就是我们上面写的$R$，因为A模上B就是我们的余数(R)
证明：
假设在这里有一个整数u是一个A和B的公约数假设$A=a \times u \quad B=b \times u$
那在（4）里面的公式就可以被改写成
============
欧几里得的原理演示：略
==========
感谢：https://zhuanlan.zhihu.com/p/259706781讲得很好
1.3拓展阿基里德算法
1.3.1gcd(a,b)缩写为(a,b)
1.3.2用途：扩展欧几里得算法是为了在计算最大公约数$gcd(a,b)$的同时，找到x，y，使得$ax + by = d$（即求得方程解）
1.3.3也就是说拓展阿基里德算法是求$(A,B) = N = ax+by$ 中的x，和y
1.3.4 $ax+by=gcd(a,b)$的求解要易于ax+by=c的求解（这里我们假设ax+by=c一定有解，因此这里默认c是$gcd(a,b)$的倍数）
我们观察到：欧几里德算法停止的状态是： a= gcd ， b = 0 ，那么，这是否能给我们求解 x y 提供一种思路呢？因为，这时候，只要 a = gcd 的系数是 1 ，那么只要 b 的系数是 0 或者其他值（无所谓是多少，反正任何数乘以 0 都等于 0 但是a 的系数一定要是 1），这时，我们就会有： a*1 + b*0 = gcd
节选：
那么，什么是拓展欧几里得呢？这是一种算法，它可以在辗转相除途中求出不定方程 $ax+by=c$的一组解。
注意到上图中倒数第二行的$3+6* 3=21$，可以改写为，$3= 6*(-3)+21$也就是说 可$3$以被表示为 和 $21$组合。
=====
拓展欧几里得原理演示： 略
======
非常感谢：https://zhuanlan.zhihu.com/p/100567253
————————————————
1.4算数基本定理
1.4.1定理：
算术基本定理（the Fundamental Theorem of Arithmetic）：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积.
1.4.2证明：
====
原理演示部分：略
====