Skip to content

Instantly share code, notes, and snippets.

@rbrito
Forked from meagtan/galois.c
Created May 23, 2019
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');
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment