信息安全数学基础2
思来想去，还是分个段吧，毕竟文章太长了也没意思。
2同余
这一章讲同余，为后面的RSA密码做铺垫
2.1同余和剩余类
2.1.1同余
定义：同余（英语：Congruence modulo，符号：≡）在数学中是指数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与“≡”符号者为德国数学家高斯。(要想打出来，用拼音quandengyu，markdown的LaTex语法是\equiv)
eg:
$26≡14(mod12) 26和14模12的余是一样的
同余的一些基本性质：
同余可以相加，可以相减，还可以相乘，但不可以相除
2.1.2剩余类
定义：把$r \bmod m$ 称为模m的一个剩余类，除以$m$后余数相等的记为一类，同一个余才属于同一类，不同的余属于不同的类。(只要取定一个m，那么就可以将所有的整数分为m个剩余类，任意的r只要是对m取模相同，则在同一个剩余类里面)
eg：一个整数被正整数n除后，余数有n种情形：$0，1，2，3，…，n-1$。我们把所有对模n同余的数构成的集合叫着模$n$的一个剩余类。
例如: 12的剩余类，为12个集合。每个集合的余数都是相同的。
$${…,0,12,24,36,…}$$ ======>余0
$${…,1,13,25,37,…}$$ ======>余1
$${….2,14,26,38,…}$$ ======>余2
…
$${…,11,23,35,47,…}$$ ======>余11
须注意：$${…,-47,-35,-23,-11,11,23,35,47,…}$$，剩余类包括正负数。
【拓展】完全剩余系
定义：完全剩余系，即是通过对一系列正整数$mod ;m$后产生的从$0$至$（m-1）$的完全数系。通常地，完全剩余系在研究数论时很有用.
注意:与之前的剩余类不同，这个系余$m$每一个余都不同，且一共有$m-1$个
eg：
如{0,1,2,3,4}是5的一个完全剩余系。
12的完全剩余系为$${0,1,2,3,4,5,6,7,8,9,10,11}$$
2.2简化剩余系，欧拉定理与费马小定理
2.2.1简化剩余系
百度上的定义:
1.简化剩余系(reduced residue system)也称既约剩余系或缩系，是m的完全剩余系中与m互素的数构成的子集;
2.如果模m的一个剩余类里所有数都与m互素，就把它叫做与模m互素的剩余类。
eg:模$7$的剩余类${1，2，3，4，5，6}$,就是一个。
3.在与模m互素的全体剩余类中，从每一个类中各任取一个数(第一个正整数)作为代表组成的集合，叫做模m的一个简化剩余系。例如，模$5$的一个简化剩余系是${1，2，3，4}$模$10$的一个简化剩余系是${1，3，7，9}$ ($2,4,5,8$与$10$不互素)。模$18$的一个简化剩余系是${1，5，7，11，13，17}$ (与上同理) 。
简化剩余系是一种特殊的完全剩余系
eg:如{0,1,2,3,4}是5的一个完全剩余系，同时也是一个简化剩余系。
2.2.2欧拉定理
定义：
对于整数n，欧拉函数是下于n的正整数中与n互质的数的数目
例如：8的欧拉函数是4，7的欧拉函数是6
综合，一共以下性质：
性质1： 如果$p$是素数，那么他的欧拉数是$p-1$
性质2： 如果$p,q$都是素数，准确的说法应该是$q,p$互素则$$φ(N)=φ(p)φ(q)=(p−1)(q−1)$$
性质3： 如果$p$是素数，对于$p^t$，$φ(p^t)=p^t-p^{t-1}$
拓展：
定理1：
如果正整数$n (\ge2)$有标准分解式$n=p_1^{t_1}….p_s^{t_s}$
则$$φ(n)=\prod_i({p_1^{t_1}….p_s^{t_s}})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})..(1-\frac{1}{p_3})$$
看不懂没关系，举个板子：
eg：求$φ(120)$
解：
$$120=2^3 \times3 \times5$$
$φ(120)=φ(2^3) \times φ(3) \timesφ(5)$
$=(2^3-2^2) \times (3-1) \times (5-1)$
$=4 \times 2 \times 4$$
$=32$
======
欧拉定理拓展：
如果$(p,m)=1$，即$p,m$互素
则$p^{φ(m)} \equiv 1 \pmod{m}$
eg:
$(5,12)=1$
$5^4\equiv1 \pmod{12}$
其中$φ(12)=4$
2.2.3
费马小定理（英语：Fermat’s little theorem）
定义：
假如 $a$ 是一个整数，$p$ 是一个质数，那么 $a^p-a$ 是 $p$ 的倍数，
整除形式就可以表示为 $a^p \equiv a \pmod p$
如果 $a$ 不是 $p$ 的倍数,那么这个定理可以写成更普通的形势 $a^{p-1} \equiv 1 \pmod p$
感慨：反正就，挺神奇的
证明(同余法,可以跳过)：
任意取一个质数，比如13。考虑从1到12的一系列整数1,2,3,4,5,6,7,8,9,10,11,12，给这些数都乘上一个与13互质的数，比如3，得到3,6,9,12,15,18,21,24,27,30,33,36。对于模13来说，这些数同余于3,6,9,12,2,5,8,11,1,4,7,10。这些余数实际上就是原来的1,2,3,4,5,6,7,8,9,10,11,12，只是顺序不同而已。
把1,2,3,„,12统统乘起来，乘积就是12的阶乘12！。把3,6,9,„,36也统统乘起来，并且提出公因子3，乘积就是312×12！。对于模13来说，这两个乘积都同余于1,2,3,„,12系列，尽管顺序不是一一对应，即312×12！≡12！mod 13。两边同时除以12！得312≡1 mod 13。如果用p代替13，用x代替3，就得到费马小定理
xp－1≡1 mod p。
感谢：https://www.cnblogs.com/flipped/p/5218037.html
2.3模运算和同余的应用
2.3.1密码系统的基本概念模型
定义：<P，C，K，E，D> 明文空间，密文空间，密钥空间，加密算法，解密算法
古典派：移位密码(凯撒)，Vigenere密码，Hill密码等
现代派(数学难题)
例：维吉尼亚密码
在一个凯撒密码中，字母表中的每一字母都会作一定的偏移，例如偏移量为3时，A就转换为了D、B转换为了E……而维吉尼亚密码则是由一些偏移量不同的恺撒密码组成。
为了生成密码，需要使用表格法。这一表格包括了26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。
例如，假设明文为：
1 | ATTACKATDAWN |
选择某一关键词并重复而得到密钥，如关键词为LEMON时，密钥为：
1 | LEMONLEMONLE |
对于明文的第一个字母A，对应密钥的第一个字母L，于是使用表格中L行字母表进行加密，得到密文第一个字母L。类似地，明文第二个字母为T，在表格中使用对应的E行进行加密，得到密文第二个字母X。以此类推，可以得到：
1 | 明文：ATTACKATDAWN |
Hill密码：https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E5%AF%86%E7%A0%81
2.3.2移位密码
2.3.3Vigenere密码
2.3.4Hill密码
以上都是一些简单密码，了解一下就行了