Reed-Solomon 纠错码

羊城杯的一道题，题目中只破坏了消息的随机两个位置，消息又在 256 以内，所以可以直接暴力枚举。 下面探寻优雅点的解法。

编码

先来看看题目的代码，如下是编码的核心函数：

m = 257
F = Zmod(m)
alpha = F(223)
PR.<x> = PolynomialRing(F)
gx = (x - alpha ^ 0) * (x - alpha ^ 1) * (x - alpha ^ 2) * (x - alpha ^ 3)

def encode_block(message):
    assert isinstance(message, list)

    f = PR([0] * 4 + message)
    px = f % gx
    mx = f - px
    c = [_ for _ in mx]
    return c + (8 - len(c)) * [0]

分析一下，代码中取一个生成多项式 ，然后将消息多项式 模 ，得到余数多项式 ，最后得到编码后的消息 。这时有 。 这里解释一下各个参数，当时我也是看了好久 sagemath 的文档也没搞懂。 生成多项式

解码

照着这篇文章搓了个 PGZ 解码器，代码如下：

def decode_block(r_x):
    S = [PR(r_x)(alpha^i) for i in range(4)]
    nu = 2
    A = matrix(F,nu,nu)
    for i in range(nu):
        for j in range(nu):
            A[i,j] = S[i+j]
    b = vector(F,[-S[nu+i] for i in range(nu)])
    x = list(A.solve_right(b))
    x.append(1)
    x.reverse()
    Lambda = PR(x)
    I = []
    for i in range(8):
        if Lambda(alpha^(-i))==0:
            I.append(i)
    I = I + [0] * (2 - len(I))
    X = [alpha^I[i] for i in range(2)]
    A = matrix(F,2,2)
    for i in range(2):
        for j in range(2):
            A[i,j] = X[j]^i
    b = list(A.solve_right(vector(F,S[:2])))
    for i in range(len(I)):
        r_x[I[i]] -= b[i]
    return r_x[4:]

参考

• https://zhuanlan.zhihu.com/p/104306038
• https://eprint.iacr.org/2017/733.pdf