信息安全与数学基础-笔记-②同余

同余

a,b 两个数字，都模m，当两个数字模m后余的数一样即为同余。
例子：
a = bq + r (mod m)，这里的a 和 r 就是同余 ，因为a模m就是余r的

• 同余性质：若 m | a-b 则 a 和 b 同余 m，同余符号用三横线表示
  

• 传递性：若：a b同余 ，b c 同余，那么a和c就同余

• 倍数原则：a和b模m同余，则a = km + b
  解释：同余中玩的也是余数，所以当模m余数相同的时候，不管你添加多少个m都是同余的结果

• 加法原则：a b 同余，c d 同余，则a + c 和 b + d也同余
  解释：原因是因为a 和 b的余数是相同的，只要两边添加相同的数字便不会改变ab之间还是同余的关系，那么上面添加的是 c 和 d，明显cd本身就是同余，也就是说ab添加的不是cd而是cd的余数，他们的余数是一样的，也就是两边添加后还是同余的结果。

• 乘法原则：a b 同余，c d 同余，则a × c 和 b × d也同余
  解释：同理，本质是用余数进行运算，所以相乘也是两边乘以同一个数字后还是同余的。
  注意：乘法成立，除法不成立

• 乘法原则推论：a b 模m同余，则：na 和 nb同余，n为任意整数
  解释：余数同乘则不变

• 指数原则：若ab同余，则：$a^n$和$b^n$也同余
  解释：因为a和b同余，次方数也一样，个数一样的a和b相乘，其实也就是和乘法原则一样，所以指数原则只要次方数一样也是同余。

• 单独原则：a + b mod m == a mod m + b mod m 或者 当ab同余的时候，na和nb在判断是否同余的时候，也可以单独先对ab分开取模，例如：n (a mod m) = n (b mod m)
  解释：在一个求模式子中，可以单独拆开来分别先取模，同理在乘法中也一样，两个数字相乘，也可以单独拆开来分别取模，这和十进制运算也是一样的道理。

• 同除原则：若ad 和 bd 模 m同余，(d,m) = 1，则：a 同余 b
  解释：上面的乘法原则提到除法不行，但是这里又可以？因为这里的d是和m互素的，所以我们可以用单独原则，将两边的d进行先取模，最后得到一个1和ab相乘，所以最后得出ab是同余的，所以在希望通过除法对数字简化的时候必须要保证两边的数字能够提取出来的公因数是与m互素的才能够保证之后的数字仍为同余。

• 若ab模m同余 ，取k,k>0,则：同乘k后ak bk 模mk仍然同余
  解释：这里的k并没有考虑是否和m互素或者与其他数字有什么联系，我们不考虑这些关系后把m也同时乘k，这时候当我们再把ak取模的时候会把k一同消去，留下的只有a的余数，同理bk也是留下了b的余数，那么就和原本的ab模m同余一样了。对比上面同乘原则这里更多的是考虑整体，而同乘原则考虑的是余数之间，因为同余的余数相等，同乘k是依旧同余，但余数余数不一样了，变成了k倍了，但是这里是整体乘k，取模的时候是整体模k，所以，模完之后的余数仍然和原本的ab模m后的余数使用一样的，因此这两个定理是不一样的。

• 若ak bk 模mk同余，则：a b 模 m同余
  解释：其实是上一条定理的推论，但是要把模数也除，因为这里的k并没有和模数mk互素，因此也要都除。为什么不叫同除：因为同的意思是同余的两个数的同除，不关模数的事情，但这里把模数也除了，所以不叫同除原则了（好牵强的解释）。
  把ak bk mk换成c d e,那么推论就是：cd模e同余，那么c/k d/k 模e/k同余

• 假如：a 三 b (mod m1) ，a 三 b (mod m2)
  那么求出m1,m2的最小公倍数为 G
  则：a 三 b (mod G) 同余。
  （PS：这里的定理在后面的方程组中，如果发现一个数字可以拆分成m1,m2，mi…相乘，并且两两互素的时候就可以减少计算量）

• 总结
  “同”的字眼一般是对同余符号两边的数字进行操作，和模数没有关系
  因此：同乘k模m仍旧同余，但余数若没有超出模数大小就变成了余数的k倍。同除就是能将两边的数提取公因数，并且该公因数需要和模数互素才可以同除。
  以下说的就是和模数有关的，当两边的数和模数都能提取出一个公共的公因数就可以一并提取，也可以无缘无故的同时乘一个k数进去，涉及到模数改变的，一般改变之后，和原本的式子的余数一样。

完全剩余系

完全剩余系是由剩余类中的数字组成的。
是等于模m中 ，0~m-1的数字就是完全剩余系，即两两不同余。

剩余类

