信息安全数学基础
信息安全数学基础
整除
设$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$。
设$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,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$是任意两个正整数，则存在整数$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$是任意两个不全为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,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$。