信息安全数学基础-数论

整除

设$a,b$是任意两个整数，其中$b\ne 0$，若存在$q\in \mathbb{Z}$使等式$a=qb$成立，则称$b$整除$a$或$a$被$b$整除，记作$b\mid a$，并把$b$叫做$a$的因数，把$a$叫做$b$的倍数。人们常将$q$写成$a/b$或${\displaystyle \frac{a}{b}}$。否则称$b$不能整除$a$或$a$不能被$b$整除，记作$b\nmid a$。

设$a,b\ne 0,c\ne 0$为仨整数，若$b\mid a,c\mid b$，则$c\mid a$。

设$c\ne 0,c\in \mathbb{Z}$，若$c\mid a_1,\cdots ,a_n\in \mathbb{Z}$，则$\mathrm{\forall }{s}_1,\cdots ,s_n\in \mathbb{Z}$有${\displaystyle c|\sum _{i=1}^n{s}_i{a}_i}$。

设$a,b$为非零整数，若$a\mid b,b\mid a$，则$a=\pm b$。

设整数$n\ne 0,\pm 1$，若$n$除了因数$\pm 1,\pm n$外没有其他因数，则$n$叫做素数（或质数、不可约数），否则$n$叫合数。设$n$是一个正合数，$p$是$n$的一个大于$1$的最小正因数，则$p$一定是素数且$p⩽\sqrt{n}$。设$n\in {\mathbb{N}}_{+}$，若对所有素数$p⩽\sqrt{n}$都有$p\nmid n$，则$n\in \mathbb{P}$。素数有无穷多个。

设$a,b$是两个整数，其中$b>0$，则存在唯一整数$q,r$使得$a=qb+r,0⩽r<b$。其中$q$叫做$a$被$b$除所得的不完全商，$r$叫做$a$被$b$所除所得的余数。

设$x\in \mathbb{R}$，称$x$的整数部分为小于等于$x$的最大整数，记成$[x]$，这时有$[x]⩽x<[x]+1$。

设$f(x)$和$g(x)$都是$n\in {\mathbb{Z}}_{\mathbb{+}}$的正值函数。若存在常数$C>0$，使得对任意$n\in {\mathbb{Z}}_{\mathbb{+}}$都有$f(x)⩽Cg(n)$，就称$g(n)$为$f(n)$的界，记作$f(n)=O(g(n))$，简记为$f=O(g)$。若对任意小的$ϵ>0$，存在一个$N_0\in {\mathbb{Z}}_{\mathbb{+}}$使得对任意正整数$n>N_0$都有$f(n)<ϵg(n)$，就称$g(n)$是比$f(n)$高阶的无穷量，记作$f(n)=o(g(n))$，简记为$f=o\left(g\right)$。

设$a_1,\cdots ,a_n$是$n(n⩾2)$个整数。若$d\in \mathbb{Z}$是他们中每个数的因数，则$d$为$a_1,\cdots ,a_n$的一个公因数。若整数$a_1,\cdots ,a_n$不全为零，则$a_1,\cdots ,a_n$的所有公因数中最大的一个公因数叫做最大公因数，记作$(a_1,\cdots ,a_n)$。当$(a_1,\cdots ,a_n)=1$时称$a_1,\cdots ,a_n$互素或互质。设$a_1,\cdots ,a_n$是$n$个不全为零的整数，则$a_1,\cdots ,a_n$与$\mid a_1\mid ,\cdots ,\mid a_n\mid$的公因数相同，$(a_1,\cdots ,a_n)=(\mid a_1\mid ,\cdots ,\mid a_n\mid )$。设$b\in {\mathbb{N}}_{+}$则$(0,b)=b$。

设$a,b,c$是仨不全为零等整数，若$a=qb+c,q\in \mathbb{Z}$，则$(a,b)=(b,c)$。

