2026/6/20 · 抽象代数（区块链密码学向）

1 · 群（Group）

群是抽象代数最基本、也是密码学最核心的结构：一个可逆运算的体系。椭圆曲线、模运算、RSA 背后都是群。

群是抽象代数最基本、也是密码学最核心的结构。一句话：群就是一个「可逆运算的体系」。椭圆曲线、模运算、RSA 背后都是群。

一、定义

一个集合 $G$ 配上一种运算 $\cdot$ ，满足四条公理，就是群（Group）：

封闭性： $a,b\in G \Rightarrow a\cdot b\in G$ （算完还在集合里）。
结合律： $(a\cdot b)\cdot c = a\cdot(b\cdot c)$ 。
单位元：存在 $e$ 使 $a\cdot e = e\cdot a = a$ 。
逆元：每个 $a$ 都有 $a^{-1}$ 使 $a\cdot a^{-1} = e$ 。

若还满足交换律 $a\cdot b = b\cdot a$ ，叫阿贝尔群（交换群）。

直觉：「逆元」是灵魂——有逆元意味着任何操作都能「撤销」。这正是加密能解密、签名能验证的前提。

二、例子（从熟悉到密码学）

集合	运算	是群吗	单位元
整数 $\mathbb{Z}$	加法	是（阿贝尔）	0
整数 $\mathbb{Z}$	乘法	否（除 ±1 外无逆元）	1
非零有理数	乘法	是	1
$\mathbb{Z}_n$ （模 n）	加法	是	0
$\mathbb{Z}_p^*$ （非零元，p 质）	乘法模 p	是	1
椭圆曲线上的点	点加法	是	无穷远点 $\mathcal{O}$

最后两行是密码学的主角。

三、阶、子群与拉格朗日定理

群的阶 $|G|$ ：元素个数。
元素的阶 $\text{ord}(a)$ ：使 $a^k = e$ 的最小正整数 k。
子群： $G$ 的一个子集，自己也成群。

拉格朗日定理（Lagrange）：子群的阶整除群的阶。推论：任一元素的阶整除 $|G|$ 。这是分析密码学循环结构、选参数的基本工具。

四、循环群与生成元（重中之重）

如果群里存在一个元素 $g$ ，反复运算它能生成整个群，就叫循环群， $g$ 是生成元（generator）：

G = \langle g \rangle = \{e, g, g^2, g^3, \dots\}

密码学意义：整个公钥密码学都建在循环群上。公钥 = $g^x$ （或 $x\cdot P$ ），私钥是 x。从 g 和 $g^x$ 反推 x 就是离散对数问题（DLP），现有算法极难——这个「正向快反向难」就是安全性的来源。

五、数字例题（步步算）

在 $\mathbb{Z}_7^* = \{1,2,3,4,5,6\}$ （乘法模 7）中，验证 3 是生成元。

逐个算 3 的幂（模 7）： $3^1=3,\;3^2=2,\;3^3=6,\;3^4=4,\;3^5=5,\;3^6=1$ 。

刚好跑遍 $\{1,2,3,4,5,6\}$ 全部 6 个元素，所以 3 是生成元， $\text{ord}(3)=6=|\mathbb{Z}_7^*|$ 。而 2 呢？ $2^1=2,2^2=4,2^3=1$ ，只生成 $\{1,2,4\}$ ， $\text{ord}(2)=3$ ，不是生成元（且 3 整除 6，符合拉格朗日）。

六、Python 代码

def order(g, p):                 # 求 g 在 Z_p^* 中的阶
    x, k = g % p, 1
    while x != 1:
        x = (x * g) % p
        k += 1
    return k

p = 7
for g in range(1, p):
    print(f"g={g}, 阶={order(g, p)}, 生成元？{order(g,p)==p-1}")

# 离散对数（暴力）：已知 g、h，求 x 使 g^x = h (mod p)
def discrete_log(g, h, p):
    val = 1
    for x in range(p):
        if val == h:
            return x
        val = (val * g) % p

print("3^x = 5 (mod 7) 的 x =", discrete_log(3, 5, 7))   # 5

七、动手想一想

为什么「整数在乘法下不成群」？缺了哪条公理？
$|G|=10$ ，一个元素的阶可能是 3 吗？
为什么密码学偏爱「阶为大质数」的循环群？

答案：(1) 缺逆元，比如 2 没有整数乘法逆元。(2) 不可能，拉格朗日定理要求元素阶整除 10，3 不整除 10。(3) 阶为大质数时，除了平凡子群外没有小子群，避免了利用子群结构加速离散对数的攻击（如 Pohlig–Hellman）。

小结：群是「一个集合 + 一种可逆运算」。记住四条公理（封闭、结合、单位元、逆元）与「生成元 + 离散对数」这一对，就掌握了公钥密码学最底层的结构。