密码学数学基础

AI摘要

TianliGPT

生成中...

前言

本篇文章整理了学习密码学需要的部分数学基础

参考资料：

• 《初等数论》(第三版)，潘承洞 潘承彪 著
• 《抽象代数基础》(第二版) ，丘维声 著

数学基础

数论部分

整除

对于$a,b\in \mathbb{Z},a\ne0$，若存在$\exists q\in \mathbb{Z},s.t.\ b=aq$，则说明$a$整除$b$，也即$b$被$a$整除，记作$a\ |\ b$，同理也有$q\ |\ b$。

性质：

• $a\mid b⟺-a\mid b⟺a\mid -b⟺|a|\mid |b|$

• $a\mid b \wedge b\mid c \Longrightarrow a \mid c$

• $a\mid b\wedge a\mid c⟺\mathrm{\forall }x,y\in \mathbb{Z},a\mid (xb+yc)$

• $a\mid b\wedge b\mid a⟹b=\pm a$

• 设$m\ne 0$ ，那么 $a\mid b⟺ma\mid mb$

• 设 $b\ne 0$ ，那么 $a\mid b⟹|a|\le |b|$

• 设$a \neq 0, b=q a+c$ ，那么 $a\mid b⟺a\mid c$

倍数与约数

若$a \mid b$，则称$b$是$a$ 的倍数，$a$ 是$b$ 的约数。

0是所有非0整数的倍数。对于整数$b\ne0$ ，$b$ 的约数只有有限个。

平凡约数（平凡因数）：对于整数$b\ne0$，$\pm 1、\pm b$ 是$b$ 的平凡约数。当$b=\pm 1$ 时，$b$ 只有两个平凡约数。

对于整数$b\ne0$ ，$b$ 的其他约数称为真约数（真因数、非平凡约数、非平凡因数)。

约数的性质：

• 设整数$b\ne0$。当$d$ 遍历$b$ 的全体约数的时候，$\frac{b}{d}$ 也遍历$b$ 的全体约数。
• 设整数$b\gt0$，则当$d$ 遍历$b$ 的全体正约数的时候，$\frac{b}{d}$ 也遍历$b$ 的全体正约数。
• $(bq+r,b)=(r,b)$ 也即辗转相除法

公倍数的定义：

整数$a$ 与$b$ 的公倍数是满足如下条件的正整数$d$ :$a\mid d$ 且$b\mid d$ 。表示为$d=[a,b]$，最小公倍数就是最小的$d$

公约数的定义：

整数$a$ 与$b$ 的公约数是满足如下条件的正整数$d$ :$d\mid a$ 且$d\mid b$ 。表示为$d=(a,b)$，最大公约数就是最大的$d$

公倍数和公约数之间的关系：

$[a,b]=\frac{ab}{(a,b)}$

素数与合数

定义：设整数$p\ne0,\pm1$，如果除了平凡约数外没有其他约数，那么称$p$ 为素数(不可约数).若整数$a\ne 0,\pm 1$且$a$ 不是素数，则称$a$ 为合数

互素：$a$ 和$b$ 互素当且仅当它们的最大公约数为1，即$(a,b)=1$

算术基本定理

引理：设$p$ 是素数，$p\mid a_{1}a_{2}$，那么$p\mid a_{1}$ 和$p\mid a_{2}$ 至少有一个成立

算术基本定理：设正整数$a$ ，那么必有表示：$a= p_{1}p_{2}\cdot\cdot\cdot p_{s}$，其中$p_{j}(1\leq j\leq s)$是素数，该表示法唯一(不计次序)

同余

定义：设整数$m\ne0$ ，若$m\mid(a-b)$，称$m$ 为模数(模)，$a$ 同余于$b$ 模$m$，$b$ 是$a$ 对模$m$ 的剩余，记作$a\equiv b{\mathrm{~(mod~}}m)$.否则$a$ 不同余于$b$ 模$m$，$b$ 不是$a$ 对模$m$ 的剩余，记作$a\not\equiv a{\mathrm{~(mod~}}m)$.

性质：

• 同余是等价关系(满足自反、对称和传递)
  • 自反性：$a\equiv a{\mathrm{~(mod~}}m)$
  • 对称性：若$a\equiv b{\mathrm{~(mod~}}m)$，则$b\equiv a{\mathrm{~(mod~}}m)$
  • 传递性：若$a\equiv b{\mathrm{~(mod~}}m)$，$b\equiv c{\mathrm{~(mod~}}m)$，则$a\equiv c{\mathrm{~(mod~}}m)$
• 线性运算：若$a,b,c,d\in\mathbb{Z},m\in\mathbb{N}^{*},a\equiv b{\mathrm{~(mod~}}m{\mathrm{),c}}\equiv d{\mathrm{~(mod~}}m{\mathrm{)}}$则有：
  • $a\pm c\equiv b\pm d{\pmod{m}}$
  • $a\times c\equiv b\times d{\pmod{m}}$
