GF(2)多项式模运算求助：相加后模给定多项式的实现步骤

需要计算两个多项式：x⁸+x⁵+x³+x²+1 和 x⁶+x⁵+x³+x²+x 的和，再对多项式(x⁸+x⁶+x⁵+x+1)取模。已完成多项式转类二进制整数及GF(2)域的XOR加法，得到rev_sum，现需完成模运算并转回多项式形式。

原实现代码：

x = "x8+x5+x3+x2+x0"
y = "x6+x5+x3+x2+x1"
m = "x8+x6+x5+x1+x0"
X = 0
Y = 0
M = 0
# converting polynomials to binary
for l in x:
    if l.isdigit() == True:
        X = X + 10**int(l)
for l in y:
    if l.isdigit() == True:
        Y = Y + 10**int(l)
for l in m:
    if l.isdigit() == True:
        M = M + 10**int(l)
sum=0 
# adding two binary values       
while X!=0 :
    d1 = X%10
    d2 = Y%10
    sum = (sum*10) + (d1^d2)
    Y = Y//10
    X = X//10
# reversing the sum coz the addition was performed reversed
rev_sum = 0
while sum != 0:
    digit = sum % 10
    rev_sum = rev_sum * 10 + digit
    sum //= 10 

核心思路 #

GF(2)域下的多项式模运算本质是无借位的多项式除法，用XOR操作代替减法。需要先把模拟的类二进制数转成真实二进制整数，完成模运算后再转回多项式字符串。

完整补充代码 #

将以下代码追加到原代码末尾即可：

# 1. 把类二进制整数（如100100000）转为真实二进制整数
def class_bin_to_real_int(class_num):
    return int(str(class_num), 2)

sum_real_bin = class_bin_to_real_int(rev_sum)
mod_real_bin = class_bin_to_real_int(M)

# 2. 实现GF(2)多项式模运算
def gf2_poly_mod(dividend, divisor):
    if divisor == 0:
        raise ValueError("除数不能为0")
    divisor_bit_len = divisor.bit_length()
    # 当被除数位数大于等于除数时，持续执行XOR消去最高位
    while dividend.bit_length() >= divisor_bit_len:
        shift_bits = dividend.bit_length() - divisor_bit_len
        dividend ^= (divisor << shift_bits)
    return dividend

mod_result = gf2_poly_mod(sum_real_bin, mod_real_bin)

# 3. 把二进制结果转回多项式字符串
def bin_int_to_polynomial(bin_num):
    if bin_num == 0:
        return "0"
    terms = []
    # 从最低位（x^0）遍历到最高位
    for exp in range(bin_num.bit_length()):
        if bin_num & (1 << exp):
            if exp == 0:
                terms.append("1")
            elif exp == 1:
                terms.append("x")
            else:
                terms.append(f"x{exp}")
    # 按指数从高到低排序，输出标准多项式格式
    terms.sort(key=lambda t: int(t[1:]) if len(t) > 1 else -1, reverse=True)
    return "+".join(terms)

# 输出最终结果
final_result = bin_int_to_polynomial(mod_result)
print("模运算结果多项式：", final_result)

代码说明 #

• 类二进制转真实二进制：将rev_sum和M转为字符串后，用int(s,2)直接解析为二进制整数，方便后续位运算。
• GF(2)模运算：通过位长度判断最高位位置，左移除数对齐后执行XOR，逐步消去被除数的高位，直到被除数位数小于除数。
• 二进制转多项式：遍历每一位，收集所有值为1的位对应的多项式项，排序后拼接成标准格式。

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