密码学数学基础2

等价关系

一：
二元关系”=”：

自反性：对于所有$a\in R$,都有$a=a$
对称性：对于所有$a,b\in R$,都有$a=b\rightarrow b=a$
传递性：对于所有$a,b,c\in R$,都有$a=b,b=c\rightarrow a=c$

二：

二元关系”$\cong$”:

同样有自反性，对称性，传递性

定义

设集合S，以及一个定义在S上的二元关系R，若R满足以下性质，则称它为”等价关系”,以元组的形式表示

自反性：对于所有$a\in S$,都有($a,a)\in R$
对称性：对于所有$a,b\in S$,都有$(a,a)\in R$
传递性：对于所有$a,b,c\in S$,都有$(a,b)\in R,(b,c)\in R\rightarrow (a,c)\in R$

同余

定义

$a \equiv b(\mod n)$：设n为正整数，整数a，b分别模n，如果得到相同的余数(或n|(a-b))，就称a和b在模n的情况下满足同余关系，n被称为模数。同余是一种关系,而不是一种运算

性质

$a \equiv b(\mod n)\iff a=qn+b,\exists q\in Z\rightarrow n|a-b$

同余是一种等价关系,以下性质可以逆推

对于同一个除数，两个数的乘积与它们余数的乘积同余。
对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。
对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。
对于同一个除数，若三个数a≡b（mod m），b≡c（mod m），那么a,b,c三个数对于除数m都同余（传递性）。
对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么a±c≡c±d（mod m），（可加减性）。
对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么ac≡cd（mod m），（可乘性）

同余的运算性质

若$a \equiv b(\mod n)$，则：

$a\pm m \equiv b\pm m(\mod n),m\in Z$
$a* m \equiv b* m(\mod n),m\in Z$
$a^m \equiv b^m(\mod n),m\in N$

若同时$c \equiv d(\mod n)$,则：

$a\pm c \equiv b\pm d(\mod n)$
$a* c \equiv b* d(\mod n)$

乘法逆元

倒数：两个数的乘积为1，这两个数互为倒数

定义

设$a\in Z,n\in N,如果az\equiv 1(\mod n)$,则称z是模n下a的乘法逆元，记作$a^{-1}=z$

在模运算下，所有的形如$a^{-1}$的值都可以直接被代换成a在某模数下的乘法逆元，然后继续运算

只有当一个整数和模数互素的时候，它才会有乘法逆元，即：
$$
gcd(a,n)=1\iff 模n下有乘法逆元
$$
求乘法逆元：

扩展欧几里得算法

根据最大公约数表示定理：
$$
gcd(a,n)=1 \rightarrow as+tn = 1
$$
等式两边同时mod n:
$$
as \equiv 1 (\mod n)
$$
∴模n下a的逆元是s

∴调用gcd函数传入a和n算出的s即为乘法逆元

一次同余方程

$$
a \equiv b(\mod n)
$$

等价于下面这个形式，其中m是a，b，n的公因数
$$
a/m \equiv b/m(\mod n/m)
$$
如果gcd(m,n)=1,那么
$$
a/m \equiv b/m(\mod n)
$$
才是成立的

同余下的消去律

设$a,n\in Z,n>0$,如果$gcd(a,n)=d$,有
$$
az \equiv az’(\mod n)\rightarrow z \equiv z’(\mod n/d)
$$

同余方程的解

$x \equiv b(\mod n)$的解集：{$b\pm nk$,其中$k=0,1,2,…$}

同时有规律:
原模数为n，终模数为m，设n/m = d,有0~n-1之间解的数量等于d

一次同余方程有解的条件

若gcd(a,n)=d,则
$$
ax \equiv b(\mod n)有解 \iff d|b
$$

剩余类

等价类

等价类是等价关系的一种性质，若~是S上的等价关系，对于$a\in S$,定义其等价类为{$x\in S|x\sim a$}

由于同余关系是等价关系，所以同余中也有等价类，被叫做剩余类

剩余类

设$a\in Z$,定义其剩余类为{$x\in Z|x\equiv a(\mod n)$}
记作$[a]_n$简记为$[a]$,最简可化为a(如果没有歧义)

