The branch in mathematics known as Galois theory (pronounced as "gal-wah")
which is based on abstract algebra was discovered by a young brilliant
french mathematician known as Evariste Galois.
The branch deals mainly with the analysis and formal description of binary
and unary operations upon polynomials comprised of elements within a Galois
field that then describe polynomials within the field itself.
The C++ Galois Field Arithmetic Library, implements a specialised version of Galois Fields
known as extension fields or in other words fields of the form GF(2^m) and was developed
as a base for programming tasks that involved cryptography and error correcting codes. The
library is simple, consise and straight forward, it also uses a series of look-up tables to
increase performance of calculations.
The library is broken into three classes, Galois Field, Galois Field Element and Galois
Field Polynomial. Operations such as addition, subtraction, multiplication, division,
modulus and exponentiation can occur over both field elements and field polynomials and
also left and right shifting can occur for field polynomials.
The binary extensions of Galois fields (GF(2^m)) are used extensively in digital logic and
circuitry. Galois field polynomials within the branch are seen as mathematical equivalents
of Linear Feed-Back Shift Register (LFSR) and operations upon elements are accomplished via
bitwise operations such as xor, and, or logic. Applications within the fields of cryptography
and error correcting codes use Galois fields extensively in such things as S-Box implementations
(bit scramblers), strong random number generators and algebraic codes. Galois theory is used to
describe and generalize results seen in these fields, for example the AES algorithm can be
represented with just a few lines of mathematics using Galois theory and some other related
abstract algebra.
Initially one must setup a Galois Field before you can begin using operations related to the field.
Galois fields are setup by intially defining the size of the field which means how many elements will
exist within the field, and also the values those elements will posses. The values that the elements
will posses are defined by a polynomial that is known as a primitive polynomial of the Galois field.
The field can be setup as follows:
/*
p(x) = 1x^8+1x^7+0x^6+0x^5+0x^4+0x^3+1x^2+1x^1+1x^0
1 1 0 0 0 0 1 1 1
*/
unsigned int prim_poly[9] = {1,1,1,0,0,0,0,1,1};
/*
A Galois Field of type GF(2^8)
*/
galois::GaloisField gf(8,prim_poly);
Once the field has been set-up one may want to initialize Galois field elements, In order
to do this a reference to an already initialized Galois field needs to be passed to the field
element and also the field element's initial vector form value within that particular Galois
field has to be passed.
Initialization of Galois field polynomials requires a reference to a Galois field and also a degree
of the polynomial and an array to coefficients of each term within the polynomial, the following
will produce a polynomial in the form of p(x) = 10x^9 + 9x^8 + 8x^7 + 7x^6 + 6x^5 + 5x^4 + 4x^3 + 3x^2 + 2x^1 + 1x^0
A practical example of the C++ Galois Field Arithmetic library being
used as part of a reed-solomon error correcting code encoder:
GaloisField* gf; // reed-solomon defined Galois field
GaloisFieldPolynomial generator; // generator polynomial for reed-solomon
unsigned int code_length; // data + fec length
unsigned int fec_length; // number of fec symbols
unsigned int data_length; // data length
std::string data // data to be encoded
std::string fec = string(fec_length,0x0);
GaloisFieldPolynomial message(gf,code_length);
for(unsigned int i = fec_length; i < code_length; i++)
{
message[i] = data[code_length - i - 1];
}
GaloisFieldPolynomial parities = message % generator;
for(unsigned int i = 0; i < fec_length; i++)
{
fec[i] = parities[fec_length - i - 1].poly();
}
Free use of The Galois Field Arithmetic Library is permitted under the guidelines and in accordance with
the most current version of the "Common Public License."
