网安数学基础期末复习

整除

• a的显然因数/平凡因数±1，±a
• 整除的传递性和组合性
  
• 若 $a|b,b|a$ 则 $a=\pm b$
• 欧几里得带余除法
  
• 公因数和最大公因数在整除里的定义，最大公因数为1则两数互质，注意公因数有正负，任何公因数都整除最大公因数
• 辗转相除法的原理：
• 相关的推论：
  
• 扩展欧几里得算法求公因数的过程
  代码实现：

#扩展欧几里得算法ax+by=gcd(a,b),该函数可求gcd(a,b),x,y
def extend_gcd(a,b):
    if b==0:
        return (a,1,0)
    else:
        g,x,y=extend_gcd(b,a%b)
        return (g,y,x-(a//b)*y)

• 该式的逆命题不一定成立，即存在ax+by=d，但d不一定是最大公因数
• 三个推论及证明（体会这个式子在证明中的应用）
  
  
• 素数和算数基本定理
  
• 证明素数有无限多个的思路：反证法假设素数有有限多个分别是$p_1,p_2...p_n$,设$n=p_1\ast p_2\ast ...p_n+1$,由算数基本定理，可以确定n一定有一个素因子p，因为n加了1，显然p的倍数不可能是1，所以p不属于$p_1...p_n$中的任何p，所以素数有无限多个
• 证明形如4k-1的素数有无限多个：
  1. 证明形如4k-1的数一定含有4k-1的因子
  2. 反证法推出矛盾
     
     简单推理就能得到$（4k+1）\ast （4k+1）$得到数的形式还是（4k+1）
     
• 厄拉托赛师法筛选素数：
• 梅森素数：形如$2^n-1$的数
• fermat素数：形如$2^{2^n}+1$的数
• 整数的进制表示和高精度运算：略作了解即可

同余

• $a\equiv b(\mathrm{mod}c)$
• 同余方程写成整除的形式：
  
  
• 同余式可逐项加减乘
• 相关定理
  
  
  
  
  
• 同余类/剩余类：模m的值相同组成的集合，共有m个，剩余类中的元素叫剩余或代表元，m个互不相同的代表元组成完全剩余系，$0,1,2,..m-1$组成的剩余系叫最小非负完全剩余系，记作$Z_m$。
  
  
  
• 欧拉函数的计算：
  
• 欧拉定理：
• 
  费马小定理（注意和欧拉定理的区别）：
  
• 固然可以用欧拉函数求满足条件的值，但是阶的值可能是欧拉函数的因子（即比欧拉函数更小
• 模重复平方算法：简单理解就是快速冥算法再加个取模操作
• 素性检测：利用以下引理，那么当二次同余方程有其他解时，则说明p不是素数
  
  费马小定理进行素性检测
  
  

同余方程

• 同余方程的解数：满足条件的同余类的个数
  
• 一次同余方程的求解过程：先找$ax=1(\mathrm{mod}m)$的唯一解$x_0$，接着回到原来的同余方程$ax=b(\mathrm{mod}m)$，系数变换$x=x_0\ast b$得到这个方程的特解，得到特解后求通解
  
• 中国剩余定理CRT：
• 中国剩余定理手算求解
• 
  二次剩余和二次非剩余（区别于二次方程有解还是无解）：
  
• 怎么找二次剩余和二次非剩余？令x是从1到10的所有数，求出的a就是二次剩余，剩下的数是二次非剩余
  
  剩余和非剩余各占简化剩余系的一半，进而得出求二次剩余的新方法：求出序列的所有同余解
  
• 欧拉判别法判定一个数是二次剩余还是二次非剩余。
• 前提：a,p 互素
  
• 三个组合的推论，本质是判断二次剩余的方程
  
  但是这样判断二次剩余计算还是过于麻烦->引入勒让德符号
  
  
• 能用勒让德符号的公式一定可以用欧拉判别法推，这些公式很重要，熟悉掌握是后续做题推理的关键
  
  
  
• 应用：判断同余方程是否有解
  
  
• 当m不是质数时，用CRT拆成同余方程组，但是这样求解还是麻烦，于是引入雅可比符号
  
  

• 区别：不同于勒让德符号，当雅可比符号等于1时，二次方程未必有解，但是当值为-1时，方程一定无解，雅可比符号的其他性质与勒让德符号一模一样
• 怎么求同余方程的解？
  更一般的求法：直接计算$a^{(p+1)/4}\mathrm{mod}p$
  

• Rabin公钥加密算法：基于大整数分解的复杂性
  
  
  

群和环

• 二元运算需要满足的三个条件，注意区分定义在什么集合上的什么运算
  
  
• 群的定义：满足代数运算和三个性质的特殊集合，怎么判断一个集合是不是群，就看是否满足这三个条件
• 群的基本性质：单位元和逆元唯一，满足消去律，逆满足线性运算原则
• 交换群/阿贝尔群：满足交换律的群
• 有限群和无限群：看群中元素个数是否有限
• 最小简化剩余系满足乘群，不满足加群
• 子群：子集合同样满足群中运算
• 循环群：