Learning 群论 (Group Theory) 基础与抽象思维 Course index

第四课:时钟与密码学基石

你已经完全掌握了群的四大公理(封闭性、结合律、单位元、逆元)。对于无限集合(比如整数在加法下)我们能判断它是不是群。但在计算机科学,特别是密码学中,我们更关心的是有限群 (Finite Groups)

为什么?因为计算机的内存是有限的,无限大的数字会溢出。我们需要一种运算,让数字变大后能自动“绕回来”。作为程序员,你立刻会想到一个操作符:模运算 (Modulo, %)

模运算天然是一个群

看看墙上的 12 小时制时钟。如果现在是 9 点,再过 4 个小时是几点?不是 13 点,而是 1 点。用代码写就是 (9 + 4) % 12 == 1

为了符合程序员从 0 开始计数的习惯,我们把 12 点记作 0 点。于是我们的集合是 { 0, 1, 2, ..., 11 }。我们来检查一下它为什么是一个完美的群:

当前数值 ( Modulo 12 )
0

循环群 (Cyclic Group)

刚才的时钟系统有一个迷人的特性:如果你只是不断地 +1,你可以遍历整个集合里的每一个元素,最后回到 0。在群论中,我们把这种能由一个单一动作(或元素)不断重复生成整个群的结构,称为循环群 (Cyclic Group)

那个能够生成整个群的元素(这里的 +1),叫做生成元 (Generator)

密码学(比如 Diffie-Hellman 密钥交换机制)底层的核心原理之一,就是利用了某个巨大的质数模数下产生的循环群,以及它里面的生成元。

小测试:密码学的微型沙盒

假设我们把模数改小一点,定义一个在模 5 (Modulo 5) 加法下的群。它的集合元素只有 { 0, 1, 2, 3, 4 }

单位元依然是 0。操作是 (a + b) % 5

请问,在这个群中,元素 3 的逆元是多少?

导师寄语:从正方形旋转到模运算,你已经跨越了群论最重要的抽象门槛!做完上面的测试,如果没问题,我们可以准备进入更核心的密码学乘法群了!