信息安全数学基础定理证明复习

发表于 2024-11-25 更新于 2025-06-03 分类于 UESTC 阅读次数：本文字数： 7.3k

UESTC 软件学院互联网安全方向信息安全数学基础的定理复习。

本文仅针对UESTC软件学院互联网安全方向信息安全数学基础的定理复习，对于概念涉及较少，建议将本文用于复习而不是预习。

整除

性质

传递性，$a\mid b, b\mid c$ 则有 $a\mid c$。

利用整除的定义，b = ak证明

整除线性组合，$a\mid b, a\mid c$ ，当且仅当对任意 \[x,y\in Z\]，有$a\mid bx + cy$

利用整除的定义，b = ak证明（充分性+必要性）

整除式乘不为零的整数，仍整除（ $m\ne 0, a\mid b$当且仅当$ma\mid mb$）

用定义即可

互相整除则相等或互为相反数。$a\mid b, b\mid a$，则 \[a = b\] 或 \[a = -b\]

两次定义代换。

最大公因数gcd

性质

交换性
若$a\mid b$ 则 $\gcd(a,b) = a$
gcd整除线性组合。 $\gcd(a,b) \mid ax + by$

由整除的性质证明。

gcd可表示为线性组合

由整除的性质，$\mid ax + by\mid$ 的最小正整数$d$可以表示为 $a,b$ 的线性组合，再根据最小性得出$a = qd + r$的余数$r$也可以写为线性组合

$a = bq + r, \gcd(a, b) = \gcd(b, r)$

$r$ 可以表示为 $a,b$ 的线性组合。$(a,b)\mid r, (a,b)\mid b$，$(b,r)$也可以表示为线性组合。

$\gcd(a,c) = 1, b\mid c$，则 $\gcd(a, b) = 1$

利用$\gcd(a,b)\mid b, b\mid c$。

$a,b$约去$\gcd(a,b)$后互素

设出两个公因数后，根据整除的定义即可推导，注意gcd性质：所有公因数均整除gcd。

同余

同余有关性质的证明最重要的是化为整除的性质。

剩余类，剩余系的四个定理

设 $m$ 是正整数，整数 $a$ 满足 $\gcd(a,m) = 1$，$b$是任意整数。若 $x$ 遍历模 $m$ 的一个完全剩余系，则 $ax + b$ 也遍历模 $m$ 的一个完全剩余系。

证明方法：完全剩余系的数 $\{a_1,a_2,\cdots,a_n\}$ 模 $m$ 两两不同余，证明运算后的数也这样即可，我们可以使用反证法，这样可以消去 $b$ 并得出矛盾。

设 $m_1, m_2$ 是两个互素的正整数。如果 $x$ 遍历模 $m_1$ 的一个完全剩余系，$y$ 遍历模 $m_2$ 的一个完全剩余系，则 $m_1y + m_2x$遍历模 $m_1m_2$的一个完全剩余系

证明方法：还是反证法证明这些数互不相同，需要引理：若$a\equiv b \pmod m, d\mid m, d>0$，则$a\equiv b\pmod d$。

设 $m$ 是正整数。整数$a$满足 $(a, m) = 1 $。若 $x$ 遍历模 $m$ 的一个既约（简化）剩余系，则 $ax$ 也遍历模 $m$ 的一个既约剩余系。

证明方法：$\gcd(ax, m) = 1$，继续反证法，同余式中可以消去 $a$。

设 $m_1, m_2$ 是两个互素的正整数。如果 $x$ 遍历模 $m_1$ 的一个简化剩余系，$y$ 遍历模 $m_2$ 的一个简化剩余系，则 $m_1y + m_2x$遍历模 $m_1m_2$的一个简化剩余系

证明方法：需要先证明 $m_1y + m_2x$ 与 $m_1m_2$互素（反证法，假设$p$为公因数，用到整除性质6），其次，还要证明$m_1m_2$的任何一个完全剩余系都能表示为 $m_1y + m_2x$ ，结合定理二，其中简化剩余系中一个元素 $a$ 可以表示为 $m_1y + m_2x$ 的形式，证明 $\gcd(x,m_1) = \gcd(y, m_2) = 1$即可。

推论

对于互素的 $m,n$ 有 $\varphi(mn) = \varphi(m)\varphi(n)$

素数相关定理

欧拉定理

