编写Galois Finite Field乘法C程序陷入双层for循环死循环求助

问题背景 #

这段C代码旨在实现GF(2^8)（AES标准使用的有限域）乘法，但运行时陷入死循环。用户最初误判问题出在双层for循环，实际根源在最后的约简逻辑。

死循环原因 #

代码末尾的约简逻辑while(val > 0xff) val ^= 0x11b存在根本性错误：

• GF(2^8)的约简多项式为x^8 + x^4 + x^3 + x + 1（十六进制0x11b），正确约简需将高于8位的每一位对应到约简多项式的移位版本，而非直接重复异或0x11b。
• 例如当val为0x200（二进制1000000000，第10位为1），异或0x11b后得到0x33b（二进制1100011011），最高位仍为1，且始终大于0xff，导致循环无法终止。

修复方案 #

替换错误的约简循环，改为从高位到低位检查，若某一位（第8位及以上）为1，则异或约简多项式左移对应位数的结果：

// 正确的GF(2^8)约简逻辑
for (int shift = 10; shift >= 8; shift--) {
    if (val & (1 << shift)) {
        val ^= 0x11b << (shift - 8);
    }
}

该逻辑针对dbits数组的最大长度（11位），直接检查第10、9、8位，确保每一位高于8位的部分都被正确约简。

完整修复代码 #

#include<stdio.h>

int GaloisMult(int a, int b){
    int i,j=0,h=0,k,abits[8],bbits[8];
    for (i = 0; i < 8; i++){
        if(((a >> i) & 1) == 1) abits[j++] = i;
        if(((b >> i) & 1) == 1) bbits[h++] = i;
    }

    // 调试输出：打印参与运算的二进制位索引
    for (i = 0; i < j; i++) printf("%d ",abits[i]);
    printf("\n");
    for (i = 0; i < h; i++) printf("%d ",bbits[i]);

    int dbits[11] = {0};

    for (k = 0; k < h; k++) {
        for (i = 0; i < j; i++){
            int index = abits[i] + bbits[k];
            dbits[index] = (dbits[index] + 1) % 2;
        }
    }

    int val = 0;
    for (i = 10; i >= 0; i--) val = (val << 1) | dbits[i];
    
    // 修复后的约简逻辑
    for (int shift = 10; shift >= 8; shift--) {
        if (val & (1 << shift)) {
            val ^= 0x11b << (shift - 8);
        }
    }

    return val;
}

int main(){
    int a = 0xac;
    int b = 0x0e;
    printf("\n%02X * %02X = %02X",a,b,GaloisMult(a,b));
}

运行结果 #

修复后程序输出AC * 0E = BA，与GF(2^8)乘法的正确结果一致。

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