Correctness of multiplication in galois field

Question

I'm into developing code to do arithmetic in Galois field gf(2^8) and I think I'm getting wrong results on multiplication operations.

private static byte Multiply(byte a, byte b)
{
    byte result = 0;

    while (b != 0)
    {
        if ((b & 1) != 0)
        {
            result ^= a;
        }

        a <<= 1;
        b >>= 1;
    }

    return result;
}

The result for Multiply(1, 2) gives the correct value of 2 but Multiply(240, 249) gives me 112 instead of the expected 148.

Now I'm not sure if this value is good or not with Russian Peasant Multiplication.

Maybe there's another algorithm that gives correct results?

Answer 1

Example code:

#define POLY 0x11D

static BYTE GFMpy(BYTE b0, BYTE b1)
{
int i;
int product;
    product = 0;
    for(i = 0; i < 8; i++){
        product <<= 1;
        if(product & 0x100){
            product ^= POLY;}
        if(b0 & 0x80u){
            product ^= b1;}
        b0 <<= 1;}
    return((BYTE)product);
}

---

Example using lookup tables:

#define POLY (0x11d)
/* all non-zero elements are powers of 2 for POLY == 0x11d */
typedef unsigned char BYTE;
/* ... */
static BYTE exp2[512];
static BYTE log2[256];
/* ... */
static void Tbli()
{
int i;
int b;
    b = 0x01;                   /* init exp2 table */
    for(i = 0; i < 512; i++){
        exp2[i] = (BYTE)b;
        b = (b << 1);           /*  powers of 2 */
        if(b & 0x100)
            b ^= POLY;
    }

    log2[0] = 0xff;             /* init log2 table */
    for(i = 0; i < 255; i++)
        log2[exp2[i]] = (BYTE)i;
}
/* ... */
static BYTE GFMpy(BYTE m0, BYTE m1) /* multiply */
{
    if(0 == m0 || 0 == m1)
        return(0);
    return(exp2[log2[m0] + log2[m1]]);
}
/* ... */
static BYTE GFDiv(BYTE m0, BYTE m1) /* divide */
{
    if(0 == m0)
        return(0);
    return(exp2[log2[m0] + 255 - log2[m1]]);
}