0

我正在尝试为 GF(2^8) 中的 2 个多项式创建欧几里得算法（以解决 Bezout 的关系）。

我目前有此代码用于我的不同操作


class ReedSolomon:   
    gfSize = 256
    genPoly = 285 
    log = [0]*gfSize
    antilog = [0]*gfSize


    def _genLogAntilogArrays(self):
        self.antilog[0] = 1
        self.log[0] = 0
        self.antilog[255] = 1
        for i in range(1,255):
            self.antilog[i] = self.antilog[i-1] << 1 
            if self.antilog[i] >= self.gfSize:
                self.antilog[i] = self.antilog[i] ^ self.genPoly
            self.log[self.antilog[i]] = i

def __init__(self):
        self._genLogAntilogArrays()

def _galPolynomialDivision(self,dividend, divisor):
        result = dividend.copy()
        for i in range(len(dividend) - (len(divisor)-1)):
            coef = result[i]
            if coef != 0:
                for j in range(1, len(divisor)):
                    if divisor[j] != 0: 
                        result[i + j] ^= self._galMult(divisor[j], coef) # équivalent result[i + j] += -divisor[j] * coef car dans un champ GF(2) addition <=> substraction <=> XOR

        remainderIndex = -(len(divisor)-1)
        return result[:remainderIndex], result[remainderIndex:]

def _galMultiplicationPolynomiale(self, x,y):
        result = [0]*(len(x)+len(y)-1)
        for i in range(len(x)):
            for j in range(len(y)):
                result[i+j] ^= self._galMult(x[i],y[j])
        return result

def _galMult(self,x,y):
        if ((x == 0) or (y == 0)):
            val = 0
        else:
            val = self.antilog[(self.log[x] + self.log[y])%255]
        return val

def _galPolynomialAddition(self, a, b):
        polSum = [0] * max(len(a), len(b))
        for index in range(0, len(a)):
            polSum[index + len(polSum) - len(a)] = a[index]
        for index in range(0, len(b)):
            polSum[index + len(polSum) - len(b)] ^= b[index]
        return (polSum)

这是我的欧几里得算法：

def _galEuclideanAlgorithm(self,a,b):
        r0 = a.copy()
        r1 = b.copy()

        u0 = [1]
        u1 = [0]

        v0 = [0]
        v1 = [1]
        while max(r1) != 0:
            print(r1)
            q,r = self._galPolynomialDivision(r0,r1)
            r0 = self._galPolynomialAddition(self._galMultiplicationPolynomiale(q,r1),r)
            r1,r0 = self._galPolynomialAddition(r0,self._galMultiplicationPolynomiale(q,r1)),r1.copy()
            u1,u0 = self._galPolynomialAddition(u0,self._galMultiplicationPolynomiale(q,u1)),u1.copy()
            v1,v0 = self._galPolynomialAddition(v0,self._galMultiplicationPolynomiale(q,v1)),v1.copy()
        return r1,u1,v1

我不明白我的算法循环的问题，这是我的测试剩余输出：

rs = ReedSolomon()
a = [1,15,7,8,0,11]

b = [1,0,0,0,0,0,0]

print(rs._galEuclideanAlgorithm(b,a))

#Console output
'''
[1, 15, 7, 8, 0, 11]
[0, 0, 82, 37, 120, 11, 105]
[1, 15, 7, 8, 0, 11]
[0, 0, 82, 37, 120, 11, 105]
[1, 15, 7, 8, 0, 11]
[0, 0, 82, 37, 120, 11, 105]
[1, 15, 7, 8, 0, 11]
'''

我知道我似乎在抛出一些代码只是希望得到答案，但我真的在寻找错误。

提前致谢 ！

4

1 回答 1

0

我创建了一个名为galois的 Python 包来执行此操作。galois扩展 NumPy 数组以对 Galois 域进行操作。代码是用 Python 编写的，但为了提高速度，使用 Numba 进行了 JIT 编译。除了数组算术，它还支持伽罗瓦域上的多项式。...而且Reed-Solomon 代码也得到了实施 :)

用于求解两个多项式的 Bezout 恒等式的扩展欧几里得算法GF(2^8)将以这种方式求解。下面是一段简短的源代码。你可以在这里看到我的完整源代码。

def poly_egcd(a, b):
    field = a.field
    zero = Poly.Zero(field)
    one = Poly.One(field)

    r2, r1 = a, b
    s2, s1 = one, zero
    t2, t1 = zero, one

    while r1 != zero:
        q = r2 / r1
        r2, r1 = r1, r2 - q*r1
        s2, s1 = s1, s2 - q*s1
        t2, t1 = t1, t2 - q*t1

    # Make the GCD polynomial monic
    c = r2.coeffs[0]  # The leading coefficient
    if c > 1:
        r2 /= c
        s2 /= c
        t2 /= c

    return r2, s2, t2

这是一个使用galois库和示例中的多项式的完整示例。（我假设最高系数是第一位的？）

In [1]: import galois                                                                                                                                                                          

In [2]: GF = galois.GF(2**8)                                                                                                                                                                   

In [3]: print(GF.properties)                                                                                                                                                                   
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: x^8 + x^4 + x^3 + x^2 + 1
  is_primitive_poly: True
  primitive_element: x

In [4]: a = galois.Poly([1,15,7,8,0,11], field=GF); a                                                                                                                                          
Out[4]: Poly(x^5 + 15x^4 + 7x^3 + 8x^2 + 11, GF(2^8))

In [5]: b = galois.Poly([1,0,0,0,0,0,0], field=GF); b                                                                                                                                          
Out[5]: Poly(x^6, GF(2^8))

In [6]: d, s, t = galois.poly_egcd(a, b); d, s, t                                                                                                                                              
Out[6]: 
(Poly(1, GF(2^8)),
 Poly(78x^5 + 7x^4 + 247x^3 + 74x^2 + 152, GF(2^8)),
 Poly(78x^4 + 186x^3 + 45x^2 + x + 70, GF(2^8)))

In [7]: a*s + b*t == d                                                                                                                                                                         
Out[7]: True
于 2021-08-11T17:59:59.710 回答