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

第五课:乘法群与质数

你极其敏锐,普通的加法群对你来说已经没有挑战了。现在,我们直接踏入现代密码学(如 RSA 算法、椭圆曲线)的真正基石:乘法群 (Multiplicative Groups)

如果我们把组合动作从“相加取模”变成“相乘取模”,会发生什么?

第一重挑战:单位元与开除 0

在乘法中,单位元不再是 0,而是 1(因为任何数乘 1 还是它自己)。

一旦单位元变成了 1,数字 0 就成了一个巨大的 bug:
根据群的逆元公理,每个元素都要能通过操作回到单位元 1。但是 0 * 任何数 = 0,它永远回不到 1!
群论的解决方案非常冷酷:把 0 开除出集合。

所以,我们的集合变成了从 1 开始:{ 1, 2, 3, 4, ... }

第二重挑战:为什么密码学必须用质数?

作为程序员,你肯定知道密码学和质数(素数)深度绑定。但你是否想过,从群论底层的角度来看,为什么必须是质数?

假设我们用一个合数(非质数)来建立乘法群,比如 模 6 (Modulo 6)。我们的集合排除了 0,剩下 { 1, 2, 3, 4, 5 }

让我们在这个集合里任选两个元素相乘:

2 * 3 = 6
6 % 6 = 0

砰!系统崩溃了。我们刚刚把 0 开除出了集合,结果 2 和 3 一相乘,居然又生成了 0!这产生了一个不在集合内的结果,无情地打破了群的第二大公理:封闭性 (Closure)

质数的魔法就在于此:
如果你使用的是质数 p(比如 5, 7, 或密码学中几百位的巨大质数),集合里任意两个比它小的数字相乘,永远不可能整除 p。它们相乘取模的结果,永远会完美地落在这个非零集合 { 1, 2, ..., p-1 } 的内部。封闭性保住了,每一个元素也都能找到自己的逆元!

核心顿悟测试

我们建立一个 模 7 乘法群,集合是 { 1, 2, 3, 4, 5, 6 }
单位元是 1。操作是 (a * b) % 7

请问:在这个群里,元素 3 的逆元(Inverse)是多少?
(提示:也就是找一个数字 x,使得 (3 * x) % 7 == 1

导师寄语:这就是为什么黑客和密码学家们对质数如此着迷。理解了这一点,你对公钥加密底层结构的理解已经超越了 90% 的普通程序员。去算出这个逆元吧!