无进位乘法逆元计算异常？8位实现结果不符预期

我参考了无进位乘法逆元的实现指导，但针对8位值对的简易实现没得到预期结果。针对8位输入[c]和[d]，计算得到结果[t]，当[t]为奇数时，将其传入逆元函数得到[e]，但[e]与[c]、[d]的对比结果不符合预期，请问问题出在哪里？

相关实现代码 #

static uint cl_mul(uint a, uint b)
{
    uint r = 0;
    while (b != 0)
    {
        if ((a & 1) != 0)
            r ^= b;      // 无进位加法即异或
        a >>= 1;
        b <<= 1;
    }
    return r;
}

static uint clmulinv(uint x)
{
    uint inv = 1;
    uint rem = x;
    for (int i = 1; i < 32; i++)
    {
        if (((rem >> i) & 1) != 0)
        {
            rem ^= x << i;
            inv |= 1u << i;
        }
    }
    return inv;
}

int main(int argc, char *argv[])
{
    
    uint16_t cc=0,dd=0;       
    uint8_t  c=0,d=0;
    uint16_t t=0,e=0, k=0;
    
    
    for(cc = 0; cc < 256; cc++)  {
        for(dd = 0; dd < 256; dd++) {
    
            c = cc;
            d = dd;
            
            t = cl_mul(d,c);
            e = clmulinv(t);


            if((t & 0x1) && ((e == d) || (e == c))) {
                printf("k %4llu  c %4hhu    d %4hhu  t  %4llu  e %4hhu   \n",k,c,d,t,e);
                k++;
                }
            }
        }
            
}  

测试输出 #

k    0  c    1  d    1          t      1        e    1
k    1  c    5  d  255          t    771        e  255
k    2  c   17  d   85          t   1285        e   85
k    3  c   21  d  219          t   3591        e  219
k    4  c   51  d   85          t   3855        e   51
k    5  c   65  d   73          t   4617        e   73
k    6  c   69  d  151          t   9995        e  151
k    7  c   73  d   65          t   4617        e   73
k    8  c   81  d  157          t   11789       e  157
k    9  c   85  d   17          t   1285        e   85
k   10  c   85  d   51          t   3855        e   51
k   11  c  151  d   69          t   9995        e  151
k   12  c  157  d   81          t   11789       e  157
k   13  c  219  d   21          t   3591        e  219
k   14  c  255  d    5          t    771        e  255

问题根源 #

1. 无进位乘法未做模运算 #

当前cl_mul是无限制的位运算乘法，输出的t是16位甚至更长的数值，但GF(2^8)（8位二进制域）中的无进位乘法必须模不可约多项式（行业标准是x^8 + x^4 + x^3 + x + 1，对应十六进制0x11B）。你直接用原始乘法结果求逆元，相当于在更大的域里计算，结果自然和8位的[c]/[d]不匹配。

2. 逆元函数逻辑完全错误 #

clmulinv的实现根本不符合GF(2^m)中求逆元的扩展欧几里得算法逻辑，只是简单通过位操作修改rem和inv，完全无法正确计算逆元。

3. 测试逻辑不符合域运算规则 #

你期望e == c或e == d，但实际上在GF(2^8)中，t = c * d（模不可约多项式）的逆元是c^{-1} * d^{-1}，只有当其中一个数是1时，逆元才会等于另一个数的逆元，你的测试条件本身就不成立。

修正方案 #

修正无进位乘法（添加模运算） #

static uint8_t cl_mul(uint8_t a, uint8_t b) {
    uint8_t r = 0;
    const uint8_t poly = 0x1B; // 对应x^8+x^4+x^3+x+1，模2^8取低8位
    while (b != 0) {
        if (b & 1) {
            r ^= a;
        }
        a <<= 1;
        if (a & 0x100) { // 超过8位时模多项式
            a ^= poly;
        }
        b >>= 1;
    }
    return r;
}

实现正确的扩展欧几里得逆元算法 #

static uint8_t clmulinv(uint8_t x) {
    uint8_t u = x;
    uint8_t v = 0x11B; // 不可约多项式x^8+x^4+x^3+x+1
    uint8_t g1 = 1, g2 = 0;
    while (u != 1) {
        int k = 0;
        while (((u >> k) & 1) == 0) {
            k++;
        }
        // 交换u/v和g1/g2，保证u的最高位不高于v
        if ((u >> k) > (v >> __builtin_ctz(v))) {
            uint8_t temp = u; u = v; v = temp;
            temp = g1; g1 = g2; g2 = temp;
        }
        u ^= v << k;
        g1 ^= g2 << k;
        // 限制在8位范围内
        u &= 0xFF;
        g1 &= 0xFF;
    }
    return g1;
}

修正测试逻辑（验证逆元定义） #

int main(int argc, char *argv[]) {
    uint8_t c, d;
    uint8_t t, e;
    unsigned int k = 0;
    
    for(c = 0; c < 256; c++) {
        for(d = 0; d < 256; d++) {
            t = cl_mul(d, c);
            if ((t & 0x1) == 0) {
                continue; // 偶数在GF(2^8)中无逆元
            }
            e = clmulinv(t);
            // 验证逆元正确性：t*e ≡ 1 mod 0x11B
            if (cl_mul(t, e) == 1) {
                printf("k %4u  c %3hhu    d %3hhu  t %3hhu  e %3hhu\n", k, c, d, t, e);
                k++;
            }
        }
    }
    return 0;
}

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