$GF(2^n)$上算术运算的实现

Posted on | Edited on | In , | Comments:
在$GF(2^n)$域上的算术运算的python代码实现

  • 代码

  • 几个关键点

    • 求模时，算法如下

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      def __modAndDiv__(x, y):
          """
          return the (x%y, x/y)
          """
          if y == 0:
              raise ZeroDivisionError
          xl = util.bitLen(x)
          yl = util.bitLen(y)
          if xl < yl:
              return x, 0
          d = 0
          while xl >= yl:
              x, d = Polynomial.__sub__(x, y << (xl - yl)), Polynomial.__add__(d, (1 << (xl - yl)))
              xl = util.bitLen(x)
          return x, d

      要注意，不可以直接__sub__(x, y)，要__sub__(x, y<<(xl-yl))，保证y<<(xl-yl)的最高位与x的最高位是同一位，这样才能把x变小。如果直接减，因为x^y^y=x，也就是减去两次y等于没有减，从而死循环

    • 计算乘法逆元时，可以使用extend gcd，也可以使用拉格朗日定理$a^{|s|}=e$（e是群S上的单位元），从而$a^{|s|-1}=a^{-1}$——因为每个元素都只有唯一逆元