{{ message }}

Instantly share code, notes, and snippets.

# meagtan/galois.c

Last active Jun 6, 2021
Quick implementation of Galois fields
 /* * The following is an implementation of the finite field GF(2^8) as bit vectors of length 8, where the nth bit represents the * coefficient of the nth power of the generator in each element, and the generator satisfies the minimal polynomial * x^8 + x^4 + x ^3 + x^2 + 1 in the prime field Z_2, in which addition is equivalent to XOR and multiplication to AND. * The elements of GF(2^8) thus represent polynomials of degree < 8 in the generator x. Addition in this field is simply * bitwise XOR, but multiplication requires the elimination of powers of x <= 8. */ #include #include typedef uint8_t gal8; /* Galois field of order 2^8 */ const gal8 min_poly = 0b11101, /* Minimal polynomial x^8 + x^4 + x^3 + x^2 + 1 */ generator = 0b10; /* Generator of Galois field */ gal8 gal_add(gal8 a, gal8 b); /* Add two elements of GF(2^8) */ gal8 gal_mul(gal8 a, gal8 b); /* Multiply two elements of GF(2^8) */ void gal_print(gal8 a); /* Print an element of GF(2^8) in binary form */ int hamming_norm(int a); /* Number of nonzero bits in a */ int hamming_distance(int a, int b); /* Number of different bits between a and b */ int main() { int i = 0, c = 0; gal8 a = 1; while (i++ < 256) { gal_print(a); /* printf("%d", hamming_distance(a, gal_mul(a, generator))); */ a = gal_mul(a, generator); if (c++ < 7) { putchar(' '); } else { putchar('\n'); c = 0; } } if (c) putchar('\n'); } gal8 gal_add(gal8 a, gal8 b) { return a ^ b; } gal8 gal_mul(gal8 a, gal8 b) { gal8 res = 0; for (; b; b >>= 1) { if (b & 1) res ^= a; if (a & 0x80) a = (a << 1) ^ min_poly; else a <<= 1; } return res; } void gal_print(gal8 a) { int i = 8; while (i--) putchar((a >> i & 1) + '0'); } int hamming_norm(int a) { int res = 0; while (a) { if (a & 1) ++res; a >>= 1; } return res; } int hamming_distance(int a, int b) { return hamming_norm(a ^ b); }
 /* * This alternate implementation realizes elements of the finite field GF(2^8) as 8x8 matrices of bits, or arrays of 8 bytes. * The generator of the finite field is simply the companion matrix of the minimal polynomial x^8 + x^4 + x^3 + x^2 + 1, * or its transpose. The arithmetic in this finite field is usual matrix arithmetic. */ #include #include #include /* for sleep */ typedef uint8_t gal8; const gal8 gener[8] = {1, 0x80, 0x40 + 1, 0x20 + 1, 0x10 + 1, 8, 4, 2}, /* companion matrix of min_poly */ gentr[8] = {0x40, 0x20, 0x10, 8, 4, 2, 1, 0b10111000}, /* transpose of gener */ unity[8] = {0x80, 0x40, 0x20, 0x10, 8, 4, 2, 1}, zero[8] = {0}; gal8 *mat_add(gal8 *a, gal8 *b); /* add two matrices */ gal8 *mat_mul(gal8 *a, gal8 *b); /* multiply two matrices */ gal8 *mat_scalar_mul(uint8_t a, gal8 *b); /* multiply matrix by scalar */ gal8 mat_app(gal8 a, gal8 *b); /* apply matrix to row vector */ gal8 *to_matrix(gal8 a); /* convert byte into matrix */ void mat_print(gal8 *a); /* print matrix */ int main() { int i, j; gal8 a[8] = {0}, *aux; /* copy unity onto a */ for (i = 0; i < 8; ++i) a[i] = unity[i]; /* print each power of gentr */ for (j = 0; j < 256; ++j) { mat_print(a); aux = mat_mul(a, gentr); for (i = 0; i < 8; ++i) a[i] = aux[i]; sleep(1); putchar('\n'); } } gal8 *mat_add(gal8 *a, gal8 *b) { gal8 res[8]; int i; for (i = 0; i < 8; ++i) res[i] = a[i] + b[i]; return res; } gal8 *mat_mul(gal8 *a, gal8 *b) { gal8 res[8] = {0}; int i, j, k; /* For each ij, res_ij = sum of a_ik & b_kj for each k */ for (i = 0; i < 8; ++i) for (j = 0; j < 8; ++j) for (k = 0; k < 8; ++k) res[i] ^= ((a[i] >> (7 - k)) & (b[k] >> (7 - j)) & 1) << (7 - j); return res; } /* this concerns a as a scalar, not as a gal8 */ gal8 *mat_scalar_mul(uint8_t a, gal8 *b) { gal8 res[8]; int i; for (i = 0; i < 8; ++i) res[i] = a & b[i]; return res; } /* a is taken to be a row vector, applied to b from the left */ gal8 mat_app(gal8 a, gal8 *b) { gal8 res = 0; int i, j; /* multiply the ith row of b with the ith bit of a starting from the left */ for (i = 0, j = 0x80; i < 8; ++i, j >>= 1) if (a & j) res ^= b[i]; return res; } /* convert a to its matrix equivalent */ gal8 *to_matrix(gal8 a) { gal8 res[8] = {0}, *aux; int i; for (; a; a >>= 1) { aux = mat_add(res, mat_scalar_mul(a & 1, gener)); for (i = 0; i < 8; ++i) res[i] = aux[i]; } return res; } void mat_print(gal8 *a) { int i; for (i = 0; i < 8; ++i) { gal_print(a[i]); putchar('\n'); } }

### abidsyed4u commented May 4, 2019

 First prog is ok.But 2nd prog i.e with matrix is giving errors.pl see

### ph04 commented Dec 24, 2020

 galois.c line 14 IS WRONG, use 0b00011011 instead

### abhijeetviswa commented Apr 2, 2021

 For posterity's sake, the gal_mul function uses a modified version of the peasant's algorithm. The algorithm with explanation itself is described on Wikipedia.