Finite field arithmetic

Arithmetic in a finite field is different from standard arithmetic. All operations must always yield results that remain within the field. There are a limited number of numbers in the finite field; all of operations performed in the finite field result in a number within that field. Finite fields are used in a variety of applications, including cryptography, such as the Rijndael encryption algorithm.
While each finite field is itself not infinite, there are an infinite number of different finite fields.
Contents 
Notation
Although elements of a finite field can be expressed in numerical form (i.e., hexadecimal, binary, etc.), it is often found convenient to express them as polynomials, with each term in the polynomials representing the bits in the elements' binary expressions. For example, the following are equivalent representations of the same value of a characteristic 2 finite field:
 Hexadecimal: {53}
 Binary: {01010011}
 Polynomial: x^{6} + x^{4} + x + 1
The exponents in the polynomial notation serve as "tags", making it possible to keep track of each bit's value throughout arithmetical manipulation, without the need for zerovalue placeholders or alignment of digits into columns. If hexadecimal or binary notation is used, braces ( "{" and "}" ) or similar devices are commonly used to indicate that the value is an element of a field.
Addition and subtraction
Addition and subtraction are performed by adding or subtracting two of these polynomials together. Any term in a polynomial can only have a value zero or one.
In a finite field with characteristic 2, addition and subtraction are identical, and are accomplished using the XOR operator. Thus,
 Hexadecimal: {53} + {CA} = {99}
 Binary: {01010011} + {11001010} = {10011001}
 Polynomial: (x^{6} + x^{4} + x + 1) + (x^{7} + x^{6} + x^{3} + x) = x^{7} + x^{4} + x^{3} + 1
Notice that each of the numbers being added in the example have a x^{6} in them. x^{6} + x^{6} would be 2x^{6}. But, since each coefficient needs to be mod 2, this becomes 0x^{6}, and then gets dropped from the answer.
Here is a table with both the normal algebraic sum and the characteristic 2 finite field sum of a few polynomials:
p_{1}  p_{2}  p_{1} + p_{2} (normal algebra)  p_{1} + p_{2} in GF(2^{n}) 
x^{3} + x + 1  x^{3} + x^{2}  2x^{3} + x^{2} + x + 1  x^{2} + x + 1 
x^{4} + x^{2}  x^{6} + x^{2}  x^{6} + x^{4} + 2x^{2}  x^{6} + x^{4} 
x + 1  x^{2} + 1  x^{2} + x + 2  x^{2} + x 
x^{3} + x  x^{2} + 1  x^{3} + x^{2} + x + 1  x^{3} + x^{2} + x + 1 
Note that a characteristic 2 finite field is sometimes called a GF(2^{n}) Galois field.
Multiplication
Multiplication in a finite field is multiplication modulo the irreducible polynomial used to define the finite field. (I.e., it is multiplication followed by division using the irreducible polynomial as the divisor—the remainder is the product.) The symbol "•" may be used to denote multiplication in a finite field.
For example, if the irreducible polynomial used is f(x) = x^{8} + x^{4} + x^{3} + x + 1 (the irreducible polynomial used in Rijndael), then {53} • {CA} = {01} because
(x^{6} + x^{4} + x + 1)(x^{7} + x^{6} + x^{3} + x) =
x^{13} + x^{12} + x^{9} + x^{7}
+ x^{11} + x^{10} + x^{7} + x^{5}
+ x^{8} + x^{7} + x^{4} + x^{2}
+ x^{7} + x^{6} + x^{3} + x =
x^{13} + x^{12} + x^{9} + x^{11} + x^{10} + x^{5} + x^{8} + x^{4} + x^{2} + x^{6} + x^{3} + x =
x^{13} + x^{12} + x^{11} + x^{10} + x^{9} + x^{8} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x
and
x^{13} + x^{12} + x^{11} + x^{10} + x^{9} + x^{8} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x modulo x^{8} + x^{4} + x^{3} + x + 1 (= 11111101111110 mod 100011011) = 1, which can be demonstrated through long division (shown using binary notation, since it lends itself well to the task):
111101 100011011)11111101111110 100011011 1110000011110 100011011 110110101110 100011011 10101110110 100011011 0100011010 000000000 100011010 100011011 00000001
(The elements {53} and {CA} happen to be multiplicative inverses of one another since their product is 1.)
Multiplication in this particular finite field can also be done as follows:
 Take two eightbit numbers, a and b, and an eightbit product p. The reason for eight bits is because this finite field can only have eight elements in the polynomial.
 Set the product to zero.
 Make a copy of a and b, which we will simply call a and b in the rest of this algorithm
 Run the following loop eight times:
 If the low bit of b is set, exclusive or the product p by the value of a
 Keep track of whether the high (leftmost) bit of a is set to one
 Rotate a one bit to the left, discarding the high bit, and making the low bit have a value of zero
 If a's hi bit had a value of one prior to this rotation, exclusive or a with the hexadecimal number 0x1b (27 in decimal). 0x1b corresponds to the irreducible polynomial x^{8} + x^{4} + x^{3} + x + 1.
 Rotate b one bit to the right, discarding the low bit, and making the high (leftmost) bit have a value of zero.
 The product p now has the product of a and b
Multiplicative inverse
The multiplicative inverse for n in a finite field can be calculated a number of different ways:
 By multiplying n by every number in the field until the product is one. This is a Bruteforce search
 By using the Extended Euclidean algorithm
 By making a logarithm table of the finite field, and performing subtraction in the table. In a logarithm table, subtraction is the same as division.
Primitive finite fields
A finite field is considered a primitive finite field if the number 2 is a generator for the finite field. In other words, if repeated multiplications by 2 results in the entire finite field being traversed before the number has a value of one, the field is a primitive finite field. As it turns out, the GF(2^{8}) finite field with the reducing polynomial x^{8} + x^{4} + x^{3} + x + 1 is not a primitive; the smallest generator in this field is 3. The GF(2^{8}) finite field with the reducing primitive polynomial x^{8} + x^{4} + x^{3} + x^{2} + 1, however, is a primitive field.
Primitive finite fields are used, for example, by Linear feedback shift registers.
Program examples
Here is some C code which will add, subtract, and multiply numbers in a characteristic 2 (GF(2^{n})) finite field with eight terms and the irreducible polynomial f(x) = x^{8} + x^{4} + x^{3} + x + 1:
/* Add two numbers in a GF(2^8) finite field */ unsigned char gadd(unsigned char a, unsigned char b) { return a ^ b; } /* Subtract two numbers in a GF(2^8) finite field */ unsigned char gsub(unsigned char a, unsigned char b) { return a ^ b; } /* Multiply two numbers in the GF(2^8) finite field defined * by the polynomial x^8 + x^4 + x^3 + x + 1 */ unsigned char gmul(unsigned char a, unsigned char b) { unsigned char p = 0; unsigned char counter; unsigned char hi_bit_set; for(counter = 0; counter < 8; counter++) { if((b & 1) == 1) p ^= a; hi_bit_set = (a & 0x80); a <<= 1; if(hi_bit_set == 0x80) a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */ b >>= 1; } return p; }
Rijndael's finite field
Rijndael uses a characteristic 2 finite field with 8 terms, which can also be called a GF(2^{8}) Galois field. Rijndael's finite field uses the following reduction polynomial for multiplication:
x^{8} + x^{4} + x^{3} + x + 1.
External links
 A description of Rijndael's finite field (http://www.samiam.org/galois.html)