Skip to content

Instantly share code, notes, and snippets.

@meagtan
Last active Jun 6, 2021
Embed
What would you like to do?
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 <stdio.h>
#include <stdint.h>
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 <stdio.h>
#include <stdint.h>
#include <unistd.h> /* 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

This comment has been minimized.

Copy link

@abidsyed4u abidsyed4u commented May 4, 2019

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

@ph04

This comment has been minimized.

Copy link

@ph04 ph04 commented Dec 24, 2020

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

@abhijeetviswa

This comment has been minimized.

Copy link

@abhijeetviswa 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment