- Finite field arithmetic
**Arithmetic in a**is different from standard integerfinite field arithmetic . There are a limited number of elements in the finite field; all operations performed in the finite field result in an element within that field.While each finite field is itself not infinite, there are infinitely many different finite fields; their number of elements (which is also called cardinal) is necessarily of the form "p"

^{"n"}where "p" is aprime number and "n" is apositive integer , and two finite fields of the same size are isomorphic. The prime "p" is called the characteristic of the field, and the positive integer "n" is called the dimension of the field over its prime field.Finite fields are used in a variety of applications, including in classical

coding theory inlinear block code s such as BCH and RS and incryptography algorithms such as theRijndael encryption algorithm.**Effective polynomial representation**The finite field with "p"

^{"n"}elements is denoted GF("p"^{"n"}) and is also called the**Galois Field**, in honor of the founder of finite field theory,Évariste Galois . GF("p"), where "p" is a prime number, is simply the ring of integersmodulo "p". That is, one can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulo "p". For instance, in GF(5), 4+3=7 is reduced to 2 modulo 5. Division is multiplication by the inverse modulo "p", which may be computed using theextended Euclidean algorithm .A particular case is GF(2), where addition is exclusive OR (XOR) and multiplication is AND. Since the only invertible element is 1, division is the

identity function .Elements of GF("p"

^{"n"}) may be represented aspolynomial s of degree strictly less than "n" over GF("p"). Operations are then performed modulo "R" where "R" is anirreducible polynomial of degree "n" over GF("p"), for instance usingpolynomial long division . The addition of two polynomials "P" and "Q" is done as usual; multiplication may be done as follows: compute "W" ="P"."Q" as usual, then compute the remainder modulo "R" (there exist better ways to do this).When the prime is 2, it is conventional to express elements of GF("p"

^{"n"}) as binary numbers, with each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "{" and "}" ) or similar delimiters are commonly added to binary numbers, or to their hexadecimal equivalents, to indicate that the value is an element of a field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:;Polynomial

: "x"^{6}+ "x"^{4}+ "x" + 1;Binary: {01010011};Hexadecimal: {53}**Addition and subtraction**Addition and subtraction are performed by adding or subtracting two of these polynomials together, and reducing the result modulo the characteristic.

In a finite field with characteristic 2, addition and subtraction are identical, and are accomplished using the

XOR operator. Thus,;Polynomial

: ("x"^{6}+ "x"^{4}+ "x" + 1) + ("x"^{7}+ "x"^{6}+ "x"^{3}+ "x") = "x"^{7}+ "x"^{4}+ "x"^{3}+ 1;Binary: {01010011} + {11001010} = {10011001};Hexadecimal: {53} + {CA} = {99}Notice that under regular addition of polynomials, the sum would contain a term 2"x"

^{6}, but that this term becomes 0"x"^{6}and is dropped when the answer is reduced modulo 2.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**(normal algebra)_{2}**p**+_{1}**p**in GF(2_{2}^{n})x ^{3}+ x + 1x ^{3}+ x^{2}2x ^{3}+ x^{2}+ x + 1x ^{2}+ x + 1x ^{4}+ x^{2}x ^{6}+ x^{2}x ^{6}+ x^{4}+ 2x^{2}x ^{6}+ x^{4}x + 1 x ^{2}+ 1x ^{2}+ x + 2x ^{2}+ xx ^{3}+ xx ^{2}+ 1x ^{3}+ x^{2}+ x + 1x ^{3}+ x^{2}+ x + 1x ^{2}+ xx ^{2}+ x2x ^{2}+ 2x0 Note: In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2

^{n})Galois field s, making these fields especially popular choices for applications.**Multiplication**Multiplication in a finite field is multiplication

modulo an irreducible reducing polynomial used to define the finite field. (I.e., it is multiplication followed by division using the reducing polynomial as the divisor—the remainder is the product.) The symbol "•" may be used to denote multiplication in a finite field.**Rijndael's finite field**Rijndael uses a characteristic 2 finite field with 8 terms, which can also be called the Galois field**GF**(2^{8}). It employs the following reducing polynomial for multiplication::"x"

^{8}+ "x"^{4}+ "x"^{3}+ "x" + 1.For example, {53} • {CA} = {01} in Rijndael's field because

("x"

^{6}+ "x"^{4}+ "x" + 1)("x"^{7}+ "x"^{6}+ "x"^{3}+ "x") ="x"

^{13}+ "x"^{12}+ "x"^{9}+**x**+ "x"^{7}^{11}+ "x"^{10}+**x**+ "x"^{7}^{5}+ "x"^{8}+**x**+ "x"^{7}^{4}+ "x"^{2}+**x**+ "x"^{7}^{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 throughlong division (shown using binary notation, since it lends itself well to the task. Notice that exclusive OR is applied in the example and not arithmetic subtraction, as one might use in grade-school long division.):__^100011011__1110000011110__^100011011__110110101110__^100011011__10101110110__^100011011__0100011010__^000000000__100011010__^100011011__00000001(The elements {53} and {CA} happen to be

multiplicative inverse s of one another since their product is 1.)Multiplication in this particular finite field can also be done using a modified version of the "peasant's algorithm":

* Take two eight-bit numbers,

**a**and**b**, and an eight-bit 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 high 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"^{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**This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths of

**a**,**b**, and**p**and the value`0x1b`appropriately.**Multiplicative inverse**The

multiplicative inverse for an element**n**of 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 aBrute-force search .* By using the

Extended Euclidean algorithm * By making a

logarithm table of the finite field, and performing subtraction in the table. Subtraction of logarithms is the same as division.**Primitive finite fields**A finite field is considered a primitive finite field if the element "x" is a generator for the finite field. In other words, if the powers of "x" assume every nonzero value in the field, it 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 primitive, although "x" + 1 is a generator in this field. The GF(2^{8}) finite field with the reducingprimitive 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 register s.**Program examples**Here is some C code which will add, subtract, and multiply numbers in Rijndael's finite field:

/* Add two numbers in a GF(2^8) finite field */uint8_t gadd(uint8_t a, uint8_t b) { return a ^ b;}/* Subtract two numbers in a GF(2^8) finite field */uint8_t gsub(uint8_t a, uint8_t 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 */uint8_t gmul(uint8_t a, uint8_t b) { uint8_t p = 0; uint8_t counter; uint8_t 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;}

Note that this code is vulnerable to

timing attack s when used forcryptography .**External links*** [

*http://www.samiam.org/galois.html A description of Rijndael's finite field*]

* [*http://www.partow.net/projects/galois/index.html Galois Field Arithmetic Library C++*]

*Wikimedia Foundation.
2010.*