密码学数学基础1

整除性

设$a,b\in Z$,如果存在一个$q\in Z$，使得$a=qb$,则称“b整除a”或”b是a的因子“,记为“$b|a$”,并用$b\not\mid a$表示b不整除a

则：

$b|0$
$1|a$
$0|a \iff a=0$
$b|a \iff b|-a \iff -b|a$

且：

定理一：$设a,b \in Z,则(b|a \land a|b) \iff a=\pm b$

素数

定义：设$n\in N\land n\geq2$,除了$1和n$以外,没有其它正整数整除n，则n称作“素数”（用p表示）；否则称为“合数”

注1：1既不是素数也不是合数
注2：若n为合数，则n=ab，其中$1<a<n,1<b<n$

引理2-1：任何大于1的整数必有素因子。
定理2-1：任何合数$n$都至少有一个不超过$\sqrt n$的素因子
定理2-2：(算数基本定理)

任何非零整数$n$，都可以表示成如下乘积形式：
$$
n=\pm p{_1}^{e_1}…p{_r}^{e_r}
$$
其中，$p_1,…p_r$是互不相同的素数，$e_1,…e_r$是正整数。

定理2-3:素数有无穷多个(欧几里得定理)

模运算

设$a,b\in Z \land b>0,若q,r\in Z满足a=qb +r,且0\leq r < b,$则定义:

$a \mod b := r$

$a \mod n = a - n⌊a/n⌋(向下整除); a∈Z,n∈N*(正整数)$

性质

$b|a \iff a \mod b = 0 $
$(a\pm b)\mod n =(a\mod n\pm b\mod n)\mod n $
$(ab)\mod n =(a\mod nb\mod n)\mod n $

最大公约数

定义

设$a,b\in Z,如果d \in Z \land d|a,d|b,$则称d是a和b的公因子(公约数)
如果$d\geq0$,且a和b的所有公因子都整除d,则称d是a和b的最大公约数,记作gcd(a,b)

公因数可以是任何整数
最大公因数只能是0或正整数，不能是负数

特别的，gcd(0,0)=1

互素

定义：设$a,b\in Z$,如果gcd(a,b)=1,则称a和b互素

设gcd(a,b)=d,则存在$q_1,q_2\in Z$,使得$a=q_1d,b=q_2d$,且$gcd(q_1,q_2)=1$,所以$q_1和q_2$互素。

欧几里得算法/辗转相除法

设$a\geq b\geq 0$,求gcd(a,b)
数学原理：

b=0时，gcd(a,0)=a
b>0时，gcd(a,b)=gcd(b,r)[a=qb+r]
最后gcd(b,r)=gcd($r,r_1$)=gcd($r_n,0$)=$r_n$

证明:

gcd递归定律：

$gcd(a,b)=gcd(b,a\mod b)$

要证:
$$
gcd(a,b)=gcd(b,a\mod b)
$$

∵根据整除性的线性性：
$$
d|(a和b的线性组合)
$$
∴
$$
gcd(a,b)|gcd(b, a \mod b)
$$

对于后一项：
$$
gcd(b,a \mod b)|gcd(a,b)
$$
设 c = gcd(b, a mod b)
∴ c|b 且 c|(a mod b)
∵ a = qb +r
∵ r = a mod b
∴ a = qb + a mod b ,即:
$$
a 是 b 和 (a \mod b) 的线性组合
$$
∴根据整除性的线性性：
$$
c | a
$$
∵ c | a且c | b

∴
$$
c | gcd(a,b)
$$
∴
$$
gcd(b,a \mod b)|gcd(a,b)
$$
得证.