• 若$a,b\in\mathbb{Z},k,m\in\mathbb{N}^{*},a\equiv b{\mathrm{~(mod~}}m{\mathrm{)}},$则$a k\equiv b k{\pmod{m k}}$
• 若$a,b\in\mathbb{Z},d,m\in\mathbb{N}^{*},d\mid a,d\mid b,d\mid m$，则当$a\equiv b{\mathrm{~(mod~}}m)$成立时，有${\frac{a}{d}}\equiv{\frac{b}{d}}\left(\mathrm{mod}\,\mathrm{\frac{~m~}{~d}}\right)$
• 若$a,b\in{\mathbb Z},d,m\in{\mathbb N}^{*},d\mid m$，则当$a\equiv b{\mathrm{~(mod~}}m)$成立时，有$a\equiv b{\mathrm{~(mod~}}d)$

同余类(剩余类)

同余类：是一个集合，可以将整数集合划分成为$m$个两两不相交的集合，并且同一个集合里面的数模$m$均同余。这$m$个集合均称为模$m$的同余类或者剩余类。记作$C_{i}$ ，其中$i \in (0,1,\dots,m-1)$. 如$m=5$时，$C_{1}=\{\dots,-9,-4,1,6,11,\dots\}$

既约剩余类：$C_{i}$ 中与$m$互素的剩余类. 如$m=4$时，$C_{3}=\{\dots,-5,-1,3,7,11,\dots\}$

剩余系

完全剩余系：对$m$ 个整数$a_{1},a_{2},\dots,a_{m}$，若对任意的数$x$ ，有且仅有一个数$a_{i}$ 使得$x$与$a_{i}$ 模$m$ 同余，则称这$m$ 个整数$a_{1},a_{2},\dots,a_{m}$ 为模$m$ 的完全剩余系，简称剩余系。如$\{0,1,2,3,4\}$为模5的一个完全剩余系

既约剩余系：对$t=\varphi(m)$ 个整数$a_{1},a_{2},\dots,a_{t}$，若$(a_{i},m)=1,\ \displaystyle\forall1\leq i\leq i$，对任意的数满足$(x,m)=1$的数$x$ ，有且仅有一个数$a_{i}$ 使得$x$与$a_{i}$ 模$m$ 同余，则称这$t$ 个整数$a_{1},a_{2},\dots,a_{t}$ 为模$m$ 的既约剩余系。如$\{1,3\}$为模4的一个既约剩余系。

欧拉函数

欧拉函数：记作$\varphi(m)$，表示的时小于等于$m$ 和$m$ 互质的数的个数。

性质：

• 若$m$为质数，$\varphi(m)=m-1$

• 若$(a,b)=1$，则$\varphi(ab)=\varphi(a)\varphi(b)$

• 若$\textstyle n=p^{k}$ ，其中$p$ 时质数，则$\varphi(n)=p^{k}-p^{k-1}$

• 由算术基本定理，设$n=\prod_{i=1}^{s}p_{i}^{k_{i}}$，其中$p_{i}$ 是质数，有$\varphi(n)=n\times\prod_{i=1}^{s}{\frac{p_{i}-1}{p_{i}}}$

欧拉(Euler)定理 & 费马(Fermat)小定理 & 威尔逊(Wilson)定理

欧拉定理：若$(a.m)=1$ ，则$a^{\varphi(m)}\equiv1{\pmod{m}}$

费马小定理：若$p$ 为素数，且$(a.p)=1$，则$a^{p-1}\equiv1{\pmod{p}}$

其实费马小定理就是欧拉函数的特殊情况

威尔逊定理：对于素数$p$ 有$(p-1)!\equiv-1{\pmod{p}}.$

线性同余方程

形如：$a x\equiv b{\pmod{n}}$ 的方程称作线性同余方程(Linear Congruence Equation)。其中，$a、b$ 和$n$ 为给定的整数，$x$ 为未知数。

当$b=1$ 时，方程的解$x$ 称作$a{\mathrm{~mod~}}n$的逆元，记作$a^{-1}$

中国剩余定理

中国剩余定理时解决形如

$\begin{cases} x \equiv a_1 \ (\text{mod} \ m_1) \\ x \equiv a_2 \ (\text{mod} \ m_2) \\ \vdots \\ x \equiv a_k \ (\text{mod} \ m_k) \end{cases}$

的同余方程组，其中$m_{1},m_{2},\dots,m_{k}$ 两两互质。

求解过程：

1、计算$M=m_{1}*m_{2}*\dots*m_{k}$

2、对于每一个方程

• 计算$M_{i}=\frac{M}{m_{i}}$
• 求解$M_{i}$ 在模$m_{i}$ 下的逆元$M_{i}^{-1}$
• 计算$c_{i} = M_{i}M_{i}^{-1}$

3、最终方程组的解为：$x=\sum_{i=1}^{k}a_{i}c_{i}{\mathrm{~(mod~}}M)$

原根

由欧拉定理可知：若$(a.m)=1$ ，则$a^{\varphi(m)}\equiv1{\pmod{m}}$

因此满足同余式$a^{n}\equiv1{\pmod{m}}$ 的最小正整数$n$ 存在，这个$n$ 称作$a$ 模$m$ 的阶，记作$\delta_{m}(a)$ 或$\mathrm{ord}_{m}(a)$