若 $m=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$，则 $\varphi(m)=m\prod_{i=1}^k(1-p_i)$。

先考虑单个方幂的欧拉函数，然后相乘。

费马小定理

设 $p$ 是一个素数，对于 $\forall a\in Z$，均有 $a^p\equiv a\pmod p$

群论

群：乘法封闭，满足结合律，有单位元，有逆元。

基本性质

单位元唯一

假设有两个，得出是同一个即可。

逆元唯一

假设有两个，得出是同一个即可。

消去律

乘逆元消去

对于群 $G$ 中任意元素 $a,b$ ，方程 $ax=b,xa = b$有唯一解。

先找到一个解，再证明唯一（消去律）。

$(ab)^{-1} = b^{-1}a^{-1}$

类似矩阵的逆，乘上逆元即可。

群的判定定理

方程 $ax = b, ya = b$在$G$中有唯一解，则 $G$ 是群。（满足结合律）

令 $a = b$可以找到单位元，然后令 $b = e$可以找到逆元。

有限群的判定

一个有乘法的有限集合$G$，若其乘法在$G$中封闭，且满足结合律和消去律，则$G$是群。

有限群就直接把元素设出来，用 $\forall a$左乘后证明元素互不相同，结合封闭性，利用群的方程组判定定理即可。

子群

性质

单位元，同一元素的逆元相同

反证法即可。

子群的构造

定义 <$a$> = $\{a^i\mid i\in Z\}$，则这就是一个子群。

利用群的定义逐条验证即可。

子群的判定定理

群 $G$ 的非空集合 $H$ 是一子群的充要条件是：对于 $\forall a,b \in H$，有 $ab^{-1}\in H$。

证明：必要性成立，主要证明充分性，令$b = a$可以得到单位元，$a = e$可以得到逆元，再证明封闭性：因为有逆元，取$b = b^{-1}$，那么$\forall a,b ,$ 有 $ab\in H$。

陪集

定义等价关系$R_H$：$a$~$b$ 当且仅当 $b^{-1}a\in H$

性质

对于 $\forall a\in G,aG = \{ah\mid h\in G\} = G$。

集合相等证明互相包含：注意$b = eb = aa^{-1}b = a(a^{-1}b)\in aG$

$GG = \{ah\mid h\in G, a\in G\} = G$

由上一条性质的并可以得到。

陪集里的元素可以看作一个等价类

设 $H$ 是 $G$ 的子群， $a\in G$，则在等价关系下 $R_H$下，$a$ 的等价类 $[a] = aH$

利用等价关系的定理证明任意元素都在陪集 $aH$ 中。

同一子群的两个陪集要么相等要么不相交，同一子群所有陪集的并就是群G

对于第一条性质，可以假设有公共元素，得到集合互相包含。$ah = bh_2h_1^{-1}h\in bH$。

对于第二条性质，有 $G = \cup_{a\in G}aH$，去掉重复的。

拉格朗日定理

子群的阶是群的因子，且 $|G| = |H|[G:H] $。

由上一条定理可以得到。

推论：$a^n = e$，欧拉定理

正规子群

$\forall a\in G, aH = Ha$，则 $H$ 是 $G$ 的正规子群。

中心

设 $N$ 是群 $G$ 中所有满足下列条件的集合：$na = an, \forall a\in G, n\in N$。那么 $N$ 是 $G$ 的正规子群，称为中心。

利用 $an_1 = n_1a,an_2=n_2a$推出$an_1n_2^{-1}=n_1n_2^{-1}a$

四个等价条件

设 $H$ 是 $G$ 的子群，$a\in G$，令 $a^{-1}Ha = \{a^{-1}ha\mid h\in H\}$，则一下四个条件等价：

$H$ 是 $G$ 的正规子群；
$\forall a\in G,h\in H$，有$a^{-1}ha\in H$
$\forall a\in G, a^{-1}Ha\subseteq H$
$\forall a\in G, a^{-1}Ha = H$

1 $\to$ 2：正规子群的定义

$2\to 3$：显然

$3\to 4$：令 $a = a^{-1}$，集合相等证明互相包含

$4\to 1$：左乘 $a$ 即可

商群

商群是一个群，里面的元素都是等价类。

商群的构成

