Description
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.
Usage Of Galois Field Arithmetic Library
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.
galois::GaloisField gf(8,prim_poly);
galois::GaloisFieldElement element1(&gf, 1);
galois::GaloisFieldElement element2(&gf, 2);
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
galois::GaloisField gf(8,prim_poly);
galois::GaloisFieldElement gfe[10] = {
galois::GaloisFieldElement(&gf, 1),
galois::GaloisFieldElement(&gf, 2),
galois::GaloisFieldElement(&gf, 3),
galois::GaloisFieldElement(&gf, 4),
galois::GaloisFieldElement(&gf, 5),
galois::GaloisFieldElement(&gf, 6),
galois::GaloisFieldElement(&gf, 7),
galois::GaloisFieldElement(&gf, 8),
galois::GaloisFieldElement(&gf, 9),
galois::GaloisFieldElement(&gf,10)
};
galois::GaloisFieldPolynomial polynomial(&gf,9,gfe);
Performing operations on Galois field elements are as follows:
galois::GaloisField gf(8,prim_poly);
galois::GaloisFieldElement element1(&gf, 1);
galois::GaloisFieldElement element2(&gf, 2);
galois::GaloisFieldElement element3;
element3 = element1 + element2; // addition
element3 = element1 - element2; // subtraction
element3 = element1 * element2; // multiplication
element3 = element1 / element2; // division
element3 = element1 ^ element2; // exponentiation
Performing operations on Galois field polynomials are as follows:
galois::GaloisField gf(8,prim_poly);
galois::GaloisFieldElement gfe1[10] = {
galois::GaloisFieldElement(&gf, 1),
galois::GaloisFieldElement(&gf, 2),
galois::GaloisFieldElement(&gf, 3),
galois::GaloisFieldElement(&gf, 4),
galois::GaloisFieldElement(&gf, 5),
galois::GaloisFieldElement(&gf, 6),
galois::GaloisFieldElement(&gf, 7),
galois::GaloisFieldElement(&gf, 8),
galois::GaloisFieldElement(&gf, 9),
galois::GaloisFieldElement(&gf,10)
};
galois::GaloisFieldElement gfe2[10] = {
galois::GaloisFieldElement(&gf,10),
galois::GaloisFieldElement(&gf, 9),
galois::GaloisFieldElement(&gf, 8),
galois::GaloisFieldElement(&gf, 7),
galois::GaloisFieldElement(&gf, 6),
galois::GaloisFieldElement(&gf, 5),
galois::GaloisFieldElement(&gf, 4),
galois::GaloisFieldElement(&gf, 3),
galois::GaloisFieldElement(&gf, 2),
galois::GaloisFieldElement(&gf, 1)
};
galois::GaloisFieldPolynomial poly1(&gf, 9,gfe1);
galois::GaloisFieldPolynomial poly2(&gf, 9,gfe2);
galois::GaloisFieldPolynomial poly3;
poly3 = poly1 + poly2; // addition
poly3 = poly1 - poly2; // subtraction
poly3 = poly1 * poly2; // multiplication
poly3 = poly1 / poly2; // division
poly3 = poly1 % poly2; // modulus or remainder
poly3 = poly1 ^ 3; // exponentiation
poly3 = poly1 % 1; // poly1 mod (1x^1 + 0x^0)
poly3 = poly1 % 2; // poly1 mod (1x^2 + 0x^0)
poly3 = poly1 % n; // poly1 mod (1x^n + 0x^0)
poly1 <<= 1; // Shift left or multiply polynomial by 1x^1 + 0x^0
poly2 >>= 1; // Shift right or divide polynomial by 1x^1 + 0x^0
poly3 = poly1 << 2;
poly3 = poly2 >> 3;
poly3 = gcd(poly1,poly2); // Greatest common divisor
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();
}