性质：

• $a,a^2,\dots,a^{\delta_{m}(a)}$ 模$m$ 两两不同余
• 若$a^{n}\equiv1{\pmod{m}}$，则$\delta_{m}(a)\mid n$
• 设$m\in\mathbb{N}^{*},\,\,\,\,a,b\in\mathbb{Z},\,\,\,\,(a,m)=(b,m)=1$，则$\delta_{m}(a b)\,=\,\delta_{m}(a)\delta_{m}(b)$ 的充分必要条件是$(\delta_{m}(a),\delta_{m}(b))=1$

原根：设$m\in\mathbb{N}^{*},\ \ g\in\mathbb{Z}$，若$(g,m)=1$，且$\delta_{m}(g)=\varphi(m)$，则称$g$ 为模$m$ 的原根

判定定理：设$m\geqslant3,(g,m)=1$，则$g$ 是模$m$ 的原根的充要条件是，对于$\varphi(m)$ 的每个素因数$p$，都有$g^{\frac{\varphi(m)}{p}}\not\equiv1\left(\mathrm{mod}~~m\right)$

个数：若一个数$m$ 有原根，则它的原根个数为$\varphi(\varphi(m))$

存在定理：一个数$m$ 存在原根当且仅当$m=2,4,p^{\alpha},2p^{\alpha}$，其中$p$ 为奇素数，$\alpha\in\mathbb{N^{*}}$

抽象代数部分

群

定义：是由一种集合以及一个二元运算所组成的，若$<G,\cdot>$ 是一个群，它满足以下性质：

• 封闭性：对于群$G$ 里任意的$a,b$，运算$a\cdot b$ 的结果也在$G$ 中
• 结合律：对于群$G$ 里任意的$a,b,c$，满足$(a\cdot b)\cdot c=a\cdot (b\cdot c)$
• 单位元：对于群$G$ 里存在唯一一个$e$ ，若满足$a\cdot e = e\cdot a=a$，则$e$ 为群$G$ 的单位元
• 逆元：对于 群$G$ 里任意的$a$，总存在一个元素$b$ 使得$a\cdot b=b\cdot a=e$，则称$b$ 为$a$ 的逆元，记作$a^{-1}$

衍生结构：

• 若$<G,\cdot>$ 只满足封闭性和 结合律，则称其为半群
• 若$<G,\cdot>$ 只满足封闭性、结合律和单位元，则称其为幺半群
• 若$<G,\cdot>$ 还满足交换律，即$a\cdot b=b\cdot a$ ，则称其为交换群或者阿贝尔群

环

定义：是一种集合以及两种二元运算(加法和乘法)所组成，注意此处的加法和乘法是广义上的加法和乘法，而非四则运算里面的加法和乘法。若$<R,+,\cdot>$ 是一个环，它满足以下性质：

• $<R,+>$ 构成交换群，其中单位元记作0，$R$ 中运算$a$ 的逆元记作$-a$
• $<R,\cdot>$ 构成半群
• $<R,+,\cdot>$ 满足分配律：对于$R$ 中所有的$a,b,c$ ，等式$a\cdot(b+c)=a\cdot b+a\cdot c$ 和$(a+b)\cdot c=a\cdot c+b\cdot c$ 成立

衍生结构：

• 若环$R$ 上的乘法还满足交换律，则称$R$ 为交换环
• 若环$R$ 存在乘法单位元$1$ ，则称$R$ 为幺环
• 若幺环$R$ 的所有非0元素$a$ 存在乘法逆元$a^{-1}$ ，则称$R$ 为除环

域

定义：域是交换除环

群里面的基本概念

在研究集合时，我们使用子集(subset)、函数(function)和等价关系商(quotient by an equivalence relation)等概念。在研究群时，我们通过等价关系用子群(subgroup)、同态(homomorphism)和商群(quotient group)来代替

子群

定义：群$G$ 的非空子集$H$ 如果对于$G$ 的运算也成一个群，则称$H$ 为$G$ 的子群(subgroup)，可记作$H<G$

陪集

定义：对于给定的$a\in G$，$H<G$ ，令

$aH\Longleftrightarrow \{ ah \mid h\in H\}$

称$aH$ 是子群$H$ 的一个左陪集 ，$a$ 称为左陪集$aH$ 的一个代表。

同理可以定义：对于给定的$a\in G$，$H<G$ ，令

$Ha\Longleftrightarrow \{ ha \mid h\in H\}$

称$Ha$ 是子群$H$ 的一个右陪集 ，$a$ 称为右陪集$aH$ 的一个代表。

群同态

定义：设$G$ 和$G^{'}$ 是两个群，如果$G$ 到$G^{'}$ 有一个映射$\sigma$ ，使得对于$G$ 中任意两个元素$a,b$ 都有

$\sigma(ab)=\sigma(a)\sigma(b)$

则称$\sigma$ 是群$G$ 到$G^{'}$ 的一个同态映射，简称同态(homomorphism)