信息安全数学基础-数论
信息安全数学基础-数论
整除
设$a,b$是任意两个整数，其中$b\not=0$，若存在$q\in\mathbb{Z}$使等式$a=qb$成立，则称$b$整除$a$或$a$被$b$整除，记作$b\mid a$，并把$b$叫做$a$的因数，把$a$叫做$b$的倍数。人们常将$q$写成$a/b$或$\dfrac{a}{b}$。否则称$b$不能整除$a$或$a$不能被$b$整除，记作$b\not\mid a$。
设$a,b\not=0,c\not=0$为仨整数，若$b\mid a,c\mid b$，则$c\mid a$。
设$c\not=0,c\in\mathbb{Z}$，若$c\mid a_1,\cdots,a_n\in\mathbb{Z}$，则$\forall s_1,\cdots,s_n\in\mathbb{Z}$有$\displaystyle c\left|\sum_{i=1}^ns_ia_i\right.$。
设$a,b$为非零整数，若$a\mid b,b\mid a$，则$a=\pm b$。
设整数$n\neq0,\pm1$，若$n$除了因数$\pm1,\pm n$外没有其他因数，则$n$叫做素数（或质数、不可约数），否则$n$叫合数。设$n$是一个正合数，$p$是$n$的一个大于$1$的最小正因数，则$p$一定是素数且$p\leqslant\sqrt n$。设$n\in\mathbb{N}_+$，若对所有素数$p\leqslant\sqrt n$都有$p\not\mid n$，则$n\in\mathbb P$。素数有无穷多个。
设$a,b$是两个整数，其中$b>0$，则存在唯一整数$q,r$使得$a=qb+r,0\leqslant r<b$。其中$q$叫做$a$被$b$除所得的不完全商，$r$叫做$a$被$b$所除所得的余数。
设$x\in\mathbb{R}$，称$x$的整数部分为小于等于$x$的最大整数，记成$[x]$，这时有$[x]\leqslant x<[x]+1$。
设$f(x)$和$g(x)$都是$n\in\mathbb{Z_+}$的正值函数。若存在常数$C>0$，使得对任意$n\in\mathbb{Z_+}$都有$f(x)\leqslant Cg(n)$，就称$g(n)$为$f(n)$的界，记作$f(n)=O\left(g(n)\right)$，简记为$f=O(g)$。若对任意小的$\epsilon>0$，存在一个$N_0\in\mathbb{Z_+}$使得对任意正整数$n>N_0$都有$f(n)<\epsilon g(n)$，就称$g(n)$是比$f(n)$高阶的无穷量，记作$f(n)=o\left(g(n)\right)$，简记为$f=o\left(g\right)$。
设$a_1,\cdots,a_n$是$n(n\geqslant2)$个整数。若$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{align}
r_{-2}&=&q_0r_{-1}&+&r_0,&0<r_0<r_{-1},\\
r_{-1}&=&q_1r_0&+&r_1,&0<r1<r_0,\\
r_0&=&q_2r_1&+&r_2,&0<r_2<r_1,\\
&&\vdots\\
r_{n-2}&=&q_nr_{n-1}&+&r_n,&0<r_n<r_{n-1},\\
r_{n-1}&=&q_{n+1}r_n&+&r_{n+1},&r_{n+1}=0
\end{align}
$$
设$a,b$是任意两个正整数，则$r_n=0$时有$n\leqslant5\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$，有：
$$
\begin{pmatrix}
r_{-2}\\
r_{-1}
\end{pmatrix}
=\begin{pmatrix}
q_0&1\\
1&0
\end{pmatrix}
\begin{pmatrix}
r_{-1}\\
r_0
\end{pmatrix}
=\left(
\prod_{i=0}^{j+1}\begin{pmatrix}
q_{i}&1\\
1&0
\end{pmatrix}
\right)
\begin{pmatrix}
r_j\\
r_{j+1}
\end{pmatrix}
$$
从而有：
$$
\begin{pmatrix}
r_j\\
r_{j+1}
\end{pmatrix}
=\left(
\prod_{i=j+1}^0\begin{pmatrix}
0&1\\
1&-q_i
\end{pmatrix}
\begin{pmatrix}
r_{-2}\\
r_{-1}
\end{pmatrix}
\right)
$$
记：
$$
A_j=\begin{pmatrix}
s_j&t_j\\
u_j&v_j
\end{pmatrix}
$$
则有：
$$
\begin{pmatrix}
r_j\\
r_{j+1}
\end{pmatrix}
=A_j\begin{pmatrix}
r_{-2}\\
r_{-1}
\end{pmatrix},-2\leqslant j\leqslant n
$$
此时有：
$$
\begin{cases}
s_{-2}=1,\\
s_{-1}=0
\end{cases}
,\begin{cases}
t_{-2}=0,\\
t_{-1}=1
\end{cases}
,\begin{cases}
s_j=u_{j-1},\\
t_j=v_{j-1}
\end{cases}
,-1\leqslant j\leqslant n
$$
以及：
$$
\begin{pmatrix}
s_j\\
s_{j-1}
\end{pmatrix}
=\begin{pmatrix}
-q_j&1\\
1&0
\end{pmatrix}
\begin{pmatrix}
s_{j-1}\\
s_{j-2}
\end{pmatrix}
,\begin{pmatrix}
t_j\\
t_{j-1}
\end{pmatrix}
=\begin{pmatrix}
-q_j&1\\
1&0
\end{pmatrix}
\begin{pmatrix}
t_{j-1}\\
t_{j-2}
\end{pmatrix}
$$
即为广义欧几里得除法：设$a,b$为任意两个正整数，则$s_na+t_nb=(a,b)$，对于$0\leqslant j\leqslant n$，定义为：
$$
\begin{cases}
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{cases}
,0\leqslant j\leqslant n
$$
其中$q_j=\left[\dfrac{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$，则：
$$
\left(
\dfrac{a}{d},\dfrac{b}{d}
\right)
=\dfrac{(a,b)}{|d|},\left(
\dfrac{a}{(a,b)},\dfrac{b}{(a,b)}
\right)
=1
$$
设$a,b,c$是三个整数，且$b\neq0,c\neq0$，若$(a,c)=1$，则$(a,b,c)=(b,c)$。设$a_1,\cdots,a_n,c\in\mathbb Z$，若$(a_i,c)=1,1\leqslant i\leqslant 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\neq0$，令：
$$
\begin{cases}
(a_1,a_2)=d2,\\
(d_2,a_3)=d3,\\
\cdots,\\
(d_{n-1},a_n)=dn
\end{cases}
$$
则$(a_1,a_2,\cdots,a_n)=d_n$且$\displaystyle\exists s_1,s_2,\cdots,s_n\in\mathbb Z,\sum_{i=1}^ns_ia_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\neq0$，若$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\left|\prod_{i=1}^na_i\right.$，则$\exists 1\leqslant k\leqslant 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_+}$，有$[a,b]=ab$，且若$a\mid D,b\mid D$则$ab\mid D$。设$a,b\in\mathbb{Z_+}$，有$[a,b]=\dfrac{ab}{(a,b)}$，且若$a\mid D,b\mid D$则$[a,b]\mid D$。
设$a_1,\cdots,a_n\in\mathbb Z$，令：
$$
\begin{cases}
[a_1,a_2]=D_2,\\
[D_2,a_3]=D_3,\\
\cdots,\\
[D_{n-1},a_n]=D_n
\end{cases}
$$
则$[a_1,\cdots,a_n]=D_n$。若$\forall 1\leqslant k\leqslant n,a_k\mid D$，则$[a_1,\cdots,a_n]\mid D$。
整数分解定理：给定合数$n>1$，若$\exists a,b\in\mathbb Z,n\mid a^2-b^2,n\not\mid a-b,n\not\mid a+b$，则$(n,a-b)$和$(n,a+b)$都是$n$的真因数。
算数基本定理：任一整数$n>1$都可表示成素数的成绩，不考虑成绩顺序的情况下，表达式是唯一的，即$\displaystyle n=\prod_{i=1}^sp_i,p_1\leqslant\cdots\leqslant p_s,p_i\in\mathbb P$。
标准分解式：任一整数$n>1$可唯一表示成$\displaystyle n=\prod_{i=1}^sp^{\alpha_i},\alpha_i>0,p_i<p_j(i<j)\in\mathbb P$。设整数$n>1$，有$\displaystyle n=\prod_{i=1}^sp_i^{\alpha_i},\alpha$