3.数论与群论结合：整数模 n 乘法群

有限域与数论结合

代数结构研究一个特定对象的非空集合及其之前的操作。有限域 (finite field) 或者伽罗瓦域 (Galois Field). 有限域是定义在一类特定的对象上，满足加法、减法、乘法和除法运算的代数结构。而数论研究整数以及整数值函数。

有限域是一种数学对象，它既属于数论，也属于抽象代数的研究范畴。最常见的有限域是 Fp = (Zp,+,x) 整数模素数 p 有限域。Number theory 所研究的整数作为 algebraic structure 群中的 objects 组成集合，元素之间进行模算术运算。其代数操作包括基于范畴论衍生的群与群之间的同态映射操作，基于数论衍生的单个群内部的数之间的函数以及操作。

数论中的模算术（modular arithmetic）和有限域的循环群（cyclic group）具备相似的结构与规则。模运算的性质可以覆盖群环域所涉及的封闭性，结合律（加法性，乘法性），单位圆，逆元（模逆元），交换律，因此数论的模运算和群论的群环域结合，形成了最常见最有用的整数模素数 p 有限域 GF(p)。

有限域涉及抽象代数的知识主要有：

  1. 域的基本概念和性质，如交换环、整环、域、素域、同构、同态、自同构等。
  2. 域的扩张，\(F_p\) 扩张到 \(F_{p^n}\)。
  3. 域的应用，如伽罗瓦理论、可解性、根式解、基本定理、不可约多项式、有限域、循环域等。

有限域涉及数论的知识主要有域的算术，如欧几里得算法、辗转相除法、最大公因数、最小公倍数、互素、模运算、同余、欧拉函数、费马小定理、欧拉定理等。

有限域介绍

如果域 F 只包含有限个元素，则称其为有限域。有限域中元素的个数称为有限域的阶 (order)。尽管存在有无限个元素的无限域，但只有有限域在密码编码学中得到了广泛的应用。每个有限域的阶必为素数的幂（注：素数的幂不是素数），即有限域的阶可表示为 pⁿ（p 是素数、n 是正整数），该有限域通常称为 Galois 域 (Galois Fields)，记为 GF(pⁿ)。

当 n = 1 时，存在有限域 GF(p)，也称为素数域 (prime field),也写做 \(\mathbb{F}_p\)。在密码学中，最常用的域是阶为 p 的素数域 \(\mathbb{F}_p\)）或阶为 \(2^n\) 的 GF(2^n) 域。

整数模 n 乘法群

Multiplicative group of integers modulo n : the elements of this group can be thought of as the congruence classes, also known as residues modulo n, denoted by \((Z/nZ)^*\)（*表示正数，0 属于 N 集和 Z 集，但不属于 \(N^*\) 集）

整数模 n 乘法群是由模 n 的互质同余类组成的，0 没有逆元，所以不包含在整数模 n 乘法群中。整数模 n 乘法群的阶为 n。

  1. 从群论角度理解 n 为质数时，每个元素有逆元，模 n 整数才能构成群。

    模算术的剩余类 (Z/nZ, +) is \(C_n\) 可以组成一个 cyclic groups。

    对于 Z/nZ 来说，n 为质数时，根据欧拉函数，任意元素 \(a^{\varphi(n)} \equiv 1 \mod n\), 因此该元素通过拆分 \(\varphi(n)\) 就存在逆元，根据封闭性，它的不同幂次也是集合元素，也就生成了群，也就是生成元，所以 n 是素数时，n 与每个元素互质，则每个元素都是循环群的生成元。

    The class \([m]_n\) generates Z/nZ if and only if gcd(m, n) = 1

  2. 从数论角度理解：p 是素数，模 p 乘法构成群：

    如果 p 是合数，那么 $ ax p$ 的结果，即 \(ax-kp\) 的结果必为二者公因子的 gcd(a，p), 而二者公因子不是 1，所以其中任意不互质元素 a 不是乘法逆元。

    s = a*b, t = a*c, sx mode t, abx-kac=a(bx-kc) 为了让其最小 bx-kc=1, 如果 p 是质数，那么 \(gcd(a, p)=1\) , ax+py=1 可以求出逆元。

模 n 有限域

模 n 整数环 ⟨Zn,+,x⟩ 是交换环, 含幺环. 当 n 为素数时可以证明 Zn 构成域; 当 n 为合数时不构成整环和域.

n 不为素数，则只有与 n 互质的元素，才有逆元，不是所有的元素都有逆元，所以是（Zn,x) 只是具备交换律的幺半群，而不是交换群。而当 n 为素数，则 n 与每个元素互质，即每个元素存在逆元，（Zn,x) 便成了交换群，⟨Zn,+,x⟩ 便成了域，所以说：模 p 的有限域⟨Zp,+,x⟩，p 肯定是素数，否则就不是域了。

GF(p^n)

GF(p^n) 是 GF(p) 扩域而得，它不再是指单纯的数，而是从数扩展到多项式。一般而言, 所有有限域都形如 \(F_{p^n}\), 其中 p 是素数, n 是正整数. 该有限域有 \(p^n\) 个元素, 可以从 Fp 通过扩域得到。例如, 考虑域

\[\mathbb{F}_3[\sqrt{-1}]=\left\{a+b \sqrt{-1} \mid a, b \in \mathbb{F}_3\right\} \]

可以验证它在自然的加法、乘法下构成域. 它有 9 个元素, 因此这样就通过 \(F_3\) 的扩域得到了有限域 \(F_9\)

费马小定理/欧拉定律

费马小定理推论到群：若群 G 为 n 阶循环群，a 为 G 的生成元，则 a^n=e

群推论到费马小定理：模素数 p 单位群 \(Z^*_p\) 中 a 与 素数 p 互素， 欧拉函数 \(\varphi(p)=p-1\)，则 \(a^{\varphi(p)}=a^{p-1} \equiv 1 \mod p\)，所以推出费马小定理 \(a^{p-1} \equiv a \mod p\)

参考资料

  1. A visit to group theory and elementary number theory Zhen DING
  2. Number theory - Wikipedia
  3. Finite field - Wikipedia
  4. 【算法学习笔记】模运算总结 - RioTian - 博客园
  5. Prime Field -- from Wolfram MathWorld
  6. 有限域_百度百科