如何在F_{2^8}有限域实现加法与乘法，修复现有代码乘法模运算问题

现有代码核心问题 #

• 递归函数无返回值：add、multiply的补前导0递归逻辑没有return，执行完递归后会继续走后续错误逻辑
• 加法实现冗余且不符合F_2特性：F_2下加法等价于按位异或，不需要逐位处理十进制加法结果
• 乘法逻辑错误1：y最低位为1时，不需要对y执行加1操作，仅需累加当前x到结果即可
• 乘法逻辑错误2：不可约多项式取模时机错误，仅当x左移后最高位为1（即左移前x的最高位是1）时，才需要和不可约多项式100011011做异或，不是每次左移都异或
• 位宽处理逻辑缺陷：toBinary仅返回8位，左移后的9位高位直接丢失，无法判断是否需要取模

修正后可运行代码 #

# 通用转二进制函数，支持指定返回位宽
def toBinary(self, n, width=8):
    return ''.join(str(1 & int(n) >> i) for i in range(width)[::-1])

def add(self, x, y):
    """
    F_2加法等价于按位异或
    "10111001" + "10010100" = "00101101"
    """
    # 补前导0到8位，直接用zfill更简洁
    x = x.zfill(8)
    y = y.zfill(8)
    # 按位异或后转8位二进制
    return self.toBinary(int(x, 2) ^ int(y, 2))
    
def multiply(self, x, y):
    """
    F_2^8乘法，模不可约多项式x^8 + x^4 + x^3 + x + 1（即二进制100011011，对应十进制283）
    "10111001" * "10010100" = "10110010"
    """
    x = x.zfill(8)
    y = y.zfill(8)
    x_int = int(x, 2)
    y_int = int(y, 2)
    result = 0
    ir_poly = 0b100011011  # 不可约多项式整数值

    while y_int > 0:
        # y最低位为1，累加当前x到结果
        if y_int & 1:
            result ^= x_int
        # x左移1位
        x_int <<= 1
        # 若x超过8位，模不可约多项式
        if x_int >> 8:
            x_int ^= ir_poly
        # y右移1位
        y_int >>= 1
    # 返回8位二进制字符串
    return self.toBinary(result)

逻辑说明 #

• 所有运算直接用整数位操作实现，比字符串逐位处理效率高且不易出错
• 取模逻辑仅在x左移后最高位为1（即x_int >= 256）时执行异或不可约多项式操作，符合有限域乘法规则
• 补前导0直接用字符串zfill方法替代递归，逻辑更清晰

内容的提问来源于stack exchange，提问作者harlee53