网络安全数学基础-课本笔记

部分内容来自 OI Wiki 数论基础

1. 整除

1.1 整数的除法

整除

设 $a,b\in \mathbf{Z}$，$a\ne 0$。如果 $\exists q\in \mathbf{Z}$，使得 $b=aq$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$；$b$ 不被 $a$ 整除记作 $a\nmid b$。

对于整除，我们有如下性质：

• $a\mid b⟺-a\mid b⟺a\mid -b⟺|a|\mid |b|$
• $a\mid b\wedge b\mid c⟹a\mid c$
• $a\mid b\wedge a\mid c⟺\forall x,y\in \mathbf{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\ne 0,b=qa+c$，那么 $a\mid b⟺a\mid c$。

带余除法

设 $a,b$ 为两个给定的整数，$b>0$，则存在唯一的一对整数 $q$ 和 $r$，满足 $a=qb+r,0\le r<b$。然后有 $r=0⟺b\mid a$。

最大公约数与最小公倍数

• 公约数的定义：d 为 a 和 b 的公约数，即 $d\mid a$ 且 $d\mid b$。
• 最大公约数：所有公约数里面最大的一个，记作 $gcd(a,b)$ 或 $(a,b)$，显然 $(a,b)\ge d$。
• 公倍数的定义：m 为 a,b 的公倍数，即 $m>0,a\mid m,b\mid m$。
• 最小公倍数：所有公倍数里面，最小的一个数，记作 $lcm(a,b)$ 或 $[a,b]$，显然 $[a,b]\le m$。

有如下常见的定理：

• $a\mid b⟹(a,b)=|a|,[a,b]=|b|$。
• 对任意整数 x，有 $(a,b)=(a,b+ax)$。
• 公倍数一定是最小公倍数的倍数，公约数一定是最大公约数的约数：这个可由带余除法证明或使用算数基本定理证明。
• 设 m 为正整数，则有 $m(a,b)=(ma,mb),m[a,b]=[ma,mb]$，证明同样可用算数基本定理。

同时有如下的性质：

• $(m,a)=1⟹(m,ab)=(m,b)$，证明同样用算数基本定理
• $(m,a)=1$，则 $m\mid ab⟹m\mid b$，证明同上
• $(a,b)=d$，则 $(\frac{a}{d},\frac{b}{d})=1$，证明同上
• $[a,b]=\frac{|ab|}{(a,b)}$，证明同上

对于 3 个参数的最大公约数和最小公倍数，有： $(a,b,c)=((a,b),c),[a,b,c]=[[a,b],c]$ 证明同样用算数基本定理

裴蜀定理

设 $a,b$ 是不全为零的整数。那么，对于任意整数 $x,y$，都有 $\gcd (a,b)\mid ax+by$ 成立；而且，存在整数 $x,y$，使得 $ax+by=\gcd (a,b)$ 成立。

即：$S=\{s:s=ax+by,x,y\in Z\}$ 由 $gcd(a,b)$ 的所有倍数构成，也因此 $ax+by=1$ 成立当且仅当 $a,b$ 互素。

1.2 算数基本定理

设正整数 $a$，那么必有表示：

$$a=p_1{p}_2\cdots p_s$$

其中 $p_j(1\le j\le s)$ 是素数。并且在不计次序的意义下，该表示唯一。

1.3 素数

• 素数有无穷多个。反证：设只有 $p_1,p_2,\dots ,p_m$，则存在 $p_1{p}_2\dots p_m+1$ 既不是合数也不在前面。
• 素数定理：${\lim }_{x\to +\infty }\frac{\pi (x)}{\frac{x}{\ln x}}=1$，其中 $\pi (x)$ 为小于等于 x 的素数的个数。证明见《什么是数学》P39、503。

具有特殊形式的几种素数：

• $F_n=2^{2^n}+1$：费马数，前五个为 0, 3, 5, 17, 257, 65537。$F_5$ 不是素数。
• $M_p=2^p-1$：Mersenne 素数
• 除以 4 余 3 的素数被称为 Blum 素数，两个 Blum 素数的乘积为 Blum 整数。

1.4 欧几里得算法

对于 $a=bk+c$，显然有 $gcd(a,b)=gcd(bk+c,b)=gcd(c,b)=gcd(b,c)$（定理详见），由此我们便得到欧几里得算法：$gcd(a,b)=gcd(b,a\mathrm{mod}b)$。（不妨设 $a>b$，且 a 不整除 b，因为最大公约数要求 $gcd(a,b)$ 中的 $a、b$ 均不为 0。）

拓展欧几里得算法：用于获得 $ax+by=gcd(a,b)$ 的一组可行解。

对于求 $(a_0,a_1)$，我们有：

\begin{eqnarray}a_0 & = & q_0a_1+a_2 \\a_1 & = & q_1a_2+a_3 \\a_2 & = & q_2a_3+a_4 \\a_3 & = & q_3a_4\end{eqnarray}

这样就有 $gcd(a_0,a_1)=(a_1,a_2)=\cdots =(a_3,a_4)=a_4$。

同时我们也发现倒数第二个式子中的 $a_4$ 可由 $a_2、a_3$ 线性表出。同理递推，最后 $a_2$ 可由 $a_0、a_1$ 线性表出，这样就求得了：$gcd(a_0,a_1)=a_4=p{a}_0+q{a}_1$。

递归算法设计

我们有： \begin{eqnarray}ax_1+by_1 & = & \gcd(a,b) \\ bx_2+(a\bmod b)y_2 & = & \gcd(b,a\bmod b)\end{eqnarray}

由欧几里得定理可知：$\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$

所以 $a{x}_1+b{y}_1=b{x}_2+(a\mathrm{mod}b)y_2$

又因为 $a\mathrm{mod}b=a-(\lfloor \frac{a}{b}\rfloor \times b)$

所以 $a{x}_1+b{y}_1=b{x}_2+(a-(\lfloor \frac{a}{b}\rfloor \times b))y_2$

$a{x}_1+b{y}_1=a{y}_2+b{x}_2-\lfloor \frac{a}{b}\rfloor \times b{y}_2=a{y}_2+b(x_2-\lfloor \frac{a}{b}\rfloor y_2)$

因为 $a=a,b=b$，所以 $x_1=y_2,y_1=x_2-\lfloor \frac{a}{b}\rfloor y_2$

算法只需返回当前 $a,b$ 下的 $x,y$，显然递归的最底层为 $gcd((a,b),0)=gcd(a,b)\cdot x+0\cdot y$，因此不妨取最终 $x=1,y=0$，直接返回，然后倒数第二层使用当前的 a,b 计算 $x=0,y=1-\lfloor \frac{a}{b}\rfloor \times 0=1$。这样写出递归，以下是对应的代码实现：

def Exgcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = Exgcd(b, a % b)
    return d, y, x - (a // b) * y

迭代算法设计

首先，当 $x=1$，$y=0$，$x_1=0$，$y_1=1$ 时，显然有：

$$\{\begin{array}{ll}ax+by& =a\\ a{x}_1+b{y}_1& =b\end{array}$$

已知 $a\mathrm{mod}b=a-(\lfloor \frac{a}{b}\rfloor \times b)$，下面令 $q=\lfloor \frac{a}{b}\rfloor$。参考迭代法求 gcd，每一轮的迭代过程可以表示为：

$$(a,b)\to (b,a-qb)$$

将迭代过程中的 $a$ 替换为 $ax+by=a$，$b$ 替换为 $a{x}_1+b{y}_1=b$，然后计算 $a-qb$，并把其中的 $a,b$ 用上述式子代替，可以得到：

$$\begin{array}{rl}& \{\begin{array}{ll}ax+by& =a\\ a{x}_1+b{y}_1& =b\end{array}\\ \to & \{\begin{array}{ll}a{x}_1+b{y}_1& =b\\ a(x-q{x}_1)+b(y-q{y}_1)& =a-qb\end{array}\end{array}$$

其中 $a-qb=a\mathrm{mod}b$，我们最终可以迭代得到 $(d,0)=gcd(a,b)=d$，此时我们也计算出了对应的 $x,y$。

因为迭代的方法避免了递归，所以代码运行速度将比递归代码快一点。

int gcd(int a, int b, int& x, int& y) {
  x = 1, y = 0;
  int x1 = 0, y1 = 1, a1 = a, b1 = b;
  while (b1) {
    int q = a1 / b1;
    // x <- x1, y <- y1, x1 <- x-qx1, y1 <- y-qy1
    // a <- b, b <- a-qb
    // 如果不怎么做的话注意使用中间变量，不要搞错
    // 注意到 x <- x1, y <- y1, a <- b
    // 那剩下 x1,y1,b 的计算算式结果用中间变量存储，然后先更改 x,y,a
    // 再把中间变量落实到 x1,y1,b 上即可
    tie(x, x1) = make_tuple(x1, x - q * x1);
    tie(y, y1) = make_tuple(y1, y - q * y1);
    tie(a1, b1) = make_tuple(b1, a1 - q * b1);
  }
  return a1; // 最终 a1 就是 gcd，且 x、y 也正确更新了
}

2. 同余

2.1 同余的基本概念和性质

基本概念和性质

书上最开始是由集合及映射的角度定义同余的，这里摘录 OI Wiki 上的等价定义如下：

[!定义] 设整数 $m\ne 0$。若 $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 b(\mathrm{mod}m)$。

这样的等式，称为模 $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 \mathbf{Z},m\in {\mathbf{N}}^{\ast },a\equiv b(\mathrm{mod}m),c\equiv d(\mathrm{mod}m)$ 则有：

  • $a\pm c\equiv b\pm d$。
  • $a\times c\equiv b\times d$。
  • 但是在同余式 $ac\equiv bc(\mathrm{mod}n)$ 中，如果我们想消去 $c$，必须满足 $(c,n)=1$（即 $c$ 与模数 $n$ 互质）。
  • 设 $f(x)={\sum }_{i=0}^n{a}_i{x}^i$ 和 $g(x)={\sum }_{i=0}^n{b}_i{x}^i$ 是两个整系数多项式，$m\in {\mathbf{N}}^{\ast }$，且 $a_i\equiv b_i,0\le i\le n$，则对任意整数 $x$ 均有 $f(x)\equiv g(x)$。进而若 $s\equiv t$，则 $f(s)\equiv g(t)$。

• 若 $a,b\in \mathbf{Z},k,m\in {\mathbf{N}}^{\ast }$，有 $a\equiv b(\mathrm{mod}m)⟺ak\equiv bk(\mathrm{mod}mk)$。

• 若 $a,b\in \mathbf{Z},d,m\in {\mathbf{N}}^{\ast },d\mid m$，则当 $a\equiv b(\mathrm{mod}m)$ 成立时，有 $a\equiv b(\mathrm{mod}d)$（注意：反过来并不一定成立）。

• 若 $a,b\in \mathbf{Z},l,m\in {\mathbf{N}}^{\ast }$，则 $a\equiv b(\mathrm{mod}{m}^l)⟹a\equiv b(\mathrm{mod}m)$。

结合最大公约数和最小公倍数的概念，我们还有性质：

设$m\in N^{+},\forall \le i\le n,m_i\in N^{+}$，有：

• $a\equiv b(\mathrm{mod}m)⟹(a,m)=(b,m)$，证明：$a=pm+b$，然后用最大公约数的性质。
• $\forall i\le i\le n,a\equiv b(\mathrm{mod}{m}_i)⟺a\equiv b(\mathrm{mod}[m_1,m_2,\dots ,m_n])$

若 $k\in Z,ak\equiv bk(\mathrm{mod}m)$，则 $a\equiv b(\mathrm{mod}\frac{m}{(k,m)})$。

模逆元

然后是新概念，模逆元：

[!定义] 对于非零整数 $a,m$，如果存在 $b$ 使得 $ab\equiv 1(\mathrm{mod}m)$，就称 $b$ 是 $a$ 在模 $m$ 意义下的 逆元（inverse）。

这相当于说，$b$ 是线性同余方程 $ax\equiv 1(\mathrm{mod}m)$ 的解。根据裴蜀定理，当且仅当 $\gcd (a,m)=1$，即 $a,m$ 互素时，逆元 $a^{-1}\mathrm{mod}m$ 存在，且在模 $m$ 的意义下是唯一的。

然后模逆元可以用来解线性同余方程（linear congruence equation）：$ax\equiv b(\mathrm{mod}n)$。

首先，考虑 $a$ 和 $n$ 互素的情形，即 $\gcd (a,n)=1$ 的情形。此时，可以计算 $a$ 的 逆元 $a^{-1}$，并将方程两边同乘以 $a^{-1}$，这就得到方程的唯一解：

$$x\equiv b{a}^{-1}(\mathrm{mod}n).$$

紧接着，考虑 $a$ 和 $n$ 不互素的情形，即 $\gcd (a,n)=d>1$ 的情形。此时，原方程不一定有解。例如，$2x\equiv 1(\mathrm{mod}4)$ 就没有解。因此，需要考虑两种情形：

• 当 $d$ 不能整除 $b$ 时，方程无解。对于任意的 $x$，方程左侧 $ax$ 都是 $d$ 的倍数，但是方程右侧 $b$ 不是 $d$ 的倍数。因此，它们不可能相差 $n$ 的倍数，因为 $n$ 的倍数也一定是 $d$ 的倍数。因此，方程无解。

• 当 $d$ 可以整除 $b$ 时，可以将方程的参数 $a,b,n$ 都同除以 $d$，得到一个新的方程： $a^{\prime }x\equiv b^{\prime }(\mathrm{mod}{n}^{\prime }).$

  其中，$\gcd (a^{\prime },n^{\prime })=1$，也就是说，$a^{\prime }$ 和 $n^{\prime }$ 互素。这种情形已经在前文解决，所以，可以通过求解逆元得到方程的一个解 $x^{\prime }$.

  显然，$x^{\prime }$ 也是原方程的一个解。但这并非原方程唯一的解。由于转化后的方程的全体解为： $\{x^{\prime }+k{n}^{\prime }:k\in \mathbf{Z}\}.$

  这些解中落在区间 $[0,n-1]$ 的那些，就是原方程在区间 $[0,n-1]$ 中的全部解： $x\equiv (x^{\prime }+k{n}^{\prime })(\mathrm{mod}n),k=0,1,\cdots ,d-1.$

总结这两种情形，线性同余方程的 解的数量 等于 $d=\gcd (a,n)$ 或 $0$。

同余类

[!定义] 设 $l\in N^{+}$，对于整数 $i$，记 $\bar{i}=\{x:x\in Z,x\equiv i(\mathrm{mod}n)\}$

此时每个集合 $\bar{i}$ 叫做模 $n$ 的一个同余类，如果 $gcd(i,n)=1$，这样的同余类称作模 $n$ 的缩同余类。

显然有：

• 模 n 至多有 n 个两两不同的同余类，它们的并集就是 $Z$。
• 缩同余类中的每个数都与 n 互素。
• 缩同余类的个数即为 0~n+1 中和 n 互素的数的个数，我们把这个数表示为 $\varphi (n)$，称作欧拉函数。

欧拉函数有性质：$n={\sum }_{d\mid n}\phi (d)$。

证明：

对于 k 取 1~n，我们设 $f(x)$ 表示 $\gcd (k,n)=x$ 的 k 的取值的个数，显然由于 k 的取值总共有 n 个，因此 $n={\sum }_{i=1}^{n}f(i)$。

对于 $f(d)$，即求 $\gcd (k,n)=d$ 中 k 的取值的个数，因为 d 均为 k、n 因子，因此有 $\gcd (\frac{k}{d},\frac{n}{d})=1$，相当于互素，求互素个数就是 $\phi (\frac{n}{d})$。

由此我们发现 $f(x)=\phi (\frac{n}{x})$，因此 $n={\sum }_{x=1}^n\phi (\frac{n}{x})$，显然此处 $x$ 只能取 $n$ 的因子，因此 $n={\sum }_{d\mid n}\phi (\frac{n}{d})$，又因为对于 d 为 n 的因子，遍历 $\frac{n}{d}$ 相当于遍历 $d$，因此 $n={\sum }_{d\mid n}\phi (d)$。

完全剩余系与既约剩余系（缩系）

为方便讨论，对集合 $A,B$ 和元素 $r$，我们引入如下记号：

• $r+A:=\{r+a:a\in A\}$；
• $rA:=\{ra:a\in A\}$；
• $A+B:=\{a+b:a\in A,b\in B\}$；
• $AB:=\{ab:a\in A,b\in B\}$。

我们把模 $m$ 的同余类全体构成的集合记为 ${\mathbf{Z}}_m$，即 ${\mathbf{Z}}_m:=\{r\mathrm{mod}m:0\le r<m\}$

不难发现：

• 对任意整数 $a$，$a+{\mathbf{Z}}_m={\mathbf{Z}}_m$；
• 对任意与 $m$ 互质的整数 $b$，$b{\mathbf{Z}}_m={\mathbf{Z}}_m$。

由抽屉原理可知：

• 任取 $m+1$ 个整数，必有两个整数模 $m$ 同余。
• 存在 $m$ 个两两模 $m$ 不同余的整数。

由此我们给出完全剩余系和既约剩余系的定义：

[!定义] $n$ 个整数 $a_1,a_2,\cdots ,a_n$ 彼此模 $n$ 不同余，称为模 $n$ 的完全剩余系（简称完系），$\phi (n)$ 个整数 $b_1,b_2,\cdots ,b_{\phi (n)}$ 彼此模 $n$ 不同余且均与 $n$ 互素，称为模 $n$ 的既约剩余系（简称缩系）。

注意概念差异的辨析：

• 模 m 的同余类是一个由无数个与某数在模 m 下同余的整数构成的集合。
• $Z_m$ 是包含模 m 所有同余类的集合。
• 完全剩余系是从模 m 的每个同余类中各取一个整数，组成的 m 个整数的集合

我们又把模 $m$ 的既约同余类全体构成的集合记为 ${\mathbf{Z}}_m^{\ast }$，即 ${\mathbf{Z}}_m^{\ast }:=\{r\mathrm{mod}m:0\le r<m,(r,m)=1\}$

在这里，注意有：

• 对于任意的整数 $a$ 和与 $m$ 互质的整数 $b$，$b{\mathbf{Z}}_m^{\ast }={\mathbf{Z}}_m^{\ast }$。
• 但是 $a+{\mathbf{Z}}_m^{\ast }$ 不一定为 ${\mathbf{Z}}_m^{\ast }$。这一点与 ${\mathbf{Z}}_m$ 不同。

上述关于 ${\mathbf{Z}}_m^{\ast },{\mathbf{Z}}_m$ 的性质对于相应的完全剩余系或既约剩余系依然成立。

Wilson 定理

[!定义] 若 $p$ 为素数，则 $(p-1)!\equiv -1(\mathrm{mod}p)$

证明：$p=2$ 时测试成立

其他情况下，因为 $p$ 为素数，所以对于 $1\le a\le p-1$，显然其与 $p$ 互素，因此存在模逆元。

要注意 $a$ 和 $a^{-1}$ 可能相等：$a=a^{-1}$，当且仅当 $a^2\equiv 1(\mathrm{mod}p)$，即： $0\equiv a^2-1\equiv (a+1)(a-1)(\mathrm{mod}p)$

因此只有 $a=1,p-1$ 的情况下模逆元为其自身，又因为 $p$ 为素数，为奇数，所以 $2\le a\le p-2$ 是若干对模逆元（这一共有偶数个数字），这若干对模逆元的乘积为 1。所以 $(p-1)!\equiv 1\cdot (p-1)\equiv -1(\mathrm{mod}p)$。

2.2 Euler 定理和 Fermat 小定理及其应用

Euler 函数

积性函数

[!定义] 在数论中，若函数 $f(n)$ 满足 $f(1)=1$，且 $f(xy)=f(x)f(y)$ 对任意互质的 $x,y\in {\mathbf{N}}^{\ast }$ 都成立，则 $f(n)$ 为 积性函数。

在数论中，若函数 $f(n)$ 满足 $f(1)=1$ 且 $f(xy)=f(x)f(y)$ 对任意的 $x,y\in {\mathbf{N}}^{\ast }$ 都成立，则 $f(n)$ 为 完全积性函数。

下面我们来证明欧拉函数为积性函数。

对正整数 $m$，我们有如下定理：

• 若 $m=m_1{m}_2,1\le m_1,m_2$，令 $Z_{m_1},Z_{m_2}$ 分别为模 $m_1,m_2$ 的 完全 剩余系，则对任意与 $m_1$ 互质的 $a$ 均有：$Z_m=a{Z}_{m_1}+m_1{Z}_{m_2}$
• 若 $m=m_1{m}_2,1\le m_1,m_2,(m_1,m_2)=1$，令 $Z_{m_1}^{\ast },Z_{m_2}^{\ast }$ 分别为模 $m_1,m_2$ 的 既约 剩余系，则：$Z_m^{\ast }=m_2{Z}_{m_1}^{\ast }+m_1{Z}_{m_2}^{\ast }.$ 为模 $m$ 的 既约 剩余系。

证明：见剩余系的符合，懒得看了

由上述定理，当 $(m_1,m_2)=1$ 时，模 $m$ 的既约剩余系可以表示为： $Z_m^{\ast }=\{m_{2}x+m_{1}y\mid x\in Z_{m_1}^{\ast },y\in Z_{m_2}^{\ast }\}$

这个公式实际上建立了一个从笛卡尔积 $Z_{m_1}^{\ast }\times Z_{m_2}^{\ast }$ 到 $Z_m^{\ast }$ 的映射，而欧拉函数 $\varphi (m)=|Z_m^{\ast }|$ 等于既约剩余系中元素的个数。我们可以确定这个映射是一个双射（一一对应）。

在集合 $\{m_{2}x+m_{1}y\}$ 中：

• 变量 $x$ 有 $|Z_{m_1}^{\ast }|=\varphi (m_1)$ 种取值。
• 变量 $y$ 有 $|Z_{m_2}^{\ast }|=\varphi (m_2)$ 种取值。
• 因此，组合出的形式共有 $\varphi (m_1)\times \varphi (m_2)$ 个。

下面证明唯一性（不重复）

假设存在两组不同的系数 $(x_1,y_1)$ 和 $(x_2,y_2)$ 使得： $m_2{x}_1+m_1{y}_1\equiv m_2{x}_2+m_1{y}_2(\mathrm{mod}m)$ 由于 $m=m_1{m}_2$，这个等式在模 $m_1$ 下也成立： $m_2{x}_1+0\equiv m_2{x}_2+0(\mathrm{mod}{m}_1)⟹m_2(x_1-x_2)\equiv 0(\mathrm{mod}{m}_1)$ 因为已知 $(m_1,m_2)=1$，根据同余性质，我们可以消去 $m_2$，得到： $x_1\equiv x_2(\mathrm{mod}{m}_1)$ 同理可得 $y_1\equiv y_2(\mathrm{mod}{m}_2)$。

这说明不同的 $(x,y)$ 组合必然产生模 $m$ 不同余的元素。

因此我们有 $n$ 与 $m$ 互素时 $\phi (nm)=\phi (n)\times \phi (m)$。

下一步推导

我们已经证明了欧拉函数 $\varphi (n)$ 是积性函数，下一步要推导：

1. 求出当 $n$ 是素数的幂（即 $n=p^k$）时的表达式。
2. 利用积性性质将结论推广到任意正整数。

计算 $\varphi (p^k)$，设 $p$ 为素数，$k\ge 1$ 为正整数。 我们要找在 $1$ 到 $p^k$ 之间，有多少个数与 $p^k$ 互质：

• 总数：共有 $p^k$ 个数。
• 不互质的情况：因为 $p$ 是唯一的质因子，一个数与 $p^k$ 不互质，当且仅当这个数是 $p$ 的倍数。
• 找出 $p$ 的倍数：在 $1,2,3,\dots ,p^k$ 中，$p$ 的倍数有：$p,2p,3p,\dots ,(p^{k-1})p$显然，这类数字共有 $p^{k-1}$ 个。

因此用总数减去不互质的个数，$\varphi (p^k)=p^k-p^{k-1}=p^k\left(1-\frac{1}{p}\right)$。

根据算数基本定理，$n=p_1^{a_1}{p}_2^{a_2}\dots p_r^{a_r}$，因此： $\varphi (n)=\varphi (p_1^{a_1})\cdot \varphi (p_2^{a_2})\dots \varphi (p_r^{a_r})$ 进一步化简： $\varphi (n)=p_1^{a_1}\left(1-\frac{1}{p_1}\right)\cdot p_2^{a_2}\left(1-\frac{1}{p_2}\right)\dots p_r^{a_r}\left(1-\frac{1}{p_r}\right)$ 重排： $\varphi (n)=n{\prod }_{i=1}^r\left(1-\frac{1}{p_i}\right)$

Euler 定理

若 $n$ 是正整数，且 $a$ 与 $n$ 互质（即 $\gcd (a,n)=1$），则： $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

其中 $\phi (n)$ 是欧拉函数，表示小于等于 $n$ 且与 $n$ 互质的正整数的个数。

证明欧拉定理最常用的方法是利用既约剩余系的性质，证明如下：

1. 构造既约剩余系：设集合 $S=\{x_1,x_2,\dots ,x_{\phi (n)}\}$ 是模 $n$ 的一个既约剩余系。这意味着集合中的每一个元素都与 $n$ 互质，且它们在模 $n$ 下两两不同余。

2. 构造辅助集合：我们将 $S$ 中的每一个元素都乘以 $a$，得到一个新的集合 $S^{\prime }$： $S^{\prime }=\{a{x}_1,a{x}_2,\dots ,a{x}_{\phi (n)}\}$

3. 证明 $S^{\prime }$ 也是模 $n$ 的既约剩余系

要证明这一点，需要满足两个条件：

• 元素仍与 $n$ 互质：因为 $\gcd (a,n)=1$ 且 $\gcd (x_i,n)=1$，根据数论性质，它们的乘积 $\gcd (a{x}_i,n)=1$。
• 元素在模 $n$ 下仍两两不同：假设存在 $a{x}_i\equiv a{x}_j(\mathrm{mod}n)$。由于 $\gcd (a,n)=1$，我们可以根据同余式的消去律，在等式两边同时除以 $a$，得到 $x_i\equiv x_j(\mathrm{mod}n)$。这与原集合 $S$ 中元素互不相同矛盾。

因此，$S^{\prime }$ 只是 $S$ 中元素在模 $n$ 意义下的一个重新排列。

4. 建立等式

既然 $S$ 和 $S^{\prime }$ 在模 $n$ 意义下包含相同的元素，那么它们的乘积也应当在模 $n$ 下相等：

$(a{x}_1)\cdot (a{x}_2)\dots (a{x}_{\phi (n)})\equiv x_1\cdot x_2\dots x_{\phi (n)}(\mathrm{mod}n)$

提取左边的 $a$，总共有 $\phi (n)$ 个：

$a^{\phi (n)}\cdot (x_1{x}_2\dots x_{\phi (n)})\equiv (x_1{x}_2\dots x_{\phi (n)})(\mathrm{mod}n)$

5. 消去公共项

令 $P=x_1{x}_2\dots x_{\phi (n)}$。因为每个 $x_i$ 都与 $n$ 互质，所以它们的乘积 $P$ 也一定与 $n$ 互质（即 $\gcd (P,n)=1$）。

根据消去律，我们可以从等式两边同时消去 $P$：

$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

证毕。

Fermat 小定理

[!定义] 设 $p$ 是素数。对于任意整数 $a$ 且 $p\nmid a$，都成立 $a^{p-1}\equiv 1(\mathrm{mod}p)$.

显然，Fermat 小定理可以理解为 Euler 定理的特殊情况，但同时 Fermat 小定理也有不依赖 Euler 定理的证明方法，且能用于推出 Euler 定理，相关证明见教材及《什么是数学》。

快速幂及素性检验

书上写的是从高位到低位的快速幂，下面是一个例子

假设我们要算 $x^{13}(\mathrm{mod}n)$。$13$ 的二进制是 $(1101{)}_2$，对应的系数是 $a_3=1,a_2=1,a_1=0,a_0=1$。

算法从最高位 $a_3$ 开始处理。每一次循环，它都先做一个平方（相当于指数翻倍），如果有 $1$，再补一个乘法（指数加 1）。这样子我们想操作一次指数就只需要对结果进行一次操作。

我们来手动模拟一遍：

步骤	处理二进制位	操作逻辑	计算过程	此时的 y 等于
初始	-	-	$y=1$	$1$
$i=3$	$a_3=1$	平方 $\to$ 乘 $x$	$1^2\cdot x$	$x^1$
$i=2$	$a_2=1$	平方 $\to$ 乘 $x$	$(x^1{)}^2\cdot x$	$x^3$
$i=1$	$a_1=0$	平方 $\to$ 不乘	$(x^3{)}^2$	$x^6$
$i=0$	$a_0=1$	平方 $\to$ 乘 $x$	$(x^6{)}^2\cdot x$	$x^{13}$

然后快速幂可以用于素性检验，具体的看书。

2.3 孙子定理

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 $n_1,n_2,\cdots ,n_k$ 两两互质）：

$$\{\begin{array}{ll}x& \equiv a_1(\mathrm{mod}{n}_1)\\ x& \equiv a_2(\mathrm{mod}{n}_2)\\ & ⋮\\ x& \equiv a_k(\mathrm{mod}{n}_k)\end{array}$$

过程

1. 计算所有模数的积 $n$；
2. 对于第 $i$ 个方程：
   1. 计算 $m_i=\frac{n}{n_i}$；
   2. 计算 $m_i$ 在模 $n_i$ 意义下的 逆元 $m_i^{-1}$；
   3. 计算 $c_i=m_i{m}_i^{-1}$（不要对 $n_i$ 取模）。
3. 方程组在模 $n$ 意义下的唯一解为：$x={\sum }_{i=1}^k{a}_i{c}_i(\mathrm{mod}n)$。

2.4 同余方程的一般理论

两个变量下的情形

• $ax+by=n$ 有整数解的充分必要条件是 $(a,b)\mid n$。
• $(a,b)=1$，$x_0,y_0$ 为方程 $ax+by=n$ 的一个整数解（显然这个方程对于 n 取任意整数都有解），则：$\{\begin{array}{c}x=x_0+bt\\ y=y_0-at\end{array}$为该方程的通解，其中 $t\in Z$。

由上述两个定理，我们可以推出如下定理：

同余方程 $ax+b\equiv 0(\mathrm{mod}m)$ 有解当且仅当 $(a,m)\mid b$，而且在模 $m$ 的意义下解的数量为 $(a,m)$ 个。用这种方法要求我们先将模数变小：$\frac{a}{(a,m)}x+\frac{b}{(a,m)}\equiv 0(\mathrm{mod}\frac{m}{(a,m)})$ 然后求得同余方程的一个解 $x_0$，原方程的通解为：$x_0+t\frac{m}{(a,m)}(\mathrm{mod}m)$ 其中 $0\le t<(a,m),t\in Z$。

另外，这种同余方程也可以用模逆元章节学到的方法进行求解。

多个变量下的情形

上课没讲，书上有，自己看，这里写一点基本的。

$n$ 元一次同余方程 $a_1{x}_1+\cdots +a_n{x}_n\equiv b(\mathrm{mod}m)$ 有解的充分必要条件是 $(a_1,\dots ,a_n,m)\mid b$，若方程有解，则其在模 $m$ 下的解的数量为 $m^{n-1}(a_1,\dots ,a_n,m)$。

解的例子见 P49

3. 二次剩余

3.1 Legendre 符号(1): Euler 判别法

二次剩余可以认为是在讨论求模意义下 开平方 运算的可行性。

[!定义] 令整数 $a$，$p$ 满足 $(a,p)=1$，若存在整数 $x$ 使得$x^2\equiv a(\mathrm{mod}p),$则称 $a$ 为模 $p$ 的二次剩余，否则称 $a$ 为模 $p$ 的二次非剩余。后文可能在模 $p$ 显然的情况下简写成二次（非）剩余。 / 设 $p$ 为奇素数，在模 $p$ 的一个缩系中，恰有 $\frac{p-1}{2}$ 个模 $p$ 的二次剩余，$\frac{p-1}{2}$ 个模 $p$ 的二次非剩余；在模 $p$ 的意义下，$1^2,2^2,\dots ,(\frac{p-1}{2}{)}^2$ 即为全部模 $p$ 的二次剩余。

Legendre 符号

[!定义] 对 奇素数 $p$ 和整数 $a$，定义 Legendre 符号如下：$\left(\frac{a}{p}\right)=\{\begin{array}{ll}0,& p\mid a,\\ 1,& (p\nmid a)\wedge ((\exists x\in \mathbf{Z}),a\equiv x^2(\mathrm{mod}p)),\\ -1,& \text{otherwise}.\end{array}$

即对于 $(a,p)=1$ 的 $a$，

• $a$ 是模 $p$ 的二次剩余当且仅当 $\left(\frac{a}{p}\right)=1.$
• $a$ 是模 $p$ 的二次非剩余当且仅当 $\left(\frac{a}{p}\right)=-1.$

Euler 判别法

对奇素数 $p$ 和满足 $(a,p)=1$ 的整数 $a$，有$a^{\frac{p-1}{2}}\equiv \{\begin{array}{ll}1(\mathrm{mod}p),& (\exists x\in \mathbf{Z}),a\equiv x^2(\mathrm{mod}p),\\ -1(\mathrm{mod}p),& \text{otherwise}.\end{array}$

即对上述的 $p$ 和 $a$，

1. $a$ 是 $p$ 的二次剩余当且仅当 $a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$.
2. $a$ 是 $p$ 的二次非剩余当且仅当 $a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$.

Legendre 符号具有完全积性：对任意整数 $a_1,a_2$，

$$\left(\frac{a_1{a}_2}{p}\right)=\left(\frac{a_1}{p}\right)\left(\frac{a_2}{p}\right).$$

我们有推论：对整数 $a,b$，$p\nmid b$ 有

$$\left(\frac{a{b}^2}{p}\right)=\left(\frac{a}{p}\right).$$

由 Legendre 符号的完全积性我们可以得到：两个二次剩余之积为二次剩余，两个二次非剩余之积为二次剩余，而一个二次剩余和一个二次非剩余之积为二次非剩余。

3.1 Legendre 符号(2): 二次互反律

对任意整数 $a$，

$$a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p).$$

进一步，我们有推论：

$$\left(\frac{1}{p}\right)=1.$$ $$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{ll}1,& p\equiv 1(\mathrm{mod}4),\\ -1,& p\equiv 3(\mathrm{mod}4).\end{array}$$

这个规律就是说 $p(\mathrm{mod}4)$ 为 1 对应的 Legendre 符号就取 1，否则取 -1。（模 4 判别法）

然后我们要计算 $\left(\frac{2}{p}\right)$，一种方法是使用 Gauss 引理：

[!定理] 设 $p$ 是奇素数，$(n,p)=1$，对整数 $k\left(1\le k\le (p-1)/2\right)$，令 $r_k=nk\mathrm{mod}p$，设 $A=\{r_k:r_k<p/2\}$，$B=\{r_k:r_k>p/2\}$，则$\left(\frac{n}{p}\right)=(-1{)}^{|B|}.$

然后我们对奇素数 $p$，有

$$\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{ll}1,& p\equiv \pm 1(\mathrm{mod}8),\\ -1,& p\equiv \pm 3(\mathrm{mod}8).\end{array}$$

这个规律就是说 $p(\mathrm{mod}8)$ 为 1 或 7 对应的 Legendre 符号就取 1，否则取 -1。（模 8 判别法）

然后就能证出二次互反律，怎么证你别管，但是我们有二次互反律：

[!定律] 设 $p$，$q$ 是两个不同的奇素数，则 $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}.$

根据二次互反律我们有：

• 只有当 $p$ 和 $q$ 同时是 $4n+3$ 型（即除以 4 余 3）时，右上角的指数才是两个奇数相乘，结果是奇数，整个右边等于 $-1$。
• 其他情况下（只要 $p,q$ 中有一个除以 4 余 1），右边永远是 $+1$。

因此有：两个素数互相“是不是对方的平方剩余”，它们的答案通常是一样的；只有当它们都是 $4n+3$ 型时，答案才正好相反。

3.3 Jacobi 符号

定义与用途

雅可比符号是勒让德符号的推广。勒让德符号 $\left(\frac{a}{p}\right)$ 要求 $p$ 必须是奇素数，而雅可比符号 $\left(\frac{a}{n}\right)$ 中的 $n$ 可以是任何正奇整数（可以是合数），其标准定义为多个勒让德符号的乘积。

换句话说，勒让德符号只对“分子”有积性，而雅可比符号对“分子”和“分母”都具有积性。

有了模数积性后，计算会变得极其简单。我们可以对比一下：

如果只用勒让德符号：

计算 $\left(\frac{7}{113}\right)$ 时，你要用二次互反律翻转成 $\left(\frac{113}{7}\right)$。

计算 $\left(\frac{113}{7}\right)=\left(\frac{1}{7}\right)=1$。

这步很快，因为 113 是素数。但如果你遇到 $\left(\frac{10}{113}\right)$，你必须先把它拆成 $\left(\frac{2}{113}\right)\left(\frac{5}{113}\right)$，才能继续下一步。

使用雅可比符号：

你不需要关心分子或分母是否为素数（只要分母是奇数）。

你可以直接翻转、取模、再翻转，像处理普通分数一样。例如：

$\left(\frac{1001}{9973}\right)\stackrel{\text{翻转}}{\to }\left(\frac{9973}{1001}\right)\stackrel{\text{取模}}{\to }\left(\frac{964}{1001}\right)\dots$

差别

1. 判断二次剩余的能力
   • 勒让德符号 $\left(\frac{a}{p}\right)=1$： 一定意味着 $a$ 是模 $p$ 的二次剩余（即方程 $x^2\equiv a(\mathrm{mod}p)$ 有解）。
   • 雅可比符号 $\left(\frac{a}{n}\right)=1$： 不一定意味着 $a$ 是模 $n$ 的二次剩余。
   • 注意： 如果 $\left(\frac{a}{n}\right)=-1$，则 $a$ 一定不是模 $n$ 的二次剩余。
2. 此前定理的应用能力：
   • $-1$ 的性质（模 4）：均成立 $\left(\frac{-1}{n}\right)=(-1{)}^{\frac{n-1}{2}}=\{\begin{array}{ll}1& n\equiv 1(\mathrm{mod}4)\\ -1& n\equiv 3(\mathrm{mod}4)\end{array}$
   • $2$ 的性质（模 8）：均成立 $\left(\frac{2}{n}\right)=(-1{)}^{\frac{n^2-1}{8}}=\{\begin{array}{ll}1& n\equiv 1,7(\mathrm{mod}8)\\ -1& n\equiv 3,5(\mathrm{mod}8)\end{array}$
   • Euler 判别法：仅对勒让德符号成立
   • 二次互反律：均成立，只有当 $a$ 和 $n$ 都是 $4k+3$ 型（即模 4 余 3）时，翻转才变号；否则符号不变。

计算

我们一般按照上面的例子一样，翻转（利用二次互反律）、取模、再翻转不断缩小来进行计算，当然，拆分成勒让德符号计算也是合法的。

n 为 Blum 数（3t+4）时的特殊性质

由于 $n=3t+4$，由模 4 判别法可得，$\left(\frac{-1}{n}\right)=-1$，由这个可以推出另外两个性质：

• 若 $\left(\frac{a}{n}\right)=1$，则要么 $a$ 为模 $n$ 的二次剩余，要么 $-a$ 为模 $n$ 的二次剩余。
• 设 $n=pq$ 为 Blum 数，$a$ 为模 $n$ 的二次剩余，若 $u,v$ 为 $a$ 模 $n$ 的两个不同的平方根，则 $\left(\frac{u}{n}\right)=-\left(\frac{v}{n}\right)$。

且上述第二个定理中的 $u,v$ 是可求的，由如下定理：

• 设 $p$ 为 Blum 素数，$a$ 为模 $p$ 的二次剩余，则 $a$ 模 $p$ 的两个平方根为 $\pm a^{\frac{p+1}{4}}$。

3.4 二次同余方程

研究方程：$a{x}^2+bx+c\equiv 0(\mathrm{mod}{p}^l)$

• 前提条件：$p$ 为奇素数，$l\in {\mathbb{N}}^{+}$，$a,b,c$ 为整数系数。
• 简化假设：假设 $p^l\nmid a$。若 $p^l\mid a$，方程则退化为一次同余方程。

情形 I：$l=1$（模 $p$ 的情况）

当模数为素数 $p$ 且 $(a,p)=1$ 时，通过配方法将方程转化。

转化步骤：

1. 方程两边同乘 $4a$（因为 $p$ 是奇素数且 $(a,p)=1$，故 $4a$ 与 $p$ 互素）： $4a(a{x}^2+bx+c)\equiv 0(\mathrm{mod}p)$
2. 配方整理得： $(2ax+b{)}^2\equiv b^2-4ac(\mathrm{mod}p)$
3. 令 $y=2ax+b$，$\Delta =b^2-4ac$，原方程转化为： $y^2\equiv \Delta (\mathrm{mod}p)$，其中 $\Delta$ 为定值，而 $y$ 受 $x$ 影响的一个变量

对于 $y^2\equiv \Delta (\mathrm{mod}p)$，由二次剩余的学习，我们可知其解的数量为： $1+\left(\frac{\Delta }{p}\right)$

如果 $y_0$ 是方程 $y^2\equiv \Delta (\mathrm{mod}p)$ 的一个解，则原方程的解为： $x\equiv (2a{)}^{-1}(\pm y_0-b)(\mathrm{mod}p)$

注：$(2a{)}^{-1}$ 表示 $2a$ 模 $p$ 的逆元。

题目示例：

求出：$x^2+x+1\equiv 0(\mathrm{mod}7)$ 的所有解

解方程 $x^2+x+1\equiv 0(\mathrm{mod}7)$：

1. 配方得 $(2x+1{)}^2\equiv -3\equiv 4(\mathrm{mod}7)$。
2. 解得 $2x+1\equiv 2(\mathrm{mod}7)$ 或 $2x+1\equiv 5(\mathrm{mod}7)$。
3. 最终解为：$x\equiv 2(\mathrm{mod}7)$ 和 $x\equiv 4(\mathrm{mod}7)$。

注意：考试的时候能配方就配方，不需要上述的那种程序化方法，但是可以计算下 $\left(\frac{\Delta }{p}\right)$ 确定是否有解。

情形 II：$l\ge 2$（只讨论 $(a,p)=1$ 时的情形）

针对方程：$x^2\equiv n(\mathrm{mod}{p}^l)$，其中 $\gcd (n,p)=1$。

• 有解条件： 与模 $p$ 时一致。只要勒让德符号 $(\frac{n}{p})=1$，方程就有解。
• 解的个数： 只要有解，就恰好有两个解。
• 解法核心： 这是一个“平滑过渡”的过程。如果你已知 $x^2\equiv n(\mathrm{mod}p)$ 的解，可以通过特定的提升方法（类似牛顿迭代的思想）一步步算到模 $p^l$ 的解。

模为 2 的幂次 $2^l$ 的情形 ($p=2$)

之前的讨论都要求 $p$ 为奇素数，但在 $p=2$ 时情况比较特殊：

针对方程：$x^2\equiv n(\mathrm{mod}{2}^l)$，其中 $n$ 为奇数：

模数	有解的条件	解的个数	备注
$(\mathrm{mod}2)$	$n\equiv 1(\mathrm{mod}2)$ (即 $n$ 是奇数)	1 个解	必为 $x\equiv 1$
$(\mathrm{mod}4)$	$n\equiv 1(\mathrm{mod}4)$	2 个解	解为 $\pm 1(\mathrm{mod}4)$
$(\mathrm{mod}{2}^l)(l\ge 3)$	$n\equiv 1(\mathrm{mod}8)$	4 个解	重要考点！ 只要模 8 余 1 就有 4 个解

一般合数模 $m$ 的情形

针对方程：$x^2\equiv n(\mathrm{mod}m)$

• 基本思路： 利用中国剩余定理 (CRT)。
• 步骤：
  1. 将 $m$ 分解质因数：$m=p_1^{l_1}{p}_2^{l_2}\dots$
  2. 分别求出在每个分量 $x^2\equiv n(\mathrm{mod}{p}_i^{l_i})$ 下的解。
  3. 用 CRT 把这些局部解组合起来。
• 解的个数： 如果每个分量方程分别有 $N_1,N_2,\dots$ 个解，那么总解数就是它们的乘积：$N=N_1\times N_2\times \dots$

4. 原根和指数

4.1 原根

阶

首先我们引入阶的定义：

本节中，总是假设模数 $m\in {\mathbf{N}}_{+}$ 和底数 $a\in \mathbf{Z}$ 互素，即 $(a,m)=1$，也记作 $a\perp m$．

对于 $n\in \mathbf{Z}$，幂次 $a^n\mathrm{mod}m$ 呈现一种循环结构．这个循环节的最小长度，就是 $a$ 模 $m$ 的阶。阶就定义为幂 $a^n\mathrm{mod}m$ 第一次回到起点 $a^0\mathrm{mod}m=1$ 时的指数：

[!定义] 对于 $a\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a\perp m$，满足同余式 $a^n\equiv 1(\mathrm{mod}m)$ 的最小正整数 $n$ 称作 $a$ 模 $m$ 的阶（the order of $a$ modulo $m$），记作 ${\delta }_m(a)$ 或 ${\mathrm{ord}}_m(a)$．

阶在运算时有如下性质：

• 若 $(a,n)=1,a\equiv b(\mathrm{mod}n)$，则 ${\delta }_n(a)={\delta }_n(b)$
• 若 $(a,n)=1,a^k\equiv a^l(\mathrm{mod}n)$，则 $k\equiv l(\mathrm{mod}{\delta }_n(a))$
• 设 $a^{-1}$ 是 $a$ 模 $n$ 的逆，则 ${\delta }_n(a^{-1})={\delta }_n(a)$。

显然阶有如下两个性质：

• 对于 $a\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a\perp m$，幂次 $a^0(=1),a,a^2,\cdots ,a^{{\delta }_m(a)-1}$ 模 $m$ 两两不同余．
• 对于 $a,n\in \mathbf{Z},m\in {\mathbf{N}}_{+}$ 且 $a\perp m$，同余关系 $a^n\equiv 1(\mathrm{mod}m)$ 成立，当且仅当 ${\delta }_m(a)\mid n$．

又由第二条规律及欧拉定理 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$，我们有：${\delta }_m(a)\mid \phi (m)$。

因此：幂次 $a^0(=1),a,a^2,\cdots ,a^{{\delta }_m(a)-1}$ 只遍历了模 m 的缩系的一个子集，遍历到 $\phi (m)$ 次时正好将这个子集遍历了若干次（这个过程中不会遍历到缩系中的其他部分），此时有 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

然后我们自然就可以引入原根了：

原根

原根是一些特殊元素——它的阶就等于所有模 𝑚 既约剩余系的个数．

[!定义] 对于 $m\in {\mathbf{N}}_{+}$，如果存在 $g\in \mathbf{Z}$ 且 $g\perp m$ 使得 ${\delta }_m(g)=|{\mathbf{Z}}_m^{\ast }|=\phi (m)$，就称 $g$ 为 模 $m$ 的原根（primitive root modulo $m$）．其中，$\phi (m)$ 是欧拉函数。

若 $(a,n)=1$，则 $a^0=1,a^1,...,a^{{\phi }_n(a)-1}$ 这 ${\phi }_n(a)$ 个数模 $n$ 两两不同余。特别地，当 $a$ 是模 $n$ 的原根时，这 ${\phi }_n(a)$ 个数是模 $n$ 的一个缩系。

原根的存在性

缩系这样表示在解决某些数论问题很方便，但是不是每个整数都有原根，我们下面给出是否有原根的判定方法：

只有以下四种形式的整数 $n$ 才有原根：

1. $n=1,2,4$（其原根分别为不存在，1，3）
2. $n=p^l$ （$p$ 为奇素数，$l\ge 1$）
3. $n=2p^l$ （$p$ 为奇素数，$l\ge 1$）

判定 a 是否是模 m 的原根

对于原根的计算，由于 ${\delta }_m(a)\mid \phi (m)$，即 $a$ 模 m 的阶必须是 $\phi (m)$ 的因子，然后我们可以对这些因子进行判定：只有当 $\phi (m)$ 的素因子均不是 $a$ 的阶，即对于任意素因子 $t,a^t\not\equiv 1(\mathrm{mod}m)$ 时才有阶为 $\phi (m)$，此时为原根。

注意，实际这里只需要对素因子进行判定，因为例：如果 $a^2\equiv 1(\mathrm{mod}m)$，那么 $a^{2\times 3}=a^6$ 也一定 $\equiv 1(\mathrm{mod}m)$，显然素因子是阶时，合数因子是数因子的倍数，此时不能称之为阶，但也与 1 同余。

举例：判定 3 是不是模 7 的原根

第一步：计算 $\phi (m)$

$m=7$，因为 7 是质数，所以 $\phi (7)=7-1=6$。

第二步：找到 $\phi (m)$ 的所有质因子

$\phi (7)=6$，它的质因子有 2 和 3。

第三步：进行“排除法”判定

我们要检查 $a=3$ 的“阶”是否可能比 6 小。如果阶比 6 小，它一定是 $6/2=3$ 或者 $6/3=2$ 的约数。

1. 检查质因子 2：计算 $3^{\frac{6}{2}}=3^3(\mathrm{mod}7)$
   • $3^3=27$
   • $27÷7=3\dots 6$，所以 $3^3\equiv 6(\mathrm{mod}7)$
   • 结论：不等于 1，通过。
2. 检查质因子 3：计算 $3^{\frac{6}{3}}=3^2(\mathrm{mod}7)$
   • $3^2=9$
   • $9÷7=1\dots 2$，所以 $3^2\equiv 2(\mathrm{mod}7)$
   • 结论：不等于 1，通过。

最后结果：

既然 $3^2\not\equiv 1$ 且 $3^3\not\equiv 1$，那么 $3$ 在模 7 下的阶不可能是 2 或 3（以及它们的约数）。那么它的阶只能是最大的那个可能值，即 6。

所以，3 是模 7 的原根。

计算模 m 的原根

我们从正整数 $2,3,4,\dots$ 进行试验（利用上述素因子判定法），判断是否为模 m 的原根，在找到一个之后，我们有结论：模 $m$ 的全部原根就是集合 $\{g^k\mid 1\le k\le \phi (m),(k,\phi (m))=1\}$。

4.2 指数

上节内容告诉我们知道，当模 $n$ 有原根 $g$ 时，$1,g^1,\dots ,g^{\phi (n)-1}$ 为模 $n$ 的一个缩系，从而对于每个与 $n$ 互素的整数 $a$，必定存在唯一的整数 $k$ ($0\le k<\phi (n)$)，使得 $a\equiv g^k(\mathrm{mod}n)$ 这样一来，当模 $n$ 有原根 $g$ 时，通过原根 $g$，模 $n$ 的缩系与模 $\phi (n)$ 的完系之间就建立了一一对应。由此我们引出指数的定义

[!定义] 整数 $k$ 叫做 $a$ 对模 $n$ 以原根 $g$ 为底的指数，如果 $a\equiv g^k(\mathrm{mod}n)$ 并且 $0\le k<\phi (n)$，其中 $(a，n)=1$，$n\in {\mathbb{N}}^{+}$。记作 $k={\mathrm{ind}}_{g}a$，在不混淆的情况下，可简记为 $\mathrm{ind}a$.

指数有如下的计算性质（设 $g$ 为模 $n$ 的原根，$(a,n)=(b,n)=1$）：

• $g^{\mathrm{ind}a}\equiv a(\mathrm{mod}n)$
• $g^h\equiv g^k(\mathrm{mod}n)⟺h\equiv k(\mathrm{mod}\phi (n))$
• ${\mathrm{ind}}_g(ab)\equiv {\mathrm{ind}}_{g}a+{\mathrm{ind}}_{g}b(\mathrm{mod}\phi (n))$
• 对每个正整数 $m$ 有 $\mathrm{ind}{a}^m\equiv m\cdot \mathrm{ind}a(\mathrm{mod}\phi (n))$

这表明其具有和对数函数类似的性质。

在给定 $n,g,{\mathrm{ind}}_{g}a$ 是可以利用快速幂算法计算出 $a\equiv g^{{\mathrm{ind}}_{g}a}(\mathrm{mod}n)$，但是在给定 $n,g,a$ 时，要计算出对应指数 ${\mathrm{ind}}_{g}a$ 则非常困难，这就是所谓的离散对数问题。

换底公式与阶

换底公式：如果你有两个不同的原根 $g_1$ 和 $g_2$： $in{d}_{g_2}a\equiv (in{d}_{g_2}{g}_1)\cdot (in{d}_{g_1}a)(\mathrm{mod}\phi (n))$

• 考点：已知一个底数的指数表，让你求另一个底数下的指数。

指数与阶的关系：元素 $a$ 的阶 ${\delta }_n(a)$ 可以通过指数快速求得： ${\delta }_n(a)=\frac{\phi (n)}{(in{d}_{g}a,\phi (n))}$

• 考点：给出指数表，让你求某个数的阶是多少。

5. 群

这节及后面内容均为 Gemini 直接利用课本内容生成，没有润色，可能写的不太好，需要注意。自己添加的部分内容用高亮表示。

啊啊啊啊啊宝宝你是一个群、半群、含幺半群、阿贝尔群、循环群、有限群、正规子群、商群、环、交换环、整环、除环、域、理想、主理想、主理想环、商环、素理想、极大理想、多项式环、域、有限域、素域、分裂域

5.1 群的基本概念

核心定义

设 $G$ 是一个非空集合，如果在 $G$ 上定义了一个二元运算 “$\cdot$”（统称为“乘法”），且满足以下 4 个金标准，则称 $(G,\cdot )$ 为一个群：

特性	数学表达	通俗理解
(1) 封闭性	$\forall a,b\in G⟹a\cdot b\in G$	两个成员运算后，结果还在圈子里，没跑出去。
(2) 结合律	$(a\cdot b)\cdot c=a\cdot (b\cdot c)$	先算前两个还是后两个，结果一样（括号不影响结果）。
(3) 单位元	$\exists e\in G,\text{使得 }e\cdot g=g\cdot e=g$	存在一个“透明人” $e$，任何数和它运算都不变。
(4) 逆元	$\forall g\in G,\exists g^{-1}\in G,\text{使得 }g\cdot g^{-1}=e$	每个成员都有一个“影子”，两者抵消后回到单位元。

一些相关的名词：

• 阿贝尔群（Abel 群）： 如果群还满足 交换律（即 $a\cdot b=b\cdot a$），它就升级为“阿贝尔群”或“交换群”。这是加密算法中最常用的一类群。
• 符号习惯：
  • 乘法表示： 单位元记作 $1$ 或 $e$，逆元记作 $g^{-1}$。
  • 加法表示： 若运算定义为“+”，则单位元记作 $0$，逆元记作 $-g$（负元）。
  • 幂运算： $a^n=a\cdot a\cdots a$（$n$ 个相乘）；在加法群中写作 $na=a+a+\cdots +a$。
• 半群： 只满足 (1) 封闭性、(2) 结合律。
• 含幺半群： 满足 (1) 封闭性、(2) 结合律 + (3) 单位元（多了一个“幺”即单位元）。
• 群： 满足全部四条。

群的等价定义于 P100 提到：

1. 左/右准则： 只要证明有“左单位元”和“左逆元”，它就是群。
2. 方程准则： 如果集合满足封闭性和结合律，且对于所有的 $a$、$b$，方程 $ax=b$ 和 $ya=b$ 在集合内都有解，那么它也是一个群。

群的符号滥用现象

在严谨的数学定义里，群是一个二元组 $(G,\cdot )$，其中 $G$ 是集合，$\cdot$ 是运算。但数学家们为了说话省力，经常使用一种叫“滥用符号”（Abuse of notation）的习惯。

• 逻辑上： 群 = 集合 + 运算规则。
• 习惯上： 当运算规则已经明确（比如题目说“群 $G$”，默认运算就是 $G$ 里的那个运算）时，我们就直接用集合的名字 $G$ 来代表整个群。
• 类比： 就像我们说“篮球队”时，虽然篮球队由“球员 + 战术”组成，但我们通常直接用球员名单（集合）来代指这支球队。在证明子群时，我们默认子群继承了大群 $G$ 的运算，所以只需关注这个“子集”是否也玩得转这套规则。

群的运算与阶

群的运算不一定是普通的乘法或加法，但为了方便，通常借用这两者的符号。

概念	乘法群 (Multiplicative Group)	加法群 (Additive Group)
单位元	记作 $e$ 或 $1$	记作 $0$
逆元	$g^{-1}$	$-g$
$n$ 次运算	$a^n=a\cdot a\cdots a$ ($n$个相乘)	$na=a+a+\cdots +a$ ($n$个相加)
指数律	$a^m\cdot a^n=a^{m+n}$	$ma+na=(m+n)a$
指数律 2	$(a^m{)}^n=a^{mn}$	$m(na)=(mn)a$

一些常见特殊群的记号如下，看见了来查：

记号	名称	含义描述
${\mathbb{Z}}_n$	模 $n$ 加法群	$\{0,1,\dots ,n-1\}$ 在模 $n$ 加法下。
${\mathbb{Z}}_n^{\ast }$ 或 $U({\mathbb{Z}}_n)$	模 $n$ 乘法群	与 $n$ 互质的数在模 $n$ 乘法下。
$S_n$	对称群	$n$ 个元的全部置换构成的群。
$A_n$	交错群	$n$ 个元的全部偶置换构成的群。
$D_n$	二面体群	正 $n$ 边形的对称变换群。
$GL(n,F)$	一般线性群	$F$ 域上所有 $n\times n$ 可逆矩阵。
$SL(n,F)$	特殊线性群	行列式为 $1$ 的可逆矩阵。

群的阶 (Order)

在网安数学中，“阶”这个词有两种含义，一定要分清楚：

• 群的阶： 指群 $G$ 中元素的个数，记作 $|G|$。
  • 有限群：元素个数有限。
  • 无限群：元素个数无限。
• 元素的阶： 设 $a\in G$，使得 $a^k=e$ 成立的最小正整数 $k$ 称为元素 $a$ 的阶。
  • 通俗理解：元素 $a$ 自乘多少次能回到单位元（“打回原形”）。
  • 如果不存在这样的 $k$，则称 $a$ 是无限阶的。

元素阶的整除性质的一个引理： 若 $ord(a)=n$，则 $a^m=e$ 当且仅当 $n\mid m$。

下述是利用这个引理的一个例题。

[!题目] 设 $G$ 为群，$a\in G$，且 $ord(a)=st$，$s,t\in N^{+}$。证明：$ord(a^t)=s$。

解答:

记 $ord(a^t)=k$。

1. 证明 $k\mid s$：

   因为 $(a^t{)}^s=a^{st}=e$（由 $ord(a)=st$ 可知），根据阶的性质，必有 $k\mid s$。

2. 证明 $s\mid k$：

   由于 $(a^t{)}^k=e$，即 $a^{tk}=e$。

   已知 $ord(a)=st$，由阶的整除性可知 $st\mid tk$。

   约去 $t$ 得 $s\mid k$。

结论：

由 $k\mid s$ 且 $s\mid k$，且 $s,k$ 均为正整数，得 $k=s$。即 $ord(a^t)=s$。

子群 (Subgroup) 的判定

如果 $G$ 的一个非空子集 $H$ 也是一个群，则称 $H$ 为 $G$ 的子群。

快速判定定理（考试常用）：

只需要证明对任意 $a,b\in H$，有 $a\cdot b^{-1}\in H$（乘法形式）或 $a-b\in H$（加法形式）。

原因：如果对于任意 $a,b\in H$，都有 $a{b}^{-1}\in H$，那么：

1. 找单位元： 取 $a=b$，则 $a{a}^{-1}=e\in H$。（单位元到手）
2. 找逆元： 已知 $e\in H$，取 $a=e$，则 $e{b}^{-1}=b^{-1}\in H$。（逆元到手）
3. 找封闭性： 已知 $b\in H⟹b^{-1}\in H$，那么对于 $a$ 和 $b^{-1}$，根据公式有 $a(b^{-1}{)}^{-1}=ab\in H$。（封闭性到手）
4. 结合律：H 的结合性继承自 G。

5.2 循环群

1. 什么是循环群？

如果一个群 $G$ 中的每一个元素都可以表示成某一个固定元素 $a$ 的整数次幂（或倍数），那么 $G$ 就叫循环群，元素 $a$ 称为群的生成元（Generator）。

• 记号： $G=⟨a⟩=\{a^n\mid n\in \mathbb{Z}\}$
• 例子： 整数加法群 $(\mathbb{Z},+)$ 的生成元是 $1$ 或 $-1$。
• 如果一个模 $m$ 的乘法群是循环群，我们就说模 $m$ 有原根。
  • 这要求 m 为 $2,4,p^k,2p^k$ （其中 $p$ 是奇素数，$k\ge 1$）
  • 注意：循环群的子群也是循环群，见 子群的性质

2. 循环群的分类

考试常考两类循环群：

1. 无限循环群： 一定与整数加法群 $(\mathbb{Z},+)$ 同构（结构完全一样）。
2. $n$ 阶有限循环群： 一定与模 $n$ 加法群 $({\mathbb{Z}}_n,+)$ 同构。

3. 生成元与阶（必考计算点）

在一个 $n$ 阶循环群 $G=⟨a⟩$ 中：

• 如何判断生成元？
  • 前提： 先确定群的阶 $n$，并找到一个已知的生成元 $g$。
  • 表达： 将群中任何元素 $x$ 写成 $g^k$ 的形式。
  • 判定： $x=g^k$ 是生成元 $⟺\gcd (k,n)=1$。
• 生成元的个数： 等于 $\phi (n)$（欧拉函数值）。
• 元素的阶： 元素 $a^k$ 的阶计算公式为：$\text{ord}(a^k)=\frac{n}{\gcd (k,n)}$

[!练习] 快速练习： 在 $8$ 阶群 ${\mathbb{Z}}_8$ 中，生成元有哪些？

答：与 $8$ 互素的数有 $1,3,5,7$。所以生成元有 $4$ 个，分别是 $1,3,5,7$。

4. 子群的性质（定理 5.2.1）

这是判断题和填空题的常客：

• 子群必循环： 循环群的任何子群也一定是循环群。
• 子群的阶： 有限循环群的子群的阶一定是原群阶 $n$ 的因子。
• 子群的唯一性： 对于 $n$ 阶循环群的每一个正因子 $d$，有且仅有一个 $d$ 阶子群。
• 拉格朗日定理：对于有限群 $G$ 中的任意元素 $g$，有 $g^{|G|}=e$（单位元）。

5. 群同构（Isomorphism）

定义 5.2.4 是理解群结构的关键：

• 定义： 如果两个群 $(G,\cdot )$ 和 $(G^{\prime },\circ )$ 之间存在一个一一映射 $f$，满足 $f(a\cdot b)=f(a)\circ f(b)$，则称它们同构，记作 $G\cong G^{\prime }$。
• 直白理解： 同构意味着两个群除了元素的“名字”不同，其运算规则和内部结构完全一模一样。

子群及生成元

题目：求 ${\mathbb{Z}}_{11}^{\ast }$ 的所有子群及其生成元

第一步：分析群的结构（确定环境）

1. 确定元素： ${\mathbb{Z}}_{11}^{\ast }=\{1,2,3,4,5,6,7,8,9,10\}$。
2. 确定群阶： 因为 $11$ 是素数，群阶 $n=\varphi (11)=11-1=10$。
3. 确定性质： 如果一个模 $m$ 的乘法群是循环群，我们就说模 $m$ 有原根，这要求 m 为 $2,4,p^k,2p^k$

第二步：寻找一个“原根”作为基准（找到首领）

我们需要找到一个阶为 $10$ 的元素 $g$。

• 试算 $2$（也可参考判定 a 是否是模 m 的原根）：
  • $\phi (m)=11-1=10$，其因子为 2 和 5。
  • $2^{10/2}=32\equiv 10\not\equiv 1(\mathrm{mod}11)$
  • $2^{10/5}=4\not\equiv 1$
  • 因此 2 是模 10 的原根。
• 基准生成元： $g=2$。

第三步：确定所有子群的阶（根据拉格朗日定理）

循环群的子群与群阶 $n=10$ 的因子一一对应。

$10$ 的正因子有：$1,2,5,10$。这意味着共有 $4$ 个子群。

第四步：推导各子群及其生成元（核心步骤）

利用公式：若 $g$ 是 $n$ 阶群生成元，则阶为 $d$ 的子群由 $g^{n/d}$ 生成。

1. 阶 $d=1$ 的子群
   • 代表生成元： $2^{10/1}=2^{10}\equiv 1(\mathrm{mod}11)$
   • 子群： $H_1=\{1\}$
   • 所有生成元： $\{1\}$ （$\varphi (1)=1$个）
2. 阶 $d=2$ 的子群
   • 代表生成元： $2^{10/2}=2^5=32\equiv 10(\mathrm{mod}11)$
   • 子群： $H_2=\{1,10\}$
   • 所有生成元： $\{10\}$ （$\varphi (2)=1$个）
3. 阶 $d=5$ 的子群
   • 代表生成元： $2^{10/5}=2^2=4(\mathrm{mod}11)$
   • 子群元素： $\{4^1,4^2,4^3,4^4,4^5\}(\mathrm{mod}11)=\{4,5,9,3,1\}$
   • 所有生成元： 从 $a=4$ 出发，找 $a^k$ 满足 $\gcd (k,5)=1$： $4^1=4,4^2=5,4^3=9,4^4=3$。 故生成元为：$\{3,4,5,9\}$ （$\varphi (5)=4$个）
4. 阶 $d=10$ 的子群（原群本身）
   • 代表生成元： $2^{10/10}=2^1=2(\mathrm{mod}11)$
   • 子群元素： $\{1,2,3,4,5,6,7,8,9,10\}$
   • 所有生成元（原根）： 从 $g=2$ 出发，找 $2^k$ 满足 $\gcd (k,10)=1$： $k\in \{1,3,7,9\}$ $⟹$ $2^1=2,2^3=8,2^7=7,2^9=6$。 故生成元为：$\{2,6,7,8\}$ （$\varphi (10)=4$个）

总结笔记：反推此类题的“万能公式”

若要找 ${\mathbb{Z}}_p^{\ast }$ 的所有子群：

1. 列因子： 找出 $n=p-1$ 的所有因子 $d_i$。
2. 找原根： 找一个 $g$ 使得 $g^{n/q}\not\equiv 1(\mathrm{mod}p)$（$q$ 是 $n$ 的所有质因子）。
3. 定代表： 每个阶为 $d$ 的子群，其代表生成元是 $a=g^{n/d}$。
4. 求所有： 该子群的所有生成元集合为 $\{a^k\mid 1\le k<d,\gcd (k,d)=1\}$。

检查技巧：

所有子群生成元的个数之和应该等于群阶。

$\varphi (1)+\varphi (2)+\varphi (5)+\varphi (10)=1+1+4+4=10$。

如果你的生成元总数加起来不是 $10$，说明有遗漏或重复。

解：${\mathbb{Z}}_{12}$ 的所有子群及其生成元

已知 ${\mathbb{Z}}_{12}=\{0,1,2,3,4,5,6,7,8,9,10,11\}$ 是一个 12 阶循环群。

根据循环群的性质，${\mathbb{Z}}_{12}$ 的每个子群也是循环群，且子群的阶必定是 12 的正因子。

12 的所有正因子为：1, 2, 3, 4, 6, 12。因此，${\mathbb{Z}}_{12}$ 共有 6 个子群。

下表列出各子群的阶、元素集合及所有可能的生成元：

子群的阶 (d)	子群的标准表示法 ⟨k⟩	子群的元素集合	所有生成元
1	$⟨0⟩$	$\{0\}$	$\{0\}$
2	$⟨6⟩$	$\{0,6\}$	$\{6\}$
3	$⟨4⟩$	$\{0,4,8\}$	$\{4,8\}$
4	$⟨3⟩$	$\{0,3,6,9\}$	$\{3,9\}$
6	$⟨2⟩$	$\{0,2,4,6,8,10\}$	$\{2,10\}$
12	$⟨1⟩$	$\{0,1,2,\dots ,11\}$	$\{1,5,7,11\}$

考点要点总结（帮助理解）：

1. 子群的存在性： 对于 $n$ 阶循环群的每一个正因子 $d$，恰好存在一个 $d$ 阶子群。
2. 如何找到子群： 若 $d$ 是 $n$ 的因子，则 $k=n/d$ 生成的子群 $⟨k⟩$ 阶数为 $d$。
3. 如何找到所有生成元： 对于子群 $H=⟨k⟩$，其阶数为 $d$，则元素 $m\cdot k$ 是 $H$ 的生成元的充分必要条件是 $\gcd (m,d)=1$。
   • 例如：6 阶子群 $⟨2⟩$，其生成元为 $1\cdot 2=2$ 和 $5\cdot 2=10$（因为 1, 5 与 6 互质）。

5.3 陪集和 Lagrange 定理

1. 陪集 (Coset) 的定义

设 $H$ 是群 $G$ 的子群，对于 $G$ 中的任意元素 $g$：

• 左陪集 (Left Coset)： $gH=\{g\cdot h\mid h\in H\}$。
• 右陪集 (Right Coset)： $Hg=\{h\cdot g\mid h\in H\}$。
• 性质： * $g$ 称为该陪集的陪集代表元。
  • 当 $G$ 是 Abel 群（交换群）时，左陪集等于右陪集，$gH=Hg$。

2. 陪集的重要性质 (定理 5.3.1)

• 等价性： 两个左陪集 $aH=bH$ 的充要条件是 $a^{-1}b\in H$。
• 不相交性： 两个左陪集要么完全相等，要么交集为空（$aH\cap bH=\varnothing$）。
• 分类功能： 陪集构成了群 $G$ 的一种分类，每一个元素属于且仅属于一个陪集。

3. Lagrange（拉格朗日）定理 (定理 5.3.2)

这是群论中最著名的定理之一，揭示了子群与大群规模之间的整除关系：

• 指数 (Index)： 子群 $H$ 在 $G$ 中不同陪集的个数称为 $H$ 在 $G$ 中的指数，记为 $[G:H]$。
• 定理内容： 若 $G$ 是有限群，$H$ 是其子群，则： $|G|=|H|\cdot [G:H]$ 即：群的阶 = 子群的阶 × 子群的指数。

4. 三大重要推论

基于 Lagrange 定理，可以得出以下直接结论：

• 推论 1： 子群的阶 $|H|$ 必然整除大群的阶 $|G|$。
• 推论 2： 群中任意元素 $g$ 的阶 $ord(g)$ 必然整除群的阶 $|G|$。
• 推论 3： 对于有限群 $G$ 中的任意元素 $g$，有 $g^{|G|}=e$（单位元）。

5. 补充重要定理 (定理 5.3.3)

• 素数阶群必循环： 如果一个群的阶 $p$ 是个素数，那么这个群一定是循环群，且除了单位元外，群里的任何元素都是生成元。
  • 原因： 元素的阶必须整除素数 $p$，所以阶只能是 $1$ 或 $p$。

[!题目] 题目： 在 8 阶群 $({\mathbb{Z}}_8,+)$ 中，已知子群 $H=\{0,2,4,6\}$，求它的陪集。

1. 子群的阶： $|H|=4$。
2. 计算指数： $[G:H]=|G|/|H|=8/4=2$。说明一共有 2 个不同的陪集。
3. 寻找陪集：

• 第一个陪集就是 $H$ 本身：$0+H=\{0,2,4,6\}$。
• 选一个不在 $H$ 中的元素（如 1）：$1+H=\{1,3,5,7\}$。
• 这两个陪集正好填满了整个 ${\mathbb{Z}}_8$。

5.4 正规子群和商群

这部分内容是群论中比较抽象的进阶部分，但核心逻辑其实是：利用一种特殊的子群（正规子群）把大群“切块”（商群），并通过一种保持结构的映射（同态）来研究不同群之间的关系。

1. 正规子群 (Normal Subgroup)

并不是所有的子群都能用来做“除法”，只有正规子群可以。

• 定义： 若子群 $H$ 满足对任意 $a\in G$，左陪集等于右陪集（即 $aH=Ha$），则称 $H$ 为 $G$ 的正规子群，记作 $H◃G$。
• 等价判定： 对任意 $a\in G$ 且 $h\in H$，有 $ah{a}^{-1}\in H$。
• 两个结论：
  1. 单位元子群 $\{e\}$ 和 $G$ 本身永远是正规子群。
  2. Abel 群（交换群）的所有子群都是正规子群。

2. 商群 (Quotient Group)

当你用正规子群 $H$ 对群 $G$ 进行陪集分解后，这些陪集本身也能构成一个群。

• 记号： $G/H$。
• 元素： 所有的陪集 $\{aH\mid a\in G\}$。
• 运算： 陪集与陪集的乘法定义为 $(aH)\cdot (bH)=(ab)H$。
• 直观理解： 商群相当于把 $H$ 里的所有元素都“看作单位元”，从而简化了原群的结构。

3. 群同态 (Group Homomorphism)

研究两个群 $G$ 到 $G^{\prime }$ 之间的某种“连接”。

• 定义： 若映射 $f:G\to G^{\prime }$ 满足 $f(a\cdot b)=f(a)\circ f(b)$，则称 $f$ 为同态。
• 核 (Kernel)： $\ker (f)=\{a\in G\mid f(a)=e^{\prime }\}$。即 $G$ 中所有映射到对方单位元的元素集合。
• 像 (Image)： $\text{Im}(f)=\{f(a)\mid a\in G\}$。
• 重要性质：
  1. 核 $\ker (f)$ 永远是 $G$ 的正规子群。
  2. $f$ 是单射（单同态）的充要条件是 $\ker (f)=\{e\}$。

4. 群同态基本定理

这是这几页图片中最核心的结论（定理 5.4.4）：

• 内容： 设 $f:G\to G^{\prime }$ 是一个满同态，则：$G/\ker (f)\cong G^{\prime }$
• 直白解释： 一个群 $G$ 的同态像，本质上就是 $G$ 对该同态核做的商群。
• 意义： 我们可以通过研究商群来研究所有可能的同态映射。

6. 环和域

6.1 环和域的基本概念

环的基础定义

环是定义了加法和乘法两种运算的集合。

1. 核心定义

一个集合 $R$ 要被称为“环”，必须满足：

• 加法是阿贝尔群（交换群）： 满足结合律、交换律、有单位元（零元 $0$）、有逆元（负元素 $-a$）。
• 乘法是半群： 满足封闭律、结合律即可（不一定有交换律，也不一定有单位元 $1$）。
• 分配律： 乘法对加法满足 $a(b+c)=ab+ac$。

2. 特殊的环（常考概念）

• 交换环： 乘法满足交换律 ($ab=ba$)。
• 含单位元的环： 存在乘法单位元 $1$，使得 $1\cdot a=a\cdot 1=a$。
• 整环（Integral Domain）： 这是一个极其重要的概念。它是指：含单位元的交换环，且没有零因子。
  • 零因子： 若 $a\ne 0,b\ne 0$ 但 $ab=0$，则称 $a,b$ 为零因子。整环里不允许这种情况发生（例如整数集 $\mathbb{Z}$ 是整环）。

除环与域（Field）

域是结构最严谨的环，你可以把它类比为实数集 $\mathbb{R}$。

• 除环（Division Ring）： 每一个非零元素都有乘法逆元（即可以做除法）的环。
• 域（Field）： 交换的除环。
  • 定义： 加法成阿贝尔群，非零元乘法也成阿贝尔群，且满足分配律。
  • 例子： 有理数域 $\mathbb{Q}$、实数域 $\mathbb{R}$、复数域 $\mathbb{C}$。

考试必考结论：包含关系

域 $\subset$ 除环 $\subset$ 整环 $\subset$ 含单位元的交换环 $\subset$ 环

重要定理 6.1.1： 每一个有限整环必定是一个域。

环的特征（Characteristic）

这是网络安全（尤其是对称加密、AES算法等）中非常关键的概念。

• 定义： 在环 $R$ 中，如果存在最小的正整数 $n$ 使得 $n\cdot 1=0$（即 $n$ 个单位元相加等于零元），则称该环的特征为 $n$，记作 $\text{char}(R)=n$。如果不存在这样的 $n$，则特征为 $0$。
• 核心性质：
  1. 整环（或域）的特征要么是 $0$，要么是一个素数 $p$。
  2. 对于有限域，其特征必为素数 $p$。

6.2 理想与商环

理想是环的一个特殊子集，你可以把它类比为整数里的“倍数集合”。

核心定义

• 理想 (Ideal)： 环 $R$ 的一个子环 $I$，如果满足：对于任意 $a\in I$ 和环中任意元素 $r\in R$，都有 $ar\in I$ 且 $ra\in I$。
  • 直观理解： 理想具有“吸收性”。环里的任何元素乘以理想里的元素，结果依然在理想里。
• 平凡理想： 任何环 $R$ 都有两个默认理想：零理想 $\{0\}$ 和它本身 $R$。
• 主理想 (Principal Ideal)： 由环中单个元素 $a$ 生成的理想，记作 $(a)$。
  • 例如：在整数环 $\mathbb{Z}$ 中，所有 3 的倍数组成的集合 $(3)=\{...,-3,0,3,6,...\}$ 就是一个主理想。
• 主理想环： 如果一个环里的所有理想都是主理想，就叫主理想环（如整数环 $\mathbb{Z}$）。

商环 (Quotient Ring) 与特殊理想

这是构造“模运算”数学对象的通用方法。

1. 商环 $R/I$

通过理想 $I$ 可以将环 $R$ 分割成不相交的陪集 $[a]=a+I$。这些陪集组成的集合 $R/I$ 在特定的加法和乘法下也构成一个环，称为商环。

• 经典例子： $\mathbb{Z}/(n)$ 就是我们常说的模 $n$ 剩余类环 ${\mathbb{Z}}_n$。

2. 素理想与极大理想（高频考点 🚨）

商环的“性质”取决于理想 $I$ 的“级别”：

• 素理想 (Prime Ideal)： 若 $ab\in P⟹a\in P$ 或 $b\in P$。
• 极大理想 (Maximal Ideal)： 没有比它更大的理想（除了 $R$ 本身）。

定理 6.2.2（考试必背关系）：

• $R/I$ 是整环 $⟺$ $I$ 是素理想。
• $R/I$ 是域 $⟺$ $I$ 是极大理想。

结论： 每一个极大理想都是素理想。在 $\mathbb{Z}$ 中，当 $p$ 为素数时，$(p)$ 既是素理想也是极大理想，所以 $\mathbb{Z}/(p)$ 是一个域。

环同态 (Ring Homomorphism)

同态描述了两个环之间“保持运算结构”的映射。

1. 定义

映射 $f:R\to R^{\prime }$ 满足：

1. $f(a+b)=f(a)+f(b)$
2. $f(ab)=f(a)f(b)$

2. 同态基本定理 (Fundamental Theorem)

这是代数学的灵魂定理：

• 同态核 (Kernel)： $\text{ker}(f)=\{r\in R\mid f(r)=0\}$。注意：同态核一定是一个理想。
• 定理内容： 环 $R$ 模去同态核后的商环，同构于它的同态像，即 $R/\text{ker}(f)\cong f(R)$。

6.3 多项式环

一、 基本概念：多项式环 $R[x]$

1. 定义：设 $R$ 是一个环，由 $R$ 中元素作为系数的 $x$ 的多项式全体构成的环称为 $R$ 上的多项式环，记为 $R[x]$。
2. 次数 (Degree)：多项式 $f(x)=a_n{x}^n+\cdots +a_0$ 中最高次项的幂次 $n$ 称为次数，记为 $\text{deg}(f)$。
   • 首项系数：最高次项的系数 $a_n$。如果 $a_n=1$，称该多项式为首一多项式。
   • 零多项式：约定 $\text{deg}(0)=-\infty$。
3. 运算规则与次数关系：
   • $\text{deg}(f+g)\le \max \{\text{deg}(f),\text{deg}(g)\}$
   • $\text{deg}(fg)\le \text{deg}(f)+\text{deg}(g)$
   • 重要结论：若 $R$ 是整环（无零因子），则 $\text{deg}(fg)=\text{deg}(f)+\text{deg}(g)$，且 $R[x]$ 也是整环。

二、 带余除法与整除性

1. 带余除法（核心算法）

• 定理：在域 $F$ 上，对于 $f(x)$ 和 $g(x)\ne 0$，一定存在唯一的 $q(x)$（商）和 $r(x)$（余式），使得：$f(x)=q(x)g(x)+r(x)\text{，且 }\text{deg}(r)<\text{deg}(g)$
• 应用：手工长除法（注意在模 $p$ 域下，系数运算要模 $p$）。

2. 整除与不可约性

• 整除：若 $r(x)=0$，则称 $g(x)$ 整除 $f(x)$，记为 $g(x)\mid f(x)$。
• 不可约多项式（类比素数）：如果一个次数 $\ge 1$ 的多项式不能分解为两个次数更低的多项式之积，称其为不可约多项式。
  • 判别法：对于次数为 2 或 3 的多项式，如果不存根（即代入域内任何元素都不等于 0），则它一定不可约。

三、 根与因式

1. 余式定理：$f(x)$ 除以 $(x-a)$ 的余数等于 $f(a)$。
2. 根与因式的关系：$a$ 是 $f(x)$ 的根 $⟺(x-a)\mid f(x)$。
3. 重根判别：
   • $a$ 是 $f(x)$ 的重根 $⟺f(a)=0$ 且导数 $f^{\prime }(a)=0$。
   • 若 $\text{gcd}(f,f^{\prime })=1$，则 $f(x)$ 没有重根。

四、 最大公因式 (GCD) 与 辗转相除法

1. 定义：$\text{gcd}(f,g)=d(x)$ 是能同时整除两者的最高次首一多项式。
2. 裴蜀等式：一定存在 $s(x),t(x)$ 满足：$s(x)f(x)+t(x)g(x)=\text{gcd}(f,g)$ 这个在网络安全（如求逆元）中极其重要！
3. 求法：通过辗转相除法（Euclid 算法）不断求余直到余数为 0。

五、 商环与有限域的构造（考试大题高发点）

1. 构造：设 $p(x)$ 是域 $F$ 上的 $n$ 次不可约多项式，则商环 $F[x]/(p(x))$ 是一个域。
2. 元素个数：若 $F$ 是 $Z_p$（模 $p$ 的域），则该有限域包含 $p^n$ 个元素。
3. 元素形式：所有次数小于 $n$ 的多项式。
4. 运算规则：
   • 加法：系数对应相加（记得模 $p$）。
   • 乘法：多项式相乘后，必须模 $p(x)$ 取余数。

7. 有限域

7.1 域的有限扩张

1. 基础概念：什么是“域”的扩张？

想象你在做一个数学题，如果只有整数不够用，你会引入分数（变成有理数域 $\mathbb{Q}$）；如果 $\mathbb{Q}$ 还不满足 $x^2-2=0$，你会引入 $\sqrt{2}$（变成扩张域）。

• 域扩张（Field Extension）：如果域 $K$ 是域 $F$ 的子集，则称 $F$ 是 $K$ 的扩张域。
• 素域（Prime Field）：没有真子域的域。
  • 特征为 $p$ 的域，其素域同构于 $F_p$（即 ${\mathbb{Z}}_p$）。
  • 特征为 $0$ 的域（如实数域），其素域同构于 $\mathbb{Q}$。
• 扩张次数：记作 $(F:K)$，即把 $F$ 看作 $K$ 上的向量空间时的维数。
  • 乘法原理（定理 7.1.3）：如果有嵌套关系 $K\subseteq E\subseteq F$，那么总扩张次数是分步扩张次数的乘积：$(F:K)=(F:E)(E:K)$

2. 代数元与极小多项式（重点！）

这是构造大域的关键。

• 代数元：如果 $\alpha$ 是某个以 $K$ 中元素为系数的多项式 $f(x)$ 的根，那 $\alpha$ 就是 $K$ 上的代数元。
• 极小多项式 $m_{\alpha }(x)$：满足以 $\alpha$ 为根的、次数最低的、首项系数为 1 的不可约多项式。
  • 性质：任何以 $\alpha$ 为根的多项式，都能被极小多项式整除。

3. 单代数扩张 $K(\alpha )$ 的结构

这是考试最常考的计算背景。如果你往域 $K$ 里加入一个根 $\alpha$，新形成的域 $K(\alpha )$ 是什么样的？

• 同构关系：$K(\alpha )\cong K[x]/(m_{\alpha }(x))$。
  • 直白解释：在新域里的计算，本质上就是对极小多项式取模。
• 基底：如果 $\alpha$ 的极小多项式是 $n$ 次的，那么 $K(\alpha )$ 的一组基是 $\{1,\alpha ,{\alpha }^2,\dots ,{\alpha }^{n-1}\}$。
  • 这意味着：$K(\alpha )$ 中的任何元素都可以写成 $c_0+c_1\alpha +\cdots +c_{n-1}{\alpha }^{n-1}$ 的形式。

4. 分裂域（Splitting Field）

• 定义：对于多项式 $f(x)$，如果一个扩张域 $E$ 刚好能让 $f(x)$ 分解成一堆一次因子（即所有的根都在 $E$ 里），且 $E$ 是最小的这样的域，就叫分裂域。
• 意义：分裂域保证了多项式的根“有家可归”。

5. 有限域的性质（考试必考点！）

这是第 7.2 节的开头，也是网络安全最直接用到的部分：

• 阶数（元素个数）：有限域 $F$ 的元素个数一定是 $p^n$ 个，其中 $p$ 是素数（域的特征），$n$ 是扩张次数。
  • 结论：不存在元素个数为 6 或 10 的有限域（因为它们不是素数的幂）。
• 形式：所有的有限域元素都可以表示为基底的线性组合：$a=c_1{\alpha }_1+c_2{\alpha }_2+\cdots +c_n{\alpha }_n(c_i\in F_p)$

7.2 有限域(Galois 域)的性质

这部分内容进入了有限域（Galois Field，记作 $GF(p^n)$ 或 $F_q$）的核心性质。在网络安全中，这些性质直接决定了加密算法（如椭圆曲线 ECC）的数学基础。

1. 有限域的阶数与特征

• 元素个数：一个有限域 $F$ 的元素个数（阶）必然是某个素数 $p$ 的幂，即 $|F|=p^n$。其中 $p$ 称为域的特征，$n$ 是 $F$ 在其素域上的扩张次数。
• 元素形式：若 $F$ 阶数为 $p^n$，则其中的元素可以表示为 $c_1{\alpha }_1+c_2{\alpha }_2+\cdots +c_n{\alpha }_n$，其中系数 $c_i\in F_p$。

2. 有限域的存在性与唯一性

• 费马小定理的推广：对于 $q$ 阶有限域 $F_q$ 中的任意元素 $a$，都满足 $a^q=a$。
• 多项式根的关系：$F_q$ 中的 $q$ 个元素恰好是多项式 $x^q-x$ 在素域 $F_p$ 上的所有根。
• 唯一性：给定阶数 $q=p^n$，在同构的意义下，有且仅有一个 $q$ 阶有限域。

3. 有限域的子域结构（常考点！）

有限域并不是随意扩张的，它的子域有严格的约束：

• 子域阶数判定：$q=p^n$ 阶有限域 $F_q$ 的子域，其阶数必然形式为 $p^m$，其中 $m$ 必须是 $n$ 的因子。
• 存在性：只要 $m$ 是 $n$ 的正因子，$F_{p^n}$ 中就一定存在唯一的 $p^m$ 阶子域。
• 例子：$F_{2^{10}}$ 的子域阶数可以是 $2^1,2^2,2^5$，因为 1, 2, 5 是 10 的因子。

4. 有限域的乘法群与本原元（网络安全核心）

这是离散对数问题的基础：

• 循环群性质：有限域 $F_q$ 的所有非零元素构成的乘法群 $F_q^{\ast }$ 是一个循环群。
• 本原元（Primitive Element）：乘法群 $F_q^{\ast }$ 的生成元称为该域的本原元。
  • 这意味着：域中任何非零元素都可以写成项本原元 $a$ 的幂次 $a^k$。
  • 本原元的个数为 $\varphi (q-1)$。
• 离散对数问题：已知 $b=a^n$（$a$ 为本原元），求 $n$ 是一个数学难题。这正是目前许多非对称加密体制的安全根基。

7.3 有限域的表示

1. 有限域的表示法（两种主流方式）

为了在计算机或纸面上处理有限域 $F_{p^n}$，我们需要具体的表示方式：

• 多项式表示法（便于加法）
  • 将域元素看作次数小于 $n$ 的多项式：$f(x)=a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$，其中系数 $a_i\in F_p$。
  • 加法：对应系数相加（模 $p$）。
  • 乘法：普通多项式相乘后，必须模掉一个 $n$ 次不可约多项式。
• 幂表示法（便于乘法）
  • 利用本原元 $\xi$。由于乘法群是循环群，非零元素都可以表示为 $\{1,\xi ,{\xi }^2,\dots ,{\xi }^{q-2}\}$。
  • 乘法：指数直接相加 ${\xi }^i\cdot {\xi }^j={\xi }^{i+j}$（指数模 $q-1$）。
  • 加法：非常困难，通常需要通过查表转换回多项式表示法。

2. 具体构造实例：以 $F_{16}$ ($GF(2^4)$) 为例

这是考试最常见的背景（AES算法的基础）：

1. 选择不可约多项式：设 $f(x)=x^4+x+1$ 在 $F_2$ 上不可约。
2. 定义根：设 $\alpha$ 是 $f(x)$ 的一个根，则有关系式 ${\alpha }^4+\alpha +1=0$，即 ${\alpha }^4=\alpha +1$。
3. 生成元素：通过不断乘以 $\alpha$ 并利用上述关系式降次，可以得到所有元素：
   • ${\alpha }^4=\alpha +1$
   • ${\alpha }^5=\alpha (\alpha +1)={\alpha }^2+\alpha$
   • ${\alpha }^{15}=1$（回归单位元）

3. 寻找本原元：Gauss 算法

如果你拿到的元素 $\alpha$ 不是本原元（即它的阶小于 $q-1$），需要用 Gauss 算法调整：

• 核心思想：通过寻找不同阶的元素，利用最小公倍数性质构造出一个阶正好等于 $q-1$ 的元素。
• 步骤简述：
  1. 随机取一个非零元 $a_i$，计算其阶 $k_i$。
  2. 若 $k_i=q-1$，则找到本原元；否则取另一个不在其生成子群里的元素 $b$，计算阶 $h$。
  3. 利用 $k_i$ 和 $h$ 的质因子分解，组合出更高阶的元。

4. 离散对数问题（安全要点）

• 已知 $a$ 和 $b$，求 $n$ 使得 $b=a^n$。
• 在有限域上，当 $q$ 很大时，目前没有多项式时间的通用算法（虽然有“小步大步法”等，但依然很难）。这就是 Diffie-Hellman 和 ECC 安全性的数学保障。

7.4 有限域上的多项式

核心概念：极小多项式与本原多项式

1. 极小多项式 (Minimal Polynomial)

• 定义：设 $\alpha$ 是有限域 $F_{q^n}$ 中的一个元素，以 $\alpha$ 为根且次数最低的首一不可约多项式，称为 $\alpha$ 在 $F_q$ 上的极小多项式。
• 关键性质：
  • $\alpha$ 的所有“共轭元” $\alpha ,{\alpha }^q,{\alpha }^{q^2},\dots ,{\alpha }^{q^{d-1}}$ 具有相同的极小多项式。
  • 其次数 $d$ 是使 ${\alpha }^{q^d}=\alpha$ 成立的最小正整数。

2. 本原多项式 (Primitive Polynomial)

• 定义：如果一个 $n$ 次不可约多项式的根 $\alpha$ 是有限域 $F_{q^n}$ 的本原元（即能生成域内所有非零元的元素），那么这个多项式就叫本原多项式。
• 判定准则（定理 7.4.2）：
  • 多项式 $f(x)$ 的周期（阶） $d$ 等于 $q^n-1$。
• 数量（定理 7.4.3）：
  • $F_q[x]$ 中 $n$ 次本原多项式的个数为 $\frac{\varphi (q^n-1)}{n}$（其中 $\varphi$ 是欧拉函数）。

重点技巧：如何求极小多项式？

这是考题中最常见的计算题，图片中给出了两种主要方法。

方法一：共轭元乘积法（适用于次数较小）

根据定理 7.4.4，$\alpha$ 的极小多项式为：

$f(x)=(x-\alpha )(x-{\alpha }^q)(x-{\alpha }^{q^2})\dots (x-{\alpha }^{q^{d-1}})$

实例演示（参考图8例1）：

已知 $F_2$ 上本原多项式 $f(x)=x^4+x+1$ 的根为 $\alpha$。求 ${\alpha }^3$ 的极小多项式：

1. 找共轭元：计算 ${\alpha }^3$ 的 $q$ 次幂（这里 $q=2$）。
   • $({\alpha }^3{)}^1={\alpha }^3$
   • $({\alpha }^3{)}^2={\alpha }^6$
   • $({\alpha }^3{)}^4={\alpha }^{12}$
   • $({\alpha }^3{)}^8={\alpha }^{24}={\alpha }^9$ (因为 ${\alpha }^{15}=1$)
2. 写出乘积式：$g(x)=(x-{\alpha }^3)(x-{\alpha }^6)(x-{\alpha }^{12})(x-{\alpha }^9)$。
3. 展开化简：利用 ${\alpha }^4=\alpha +1$ 进行代换，最终得到 $g(x)=x^4+x^3+x^2+x+1$。

方法二：线性相关性法（矩阵法，推荐！）

当你不知道如何展开复杂的括号时，用这个方法。

1. 写出 $\alpha$ 的前几个幂次对应的向量表示。
2. 寻找这些向量之间的线性关系。

实例演示（参考图9例2）：

求 $\beta$ 的极小多项式，已知 ${\beta }^0,{\beta }^1,{\beta }^2$ 的向量表示。

1. 列出矩阵。
2. 通过初等行变换简化。
3. 若发现 ${\beta }^2+2\beta +3=0$，则极小多项式就是 $x^2+2x+3$。