剩余类中每一个整数都叫做这个剩余类的代表元.
$Z_n$表示模n下所有剩余类的集合

定义剩余类之间的计算：

$[a]+[b]=[a+b]$

$[a][b]=[ab]$

即：最后得到的是以a+b/ab为代表元的剩余类

设$u,v\in Z_n$（$Z_n$是包含所有剩余类的集合）,若uv=[1],则u，v互为乘法逆元

再定义$Z_n^*$为$Z_n$中有乘法逆元的剩余类

$Z_n^*$与$Z_n$的关系

n为素数：$Z_n^*$=$Z_n$ \ {[0]}
n为合数：$Z_n^*$$\subsetneq$$Z_n$ \ {[0]}

中国剩余定理

一次同余方程组

设两两互素的模数$n_1,…,n_m\in N$,及任意整数$a_1,…,a_m\in Z$,并设$n=\prod_{i=1}^mn_i$
$$
\begin{cases}
x\equiv a_1(\mod n_1)\
…\
x\equiv a_m(\mod n_m)
\end{cases}
$$
为了求解这个方程，我们需要中国剩余定理CRT

中国剩余定理

设两两互素的模数$n_1,…,n_m\in N$,及任意整数$a_1,…,a_m\in Z$,并设$n=\prod_{i=1}^mn_i$，方程组
$$
\begin{cases}
x\equiv a_1(\mod n_1)\
…\
x\equiv a_m(\mod n_m)
\end{cases}
$$
必有解，设解为$a\in Z$.并且对任意$a’\in Z$,都有
$$
a’是方程组的解 \iff a \equiv a’(\mod n)
$$
求解方法：

得到每个方程组的模数$n_1,n_2,…$
求$n =\prod_{i=1}^mn_i$
求$n_i^*=n/n_i$
求$n_i^{-1}$(在对应模数下$n_i^$的乘法逆元)
求$e_i = n_i^{-1} * n_i^$
求$a = \sum_{i=1}^{m}e_ia_i$
求$a\mod n$为最后的结果

欧拉函数

如果已知集合$Z_{n}^*={Z_{n}中有乘法逆元的剩余类}={[a]|a=0,1,…,gcd(a,n)=1}$

那么，给定一个n，如何求$Z_{n}^*$中有多少个整数/剩余类呢

定义：欧拉函数，表示为$\phi (n)$，表示大于0，小于等于n的自然数和n互质的数的个数，
即：$\phi (n):=\left|Z_{n}^*\right|$（特别地，$\phi (1)=1$）

性质

设两两互素的正整数$n_1,…,n_m\in N$并设$n =\prod_{i=1}^mn_i$，那么有：$\phi (n)=\prod\limits^m_{i=1}\phi (n_i)$
用中国剩余定理+中国剩余映射求证

若p是素数，
$\phi (p^k)=p^{k-1}\phi (p)$
$\phi (p)=p-1$

欧拉定理和费马小定理

乘法阶

设$a\in Z_n^*$，使得$a^k\equiv 1(\mod n)$的最小正整数k称作a在模n下的乘法阶。简写为a的阶.

如果$a\in Z_n^*$，其阶为k，则$a^0,a^1,a^2,…,a^{k-1}$彼此不同(注意这里是剩余类，要取模)

性质

$$
a^i\equiv1(\mod n)\iff k|i\
a^i\equiv a^j(\mod n) \iff i\equiv j (\mod k)
$$

欧拉定理

若$a\in Z_n^*$，则：$a^{\phi(n)}\equiv 1\mod n$，且$k|\phi(n)$，k为a在模n下的阶。

由于乘法的封闭性，$Z_n^*$中每个元素彼此不同，且乘以a后得到的所有元素的集合还是$Z_n^*$

所以：

$\prod\limits_{b\in Z_n^*}b\equiv\prod\limits_{b\in Z_n^*}ab \mod n$

由于b是有剩余类的元素，那么个数是$\phi (n)$个

所以：

$\prod\limits_{b\in Z_n^*}b\equiv a^{\phi (n)}\prod\limits_{b\in Z_n^*}b \mod n$

得证