你已经完全掌握了群的四大公理(封闭性、结合律、单位元、逆元)。对于无限集合(比如整数在加法下)我们能判断它是不是群。但在计算机科学,特别是密码学中,我们更关心的是有限群 (Finite Groups)。
为什么?因为计算机的内存是有限的,无限大的数字会溢出。我们需要一种运算,让数字变大后能自动“绕回来”。作为程序员,你立刻会想到一个操作符:模运算 (Modulo, %)。
看看墙上的 12 小时制时钟。如果现在是 9 点,再过 4 个小时是几点?不是 13 点,而是 1 点。用代码写就是 (9 + 4) % 12 == 1。
为了符合程序员从 0 开始计数的习惯,我们把 12 点记作 0 点。于是我们的集合是 { 0, 1, 2, ..., 11 }。我们来检查一下它为什么是一个完美的群:
((a+b)%12 + c)%12 等于 (a + (b+c)%12)%12。0。加上 0 不会改变时间。(3 + 9) % 12 == 0。在这个群里,3 的逆元是 9,4 的逆元是 8。刚才的时钟系统有一个迷人的特性:如果你只是不断地 +1,你可以遍历整个集合里的每一个元素,最后回到 0。在群论中,我们把这种能由一个单一动作(或元素)不断重复生成整个群的结构,称为循环群 (Cyclic Group)。
那个能够生成整个群的元素(这里的 +1),叫做生成元 (Generator)。
密码学(比如 Diffie-Hellman 密钥交换机制)底层的核心原理之一,就是利用了某个巨大的质数模数下产生的循环群,以及它里面的生成元。
假设我们把模数改小一点,定义一个在模 5 (Modulo 5) 加法下的群。它的集合元素只有 { 0, 1, 2, 3, 4 }。
单位元依然是 0。操作是 (a + b) % 5。
请问,在这个群中,元素 3 的逆元是多少?