使用 Python 3 计算 gf(2^8) 中的乘法逆的纯 Python 方法

Question

如何在 Python 3 中实现 GF2^8 中的乘法逆？我当前的函数如下所示：

def gf_add(a, b):
    return a ^ b

def gf_mul(a, b, mod=0x1B):
    p = bytes(hex(0x00))
    for i in range(8):
        if (b & 1) != 0:
            p ^= a
        high_bit_set = bytes(a & 0x80)
        a <<= 1
        if high_bit_set != 0:
            a ^= mod
        b >>= 1
    return p

Answer 1

这是我的做法：

def gf_degree(a) :
  res = 0
  a >>= 1
  while (a != 0) :
    a >>= 1;
    res += 1;
  return res

def gf_invert(a, mod=0x1B) :
  v = mod
  g1 = 1
  g2 = 0
  j = gf_degree(a) - 8

  while (a != 1) :
    if (j < 0) :
      a, v = v, a
      g1, g2 = g2, g1
      j = -j

    a ^= v << j
    g1 ^= g2 << j

    a %= 256  # Emulating 8-bit overflow
    g1 %= 256 # Emulating 8-bit overflow

    j = gf_degree(a) - gf_degree(v)

  return g1

函数gf_degree计算多项式的次数，而gf_invert自然会反转GF(2^8)的任何元素，当然0除外。 gf_invert 的实现遵循 "text-book" 算法寻找有限域元素的乘法逆元。

例子

print(gf_invert(5))   # 82
print(gf_invert(1))   #  1
print(gf_invert(255)) # 28

Here is a live demo.

如评论中所述，您也可以使用对数方法，或者简单地使用蛮力（尝试乘法的每种组合）。

Answer 2

您可以查看我的 libgf2 module（实际上没有其他人使用）并使用 GF2Element:

from libgf2 import GF2Element

x = GF2Element(0x8, 0x11B)
x.inv 
# find the inverse of x^3 in the quotient ring GF(2)[x]/p(x)
# where p(x) = x^8 + x^4 + x^3 + x + 1 (0x11B in bit vector format)

有关详细信息，请参阅 this blog article。

注意：libgf2 在 Python 2.7 中，因此您必须移植到 Python 3，但它是一个相当小的库。

使用 Python 3 计算 gf(2^8) 中的乘法逆的纯 Python 方法

A Pure Python way to calculate the multiplicative inverse in gf(2^8) using Python 3

python

python-3.x

galois-field

finite-field