设 $H$ 是 $G$ 的正规子群，记 $G/H = \{aH\mid a\in G\}$，在集合 $G/H$ 上定义运算：$(aH)\cdot(bH) = (ab)H$，则上述定义的运算给出了 $G/H$中的一个乘法，且 $G/H$ 在这个乘法下构成群，记为 $G$ 关于正规子群 $H$ 的商群。

这里 $H$ 是正规子群是以条件给出的，但是可以证明 $H$ 一定需要满足是一个正规子群。具体证法为：利用定义的运算，证明在该运算下，如果 $H$ 是正规子群，那么结果成立；否则，运算会得到一个陪集，且任一代表元均可代表该陪集，那么有 $(aH)(bH) = cH = abH$，乘以逆元可以得到 $HbH = bH$，此时证明相互包含即可。

然后再证明构成群：验证该运算下群的定义即可。

同态与同构

直接使用的结论：

在满同态映射下，单位元映射到单位元，逆元映射到映射象的逆元。

群同态基本定理(重要！！！)

设 $f$ 是群 $G$ 到 $G'$ 的一个满同态映射，$N$ 为 $f$ 的核，则 $N$ 是 $G$ 的一个正规子群，且 $G/N\cong G'$。

需要证明两个部分： $N$ 为正规子群和构造一个同构映射（即单射+满射=一一映射）。

先证明 $N$ 为子群，那么利用 $f(a)=f(b)=e',ab^{-1}\in N$即可。

然后是 $N$ 为正规子群，可以使用正规子群的等价条件证明（$cac^{-1}\in N, \forall c \in G,a\in N$）

接着是构造映射：定义$\phi(aN) = f(a)$（即把 $a$ 映射到对应的陪集 $aN$ 中）。

同一个数映射到唯一的象：证明$aN = bN$映射到$f(a) = f(b)$。注意$ab^{-1}\in N$，利用映射即可证明到$f(a) = f(b)$。

满射：$G$ 中至少有一个元素满足$f(a) = a'$（规定了是满同态映射）。

单射（同一个数只会被一个数映射到）：两个不同的数不会映射到同一个数，类似同一个数映射到唯一的象，注意$ab^{-1}\notin N$

再证明当前运算满足 $f(a)f(b)=f(ab)$即可。

循环群

循环群中元素的阶

引理1：$o(a) = n$，那么对于 $\forall m\in Z,a^m = e$当且仅当 $n\mid m$

当且仅当证明充分和必要，充分性易得。必要性需要，设 $m = qn + r$，由 $0\le r<n$ 推知$r = 0$。

引理2：$o(a) = n$，那么对于 $\forall k\in Z$，$o(a^k) = \frac{n}{\gcd(k,n)}$

$(a^k)^\frac{n}{d}=a^\frac{nk}{d}=(a^n)^\frac{k}{d}=e$，设 $l$ 是$a^k$的阶，那么 $l\mid \frac{n}{d}$，又有$a^{kl} = (a^k)^l=e$，所以 $n\mid kl$，同时除以 $\gcd(n,k)$可得 $l\mid \frac{n}{d}$即可证明。（主要是从 $a^k$ 的阶和 $a$ 的阶两个方向证明整除）

定理：$a^k$ 是 $G$ 的生成元的充要条件是$\gcd(n, k) = 1$。

由引理易得。

循环群的子群和商群

循环群的子群是循环群

只需要找到子群的一个生成元即可。设 $d$ 是最小的自然数，满足 $a^d\in H$，$a^tH $，设 $t = qd + r$，那么$a^r = a^t(a^d)^{-q}\in H$，由 $d$ 的极小性， $r = 0$，此时 $a^t = (a^d)^q\in$<$a^d$>

循环群的商群是循环群

$aH$是商群$G/H$的生成元。

有限 $n$ 阶循环群的子群的阶是 $n$ 的正因子，且对 $n$ 的每一个正因子 $q$ ，有且只有一个 $q$ 阶子群。

设 $s$ 是 $H $中的最小正指数，由于 $n = qs + r$，那么 $a^r = (a^{qs})^{-1}\in H$，所以 $r = 0, n = qs$。$H$可以表示为$H = \{e,a^s,\cdots,a^{(q-1)s}\}$，且当 $q$ 跑遍所有正因子时， $s$ 也跑遍所有正因子，所以只有一个 $q$ 阶子群。

循环群的同构

