从群论到快速幂和快速乘

发布于 / 笔记 / 3 条评论

在抽象代数中具有基本的重要地位。许多代数结构,包括环、域和向量空间都可以看作是在群的基础上添加新的运算和公理而形成的。群的概念在数学的很多分支都有出现,而且群论的研究方法也对抽象代数的其他分支有重要影响。

在数学中,群是由一个集合以及一个二元运算所组成的,符合以下四个性质(称为“群公理”)的代数结构。即封闭性结合律单位元逆元存在

对于(G,·),该群由一个集合G和一个二元运算·组成。对于该群,群公理表现为:

  1. 封闭性: 对于任意a, b ∈ G,有a · b ∈ G 。
  2. 结合律: 对于任意a, b, c ∈ G,有(a · b) · c = a · (b · c) 。
  3. 单位元: 存在e ∈ G,使得对于所有元素a ∈ G总有 e · a = a · e = a成立。
  4. 逆元存在: 对于任意a ∈ G,存在元素b使得总有a · b = b · a = e,此处e为单位元。

幺半群是一种类似群的结构。幺半群不一定满足逆元存在公理,但是其余的三个群公理均满足。即幺半群(G, *)满足{封闭性, 结合律, 单位元}。又因为幺半群的要求比群要少,所以所有的群都是幺半群。幺半群的例子:(非负整数,加法运算),(正整数,乘法运算)。

所以,这和标题里的快速幂和快速乘又有什么关系呢?

因为,快速幂算法就可以从幺半群的角度来分析。

对于幺半群<N*, *>(N*为非零自然数,*是乘法运算),计算a的k次幂,当k = 0时为1,其余情况为k个n相乘。根据结合律(强行),我们可以在至多O(log(k))的时间内把k拆成二进制下的1,然后使用至多O(log(k))次乘法合并这些幂次。

用代码会更清晰一些:

第一次接触的同学可能有点不明所以,但其实是一个比较清晰明了的过程的。在纸上稍微模拟两遍就可以很清晰的理解这几句代码了。

在这个过程中,我们用到了一下几个性质:

  1. 乘法 满足封闭性
  2. 乘法 满足结合律
  3. 乘法 下有单位元(即1)

即我们在不知不觉中已经使用到了幺半群的相关内容。而如果我们稍加思考,将上述幺半群<N*, *>魔改成<Z, +>呢?因为加法也满足以上的几个性质(单位元是0),所以我们就引申到了另一个神奇的算法——快速乘。这种神奇的算法在罗宾米勒算法中,为了防止a * b % mod时溢出而使用过。当a * b的结果连long long都放不下的时候,求a * b % mod 的结果就需要用到这种方法。

这样我们就得到了快速乘算法的代码。

以上,快速幂和快速乘其实就这么结束了,所以抽象代数真的很厉害。

冻葱Tewi

2018-8-16

转载原创文章请注明,转载自: 冻葱Tewi » 从群论到快速幂和快速乘
  1. ukari

    函数参数里的mod是什么,为什么会有mod

    1. ukari
      @ukari 额,原来是快速幂取模而不是快速幂算法
      1. 冻葱Tewi
        @ukari 2333,因为大部分时候都需要取模所以就直接写上了。