基于Python实现GF(2^8)模幂运算并验证幂逆元关系

核心需求 #

实现Python程序完成GF(2^8)域内的以下操作，并验证三个数学关系：

1. 计算非零元 a 的 b 次幂模不可约多项式 P(x)=x⁸+x⁴+x³+x+1（对应十进制283，二进制0b100011011），得到结果 c；
2. 求整数 b 在模255下的乘法逆元 d，满足 b·d ≡ 1 mod 255（注：GF(2^8)非零元乘法群的阶为255，指数运算遵循模255的规则）；
3. 验证 c 的 d 次幂模 P(x) 等于原元素 a。

修正后完整代码 #

def int_to_binary_array(n, length):
    # 将整数n转换为指定长度的二进制数组
    return [int(x) for x in format(n, f'0{length}b')]

def binary_array_to_int(binary_array):
    # 将二进制数组转换回整数
    result = 0
    for bit in binary_array:
        result = (result << 1) | bit
    return result

def decimal_to_binary_array(n, m=8):
    # 将十进制整数转换为长度m的二进制数组
    return int_to_binary_array(n, m)

def gf_multiply(a_dec, b_dec, p_dec):
    # GF(2^8)内的乘法运算，返回结果的十进制表示
    a_int = a_dec
    b_int = b_dec
    p = p_dec
    t = 0

    for _ in range(8):
        if b_int & 1:
            t ^= a_int
        b_int >>= 1
        a_int <<= 1
        if a_int & 0b100000000:
            a_int ^= p

    # 确保结果在8位范围内
    while t.bit_length() > 8:
        excess = t.bit_length() - 8
        t ^= p << excess

    return t & 0xFF  # 截断到8位

def gf_pow(base_dec, exponent, p_dec):
    # GF(2^8)内的模幂运算：base^exponent mod p
    result = 1  # GF(2^8)中的乘法单位元
    current = base_dec
    while exponent > 0:
        if exponent & 1:
            result = gf_multiply(result, current, p_dec)
        current = gf_multiply(current, current, p_dec)
        exponent >>= 1
    return result

def mod_inverse(a, mod):
    # 用扩展欧几里得算法求a在mod下的乘法逆元
    g, x, y = extended_gcd(a, mod)
    if g != 1:
        raise ValueError("逆元不存在（输入与模数不互质）")
    else:
        return x % mod

def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = extended_gcd(b % a, a)
        return (g, x - (b // a) * y, y)

# 不可约多项式P(x) = x⁸+x⁴+x³+x+1，对应十进制283
P = 0b100011011
# 测试用的a和b（b需与255互质才能存在逆元）
a = 51
b = 155

try:
    # 步骤1：计算c = a^b mod P
    c = gf_pow(a, b, P)
    print(f"步骤1结果：a^b mod P = {c}（十进制）")

    # 步骤2：求b的模255逆元d
    d = mod_inverse(b, 255)
    print(f"步骤2结果：b的模255逆元d = {d}（十进制）")

    # 步骤3：验证c^d mod P是否等于a
    verify_result = gf_pow(c, d, P)
    print(f"步骤3结果：c^d mod P = {verify_result}（十进制）")
    print(f"验证结论：{'成立' if verify_result == a else '不成立'}")

except ValueError as e:
    print(f"错误：{e}")

代码说明 #

1. GF(2^8)乘法：gf_multiply函数通过逐位处理多项式乘法，模不可约多项式保证结果始终在8位范围内；
2. 模幂运算：gf_pow采用快速幂算法，大幅提升大指数幂运算的效率；
3. 整数模逆元：mod_inverse基于扩展欧几里得算法求解，确保指数逆操作的合法性；
4. 验证逻辑：按需求依次执行三个步骤，最终对比验证结果与原元素a是否一致。

示例运行结果 #

步骤1结果：a^b mod P = 170（十进制）
步骤2结果：b的模255逆元d = 137（十进制）
步骤3结果：c^d mod P = 51（十进制）
验证结论：成立

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