设 $G = $ <$a$>是循环群，那么：若 $a$ 的阶是无限，则 $G$ 与整数加群$Z$同构；若 $a$ 的阶是某个正整数 $m$ ，则 $G$ 与整数模 $ m $ 的剩余类加群同构。

构造同态映射，使用群同态基本定理即可。重点是找到中心 $N$

定义 $f:Z\to G$为 $f(k) = a^k$，则 $f$ 是个满射。且 \[ f(l+n) = a^{l+n} = a^la^n = f(l)f(n) \]，故 $f$ 是个群同态。

若阶无限，那么对 $n\in ker(f)$，有 $f(n) = a^n= e$，可以得出 $n = 0$，即$ker(f) = \{0\}$，使用群同态基本定理即可。

若阶为 $m$ ,$f(n) = a^n = e$，设 $n = qm + r$，则 $e = a^n = a^r$，由最小性，$r = 0$，所以 $m\mid n$。那么 $ker(f) = \{mk\mid k\in Z\} = mZ$，再使用群同态基本定理。

环（没有子环等）

概念的梳理

环：集合上定义加法和乘法两种运算，对于加法构成一个交换群，对于乘法满足结合律，乘法对加法满足左、右分配律。
交换环：满足乘法交换
零元：加法中的单位元（环中的单位元特指乘法的）
负元：加法中的逆元
有零因子环：若 $a,b\in R,ab = 0,a\ne 0,b\ne 0$，则 $R$ 为有零因子环，$a,b$分别为左零因子和右零因子。
整环：有单位元、无零因子的交换环（不一定所有元都有逆元）
除环：有单位元、至少包含一个不等于零的元、每一个不等于零的元都有逆元
域：交换除环（或加法，乘法都构成交换群）

多项式

不可约多项式

记住$GF(2)[x]$内五次以内的不可约多项式

规律：除了最高次为1，项数只能是奇数。

0	1
1	$x,x+1$
2	$x^2+x+1$
3	$x^3+x^2+1,x^3+x+1$
4	$x^4+x^3+x^2+x+1,x^4+x^3+1,x^4+x+1$
5	$x^5+x^3+x^2+x+1,x^5+x^4+x^2+x+1,x^5+x^4+x^3+x+1,x^5+x^4+x^3+x^2+1,x^5+x^3+1,x^5+x^2+1$

余元定理：用一次多项式 $x - a$ 去除 $f(x)$ 所得余式是域 $F$ 中的元素 $f(a)$
推论：$a $ 是 $f(x)$ 的根的充要条件是 $x - a\mid f(x)$
$f(x)$ 的次数为 $n$ ，那么最多存在 $n$ 个两两相异的根

！！！重要定理

如果 $f(x)$ 在 $F$ 上不可约，则 $F[x]/$<$f(x)$>为一个域。

只需要证明任意非零元均有乘法逆元即可（$f(x)$为不可约多项式）

需要用这个定义判定是不是域。

有限域

重要定理

设 $q = p^n$，其中 $p$ 是素数，$n$ 是正整数，则有限域 $F_q $ 的任意一个子域含有 $p^m$ 个元素，其中 $m\mid n$；反之，对于任意正整数 $m$ ，若$m\mid n$，则 $F_q$ 含有唯一一个子域包含 $p^m$ 个元素。

两种表示方法

多项式表示法

$F_q$ 中的元素可以表示成 $F_p$ 上 $a$ 的次数小于 $n$ 的多项式，其上的加法为多项式的加法，而乘法可以表示为模多项式 $f(a)$ 的乘法。

本原元表示法

设 $\xi$ 是 $F_q$ 中的本原元，则 $F_q = \{0, \xi, \xi^2, \xi^3,\cdots,\xi^{q-1}\}$，在本原元表示法下，乘法很容易实现，但加法需要结合 $F_q$ 的多项式表示来计算。

0	1
1	\(x,x+1\)
2	\(x^2+x+1\)
3	\(x^3+x^2+1,x^3+x+1\)
4	\(x^4+x^3+x^2+x+1,x^4+x^3+1,x^4+x+1\)
5	\(x^5+x^3+x^2+x+1,x^5+x^4+x^2+x+1,x^5+x^4+x^3+x+1,x^5+x^4+x^3+x^2+1,x^5+x^3+1,x^5+x^2+1\)