当模m后，每一个数字都不会大于m，那么在0~m-1个数字中，每个数字代表了一个剩余数字，因为在模的世界里， 比如1模m余数为1，也就是剩余为1的一类，当1加上模数m的时候，再去模m后还是1，所以余数为1的数字很多，把这些数字统一起来叫余数为1的剩余类
设：
$C_0$ 代表余数为0的一类
$C_1$ 代表余数为1的一类
$C_2$ 代表余数为2的一类
$C_3$ 代表余数为3的一类，以此类推
这就是剩余类，剩余类有m个，范围是[0, m-1]

• 剩余类之间的关系
  ①每个数字都同余
  ②剩余类内的数字可以是无限大，只要是余数和剩余类内其他数字同余即可
  ③剩余类内任意取出一个数，该数叫做该类的剩余

完全剩余系

当模m后，我们在每一个剩余类中取出一个数字来组成一个整体，那么该整体就叫做完全剩余系。

• 完全剩余系之间的关系
  ①每个数字之间都不同余
  ②每个数字模m后组成0~m-1的数字
  ③该系中的数字可以无限大，只要不和其他数字同余即可

---

完全剩余系的性质

• 若**(a,m) = 1**，设$r_0$,$r_1$,$r_2$…$r_m$为模m的一个完全剩余系
  那么：a$r_0$ + b, a$r_1$ + b, a$r_2$ + b, … a$r_m$ + b, 仍然是模m的一个完全剩余系，该性质完全就是应用了同余知识，当a和m互素的时候就能够将原本的数字改变后仍和原来的数字是同余的，所以在完全剩余系中都不同余的数字，每一个数字改变后其实还是和原来的数字是一样的，所以其实还是原来的剩余系没有改变，仍旧是都不同余的数字，只是数字本身进行了一些变化，其他数字也会跟着变化，所以剩余系还是那个剩余系。
• 完全剩余系的应用
  
  解释该定理是如何操作的：
  一：随便找出两个互素的正整数的完全剩余系，设两个数：$m_1$$m_2$
  二：说明：待会公式中，$x_1$，$x_2$ 会分别 遍历 $m_1$，$m_2$的完全剩余系
  （x1遍历m1，x2遍历m2）
  三：公式：$x_1$×$m_2$ + $x_2$×$m_1$ ，其中$x_1$，$x_2$就开始遍历
  四：遍历得到的多个数字，$x_1$×$m_2$ + $x_2$×$m_1$ 其实就是模$m_1$×$m_2$的完全剩余系。

❀简化剩余系❀

简化剩余系就是在完全剩余系中找出与模数m互素的剩余类，将其留下来组成的整体就是简化剩余系。
举例：模数为8的时候
$C_1$ $C_3$ $C_5$ 就是模8的简化剩余系，其他剩余类中的0 2 4都不是和8互素的

欧拉函数

模m的简化剩余系中的个数，叫做欧拉函数：$\varphi$(m)
其他运算和简化剩余系一样，一些简单的运算后保证还是简化剩余系即可。

• 若p为素数，$\varphi (p)$ = p - 1
• 若mn互素，即(m,n) = 1，则$\varphi$(mn) = $\varphi$(m)$\varphi$(n)
• 若p为素数，$\varphi$($p^a$) = $p^a$ - $p^a$ ${}^{-}$ ${}^1$
• 若p,q为素数，并且n = p×q，则$\varphi$(n) = (p-1)(q-1)

---

• 欧拉函数求解通式
  设n为欧拉函数的参数
  求出n的标准分解式：n = $p_1$${}^a$${}^1$×$p_2$${}^a$${}^2$×$p_3$${}^a$${}^3$…
  则：$\varphi$(n) = n × (1- 1/$p_1$ ) × (1- 1/$p_2$ ) × (1- 1/$p_3$ )
  欧拉函数求解的通式十分重要

---

逆元

设：(a,m) = 1，a×$a^{-}$三 1 mod m
$a^{-}$就是a的逆元，相当于分数中的倒数，一个数乘以他的倒数就等于1，在同余中同理，当一个数乘以逆元，就同余1.
如何求逆元：
对(a,m)使用欧几里德算法后使用裴蜀等式算出s和t，也就是sa + tm = 1后，很明显，要找a的逆元就是s，因为tm模m后是0，只剩下sa = 1所以逆元就是s

！欧拉定理 ！

欧拉定理必须要记住，在后续解方程或者计算高次幂的数字时候能大大减少计算量。

• $a^{\varphi }$${}^{(}$${}^m$${}^{)}$ 三 1 (mod m)

---

费马小定理
$a^p$${}^{-}$${}^1$ 三 1 (mod p)
解释：其实就是应用了欧拉定理中的方法，当p是素数的时候$\varphi (p)$ = p-1

---