广义欧几里得除法：设$a,b$是任意两个正整数，记$r_{-2}=a,r_{-1}=b$，有：
$$\begin{array}{}\text{(1)}& r_{-2}& =& q_0{r}_{-1}& +& r_0,& 0<r_0<r_{-1},\text{(2)}& r_{-1}& =& q_1{r}_0& +& r_1,& 0<r1<r_0,\text{(3)}& r_0& =& q_2{r}_1& +& r_2,& 0<r_2<r_1,\text{(4)}& & & ⋮\text{(5)}& r_{n-2}& =& q_n{r}_{n-1}& +& r_n,& 0<r_n<r_{n-1},\text{(6)}& r_{n-1}& =& q_{n+1}{r}_n& +& r_{n+1},& r_{n+1}=0\end{array}$$
设$a,b$是任意两个正整数，则$r_n=0$时有$n⩽5\log b$。此时有$(a,b)=r_n$，且当$a>b$时计算$(a,b)$的时间为$。

设$a,b$是任意两个正整数，则存在整数$s,t$使得$sa+tb=(a,b)$，这叫做Bézout等式。

设$a,b$是任意两个正整数，记$r_{-2}=a,r_{-1}=b$，有：
$$\left(\begin{array}{c}{r}_{-2}\\ r_{-1}\end{array}\right)=\left(\begin{array}{cc}{q}_0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{r}_{-1}\\ r_0\end{array}\right)=\left(\prod _{i=0}^{j+1}\left(\begin{array}{cc}{q}_i& 1\\ 1& 0\end{array}\right)\right)\left(\begin{array}{c}{r}_j\\ r_{j+1}\end{array}\right)$$
从而有：
$$\left(\begin{array}{c}{r}_j\\ r_{j+1}\end{array}\right)=\left(\prod _{i=j+1}^0\left(\begin{array}{cc}0& 1\\ 1& -q_i\end{array}\right)\left(\begin{array}{c}{r}_{-2}\\ r_{-1}\end{array}\right)\right)$$
记：
$$A_j=\left(\begin{array}{cc}{s}_j& t_j\\ u_j& v_j\end{array}\right)$$
则有：
$$\left(\begin{array}{c}{r}_j\\ r_{j+1}\end{array}\right)=A_j\left(\begin{array}{c}{r}_{-2}\\ r_{-1}\end{array}\right),-2⩽j⩽n$$
此时有：
$$\{\begin{array}{l}{s}_{-2}=1,\\ s_{-1}=0\end{array},\{\begin{array}{l}{t}_{-2}=0,\\ t_{-1}=1\end{array},\{\begin{array}{l}{s}_j=u_{j-1},\\ t_j=v_{j-1}\end{array},-1⩽j⩽n$$
以及：
$$\left(\begin{array}{c}{s}_j\\ s_{j-1}\end{array}\right)=\left(\begin{array}{cc}-q_j& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{s}_{j-1}\\ s_{j-2}\end{array}\right),\left(\begin{array}{c}{t}_j\\ t_{j-1}\end{array}\right)=\left(\begin{array}{cc}-q_j& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{t}_{j-1}\\ t_{j-2}\end{array}\right)$$
即为广义欧几里得除法：设$a,b$为任意两个正整数，则$s_{n}a+t_{n}b=(a,b)$，对于$0⩽j⩽n$，定义为：
$$\{\begin{array}{l}{s}_{-2}=1,s_{-1}=0,\\ t_{-2}=0,t_{-1}=1,\\ s_j=(-q_j)s_{j-1}+s_{j-2},\\ t_j=(-q_j)t_{j-1}+t_{j-2}\end{array},0⩽j⩽n$$
其中$q_j=\left[{\displaystyle \frac{r_{j-2}}{r_{j-1}}}\right]$为不完全商。

$a,b\in \mathbb{Z}$互素的充分必要条件是存在$s,t\in \mathbb{Z}$使得$sa+tb=1$。

设$a,b$是任意两个不全为0的整数。若$m$是任一正整数，则$(ma,mb)=m(a,b)$。若非0整数$d$满足$d\mid a,d\mid b$，则：
$$({\displaystyle \frac{a}{d}},{\displaystyle \frac{b}{d}})={\displaystyle \frac{(a,b)}{|d|}},({\displaystyle \frac{a}{(a,b)}},{\displaystyle \frac{b}{(a,b)}})=1$$
设$a,b,c$是三个整数，且$b\ne 0,c\ne 0$，若$(a,c)=1$，则$(a,b,c)=(b,c)$。设$a_1,\cdots ,a_n,c\in \mathbb{Z}$，若$(a_i,c)=1,1⩽i⩽n$，则$(a_1,\cdots ,a_n,c)=1$。

设$a,b,u,v,q,r,s,t\in \mathbb{Z}$，且$a=qu+rv,b=su+tv,qt-rs=1$，则$(a,b)=(u,v)$。

设$a_1,\cdots ,a_n$为整数，且$a_1\ne 0$，令：
$$\{\begin{array}{l}(a_1,a_2)=d2,\\ (d_2,a_3)=d3,\\ \cdots ,\\ (d_{n-1},a_n)=dn\end{array}$$
则$(a_1,a_2,\cdots ,a_n)=d_n$且${\displaystyle \mathrm{\exists }{s}_1,s_2,\cdots ,s_n\in \mathbb{Z},\sum _{i=1}^n{s}_i{a}_i=d_n}$。

设$a,b\in {\mathbb{Z}}_{+}$，则$2^a-1$被$2^b-1$除的最小非负余数是$2^r-1$，其中$r$是$a$被$b$除的最小非负余数。$(2^a-1,2^b-1)=2^{(a,b)}-1$。

设$a,b,c\in \mathbb{Z},c\ne 0$，若$c\mid ab,(a,b)=1$，则$c\mid b$。设$p\in \mathbb{P}$，若$p\mid ab$，则$p\mid a$或$p\mid b$。设$a_1,\cdots ,a_n\in \mathbb{Z},p\in \mathbb{P}$，若${\displaystyle p|\prod _{i=1}^n{a}_i}$，则$\mathrm{\exists }1⩽k⩽n,p\mid a_k$。

设$a_1,\cdots ,a_n\in \mathbb{Z}$，若$D$为该$n$个数的倍数，则$D$叫做这$n$个数的一个公倍数，$a_1,\cdots ,a_n$所有公倍数中最小正整数叫做最小公倍数，记作$[a_1,\cdots ,a_n]$。设$a,b\in {\mathbb{Z}}_{\mathbb{+}}$，有$[a,b]=ab$，且若$a\mid D,b\mid D$则$ab\mid D$。设$a,b\in {\mathbb{Z}}_{\mathbb{+}}$，有$[a,b]={\displaystyle \frac{ab}{(a,b)}}$，且若$a\mid D,b\mid D$则$[a,b]\mid D$。

设$a_1,\cdots ,a_n\in \mathbb{Z}$，令：
$$\{\begin{array}{l}[a_1,a_2]=D_2,\\ [D_2,a_3]=D_3,\\ \cdots ,\\ [D_{n-1},a_n]=D_n\end{array}$$
则$[a_1,\cdots ,a_n]=D_n$。若$\mathrm{\forall }1⩽k⩽n,a_k\mid D$，则$[a_1,\cdots ,a_n]\mid D$。

整数分解定理：给定合数$n>1$，若$\mathrm{\exists }a,b\in \mathbb{Z},n\mid a^2-b^2,n\nmid a-b,n\nmid a+b$，则$(n,a-b)$和$(n,a+b)$都是$n$的真因数。

算数基本定理：任一整数$n>1$都可表示成素数的成绩，不考虑成绩顺序的情况下，表达式是唯一的，即${\displaystyle n=\prod _{i=1}^s{p}_i,p_1⩽\cdots ⩽p_s,p_i\in \mathbb{P}}$。

标准分解式：任一整数$n>1$可唯一表示成${\displaystyle n=\prod _{i=1}^s{p}^{{\alpha }_i},{\alpha }_i>0,p_i<p_j(i<j)\in \mathbb{P}}$。设整数$n>1$，有${\displaystyle n=\prod _{i=1}^s{p}_i^{{\alpha }_i},\alpha }$