《密码技术与物联网安全：mbedtls开发实战》 —3.4　群

3.4　群

3.4.1　群的基本概念

群是密码学中非常重要的概念。群是一个定义了二元运算的集合，使集合上的两个元素运算得到第3个元素。这些运算方法需要遵守特定的规则。

定义3-4

群指的是一个元素集合G以及联合G内两个元素的操作·的集合，如果一个群的元素是有限的，则称该群为有限群；群中元素的个数称为群的阶，表示为|G|；如果群的元素是无限的，则称该群为无限群。

群具有以下属性。

封闭性：如果a和b属于G，则a·b也属于G。

结合律：即对G中任意元素a、b、c，都有a·(b·c)=(a·b)·c 成立。

单位元：G中存在一个元素e，对于G中任意元素a，都有a·e=e·a=a成立。

逆元：对于G中任意元素a，G中都存在一个元素a，使得a·a=a·a=e成立。

交换性：对于G中任意的元素a、b，都有a·b=b·a成立，则称G为阿贝尔群。

例3-5

构造一个集合Z*?m，该集合由i={0,1,…,m-1}组成，且集合中的元素满足gcd(i,m)=1。例如当m=9时，Z*?m={1,2,4,5,7,8}。在Z*?9中定义一个群操作a·b mod 9，把群操作结果记录至

表3-6中。

表3-6　Z*?9群操作a·b mod 9计算结果

通过观察表3-6可以获得以下结论。

封闭性：a和b均属于集合Z*?9，而a·b mod 9的结果也属于集合Z*?9，例如当a=4，b=8时，a·b mod 9的计算结果为5，a=4，b=8和群操作结果5均属于集合Z*?9。

结合性：a、b、c均属于集合Z*?9，则a·(b·c)=(a·b)·c，例如当a=2，b=4，c=5时， 2·(4·5)=(2·4)·5≡40≡4 mod 9。

单位元：Z*?9中存在元素e，使得a·e=e·a=a，单位元e=1。

逆元：对于集合Z*?9中的每一个元素，都存在一个逆元。例如2关于模9的逆元为5，7关于模9的逆元为4。

交换性：a·b mod 9和b·a mod 9的结果相同，例如当a=7，b=2时，a·b mod 9和b·a mod 9的计算结果均为5。由于符合交换性，所以Z*?9为阿贝尔群。