信息安全数学基础总结（有空更新）
大二第一学期，学院开设了《信息安全数学基础》这门课。但由于当时对信息安全的理解还不够深入，再加上已经过去了两年之久，很多知识都理解得不好，且印象模糊。借着大四这个相对空闲的时间，对学过的知识进行复习和总结。
2024.03.01: 当时太天真了，以为大四很空闲，现在看来并不是这样的...这篇博客就占个坑留到以后更新吧...T_T
初等数论
整数的因子分解
整除
- \(a,\ b\in \mathbb{Z},\ b\neq 0,\quad 若\ \exists\ q,\ 使得\ a=qb,\ 则\ b\mid a\ (b整除a),\ 否则\ b\nmid a\)
- \(b\)称为\(a\)的因子，\(a\)称为\(b\)的倍数
- 性质
- 传递性：\(c\mid b,\ b\mid a,\ then\ c\mid a\)
- \(b\mid a,\ then\ bc\mid ac\)
- \(c\mid a,\ c\mid b,\ then\ c\mid ma+nb\)
Euclid(欧几里得)除法
- \(a,\ b\in \mathbb{Z},\ b>0,\ 则存在唯一的整数对q,r\ 使得\ a=qb+r,\ 0\leq r<b\)
- \(q\)称为不完全商，\(r\)称为余数（最小非负余数）
- 若调整\(q\)（一般是加1）使得\(|r|\leq \frac{b}{2}\)，则\(r\)为绝对值最小余数（在Euclid算法中起到加速的作用）
- 可用于求整数的\(a\)进制表示
公因子与最大公因子
- 设\(a,a_2,…,a_n\)是\(n(n\geq2)\)个整数，若整数\(d\)是它们中每一个数的因数，则\(d\)称\(a,a_2,…,a_n\)的一个公因子
- 若\(a,a_2,…,a_n\)不全为零，则\(a,a_2,…,a_n\)的所有公因子中最大的一个称为最大公因子，记为\((a,a_2,…,a_n)\)
- 特别地，当\((a,a_2,…,a_n)=1\)，称\(a,a_2,…,a_n\)互素/互质
- 定义\((0,a)=a\)，因为任何非零整数都是\(0\)的因数
辗转相除法/Euclid算法 求最大公因子
预备定理：\(a,b,r是不全为0的整数,\ 若a=qb+r,\ q\in\mathbb{Z},\ 则(a,b)=(b,r)\)
将上述辗转相除的过程反过来写（即把余数放左边，用\(a,b\)来表示余数），可以得到最大公因子的线性表示，即贝祖等式
贝祖等式：对任意两个正整数\(a,b\)，存在整数\(x,y使得(a,b)=xa+yb\)
当\((a,b)=1\)，可以求出唯一解\(x\)，即\(xa\equiv 1(mod\ b),\ x\equiv a^{-1}(mod\ b)\)
扩展/广义Euclid算法：求出最大公因子的同时求出系数\(x,y\)（主要用于求乘法逆元）
伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13Input: 非负整数a, b且a>=b (先将待计算的整数取绝对值)
Output: r=(a,b) 以及满足 sa+tb=(a,b)的s,t
Extended Euclid(a,b){
(r,s,t) <- (a,1,0);
(r',s',t') <- (b,0,1);
While r'!=0 do{
q <- floor(r/r');
(tmp1,tmp2,tmp3) <- (r-qr',s-qs',t-qt');
(r,s,t) <- (r',s',t');
(r',s',t') <- (tmp1,tmp2,tmp3);
}
Return r,s,t;
}最大公因子等价定义：\(a,b\)是不全为零的整数，则\(d=(a,b)\)是集合\(\{xa+yb|x,y\in \mathbb{Z}\}\)中的最小正整数
应用-方程有解的判定：\(a,b\)是不全为零的整数，则方程\(ax+by=c有整数解\Leftrightarrow (a,b)\mid c\) >个人理解：对于整数\(a,b\)，他们的最大公因子就是使用这两个数能得到的最小度量 > >换句话说，即长度为\(a,b\)的两把尺子可以度量的最小长度
素数
- 埃拉托色尼素数筛选法-快速计算\(1\)到\(N\)之间的所有素数：遍历\(1\)到\(\sqrt{N}\)，将其中所有素数的倍数去掉，剩下的便都是素数了
- 素性定理：\(p\)为素数，\(a,b\)为整数，若\(p\mid ab\)，则\(p\mid a\)或\(p\mid b\) ^291cce
- 算数基本定理：任意整数\(n\ (n>1)\)都可以分解为有限个素数的乘积\(n=p_1p_2...p_s\)，该分解除了素数因子的排列之外，是唯一的
- 唯一因子分解定理：任意整数\(n\ (n>1)\)可以唯一地表示成\(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_s^{\alpha_s},\ \alpha_i >0\)，其中\(p_1p_2...p_s\)为素数\(p_i<p_j\ (i<j)\)。上式叫做\(n\)的标准分解式。
整数的一些性质
- \(a=p_1^{\alpha_1}p_2^{\alpha_2}...p_s^{\alpha_s},\ b=p_1^{\beta_1}p_2^{\beta_2}...p_s^{\beta_s}\)，那么\((a,b)=p_1^{\gamma_1}p_2^{\gamma_2}...p_s^{\gamma_s},\ \gamma_i=min(\alpha_i,\beta_i)\)，最小公倍数\([a,b]=p_1^{\delta_1}p_2^{\delta_2}...p_s^{\delta_s},\ \delta_i=max(\alpha_i,\beta_i)\)
- \(a_1,a_2,...a_n\)为\(n\)个非零整数，令\([a_1,a_2]=m_1,\ [m_1,a_3]=m_2,...,[m_{n-2},a_n]=m_{n-1}\)，则\([a_1,a_2,...a_n]=m_{n-1}\)
- 除了2以外，所有素数都是奇素数
多项式的整除性
- 令\(\mathbb{Q}=\{\frac{a}{b}|a,b\in \mathbb{Z},b\neq0\}\)表示全体有理数的集合。\(\mathbb{Q}\)上有加减乘除四则运算
- 令\(\mathbb{Q}[x]=\{a_0+a_1x+...+a_nx^n|a_i\in\mathbb{Q},0\leq i\leq n\}\)表示所有系数为有理数的多项式集合。\(\mathbb{Q}[x]\)有加减乘，但没有除法
- 可以发现\(\mathbb{Q}[x]\)与整数集合\(\mathbb{Z}\)有很多类似的性质：都有带余除法、最大公因子、唯一因子分解定理等
（多项式\(f(x)\)的次数表示为\(deg\ f(x)\)，以下多项式均在\(\mathbb{Q}[x]\)内讨论）
- \(g(x)\neq 0\)，则有\(q(x),r(x)\)使得\(f(x)=q(x)g(x)+r(x),\ r(x)=0或r(x)\neq 0,deg\ r(x) < deg\ g(x)\)
- \(r(x)=0\)时，称\(g(x)整除f(x)\)，记\(g(x)|f(x)\)，\(g(x)\)称为\(f(x)\)的因子
- 当\(g(x)\)为\(f(x)\)的因子，且\(deg\ g(x) < deg\ f(x)\)时，\(g(x)\)称为\(f(x)\)的真因子
- 当\(f(x)\)没有真因子时，称为不可约多项式
个人理解：把函数的符号\(f,g\)当成整数的符号来看，多项式的整除与整数的整除几乎相同，只是多了\(x\)而已
因此其余的不再赘述：
多项式整除性质——参考整数整除性质
多项式最大公因子——参考整数最大公因子
多项式最大公因子的表示——参考整数最大公因子的表示（贝祖等式）
多项式最大公因子的求法——参考整数的辗转相除法
不可约多项式的有关定理——参考整数的素性定理
多项式的唯一分解定理——参考整数的唯一分解定理