你极其敏锐,普通的加法群对你来说已经没有挑战了。现在,我们直接踏入现代密码学(如 RSA 算法、椭圆曲线)的真正基石:乘法群 (Multiplicative Groups)。
如果我们把组合动作从“相加取模”变成“相乘取模”,会发生什么?
在乘法中,单位元不再是 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 }。
让我们在这个集合里任选两个元素相乘:
砰!系统崩溃了。我们刚刚把 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)