Inmathematics,finite field arithmetic isarithmetic in afinite field (afield containing a finite number ofelements) contrary to arithmetic in a field with an infinite number of elements, like the field ofrational numbers.

There are infinitely many different finite fields. Theirnumber of elements is necessarily of the formpⁿ wherep is aprime number andn is apositive integer, and two finite fields of the same size areisomorphic. The primep is called thecharacteristic of the field, and the positive integern is called thedimension of the field over itsprime field.

Finite fields are used in a variety of applications, including in classicalcoding theory inlinear block codes such asBCH codes andReed–Solomon error correction, incryptography algorithms such as theRijndael (AES) encryption algorithm, in tournament scheduling, and in thedesign of experiments.

The finite field withpⁿ elements is denoted GF(pⁿ) and is also called theGalois field of orderpⁿ, in honor of the founder of finite field theory,Évariste Galois. GF(p), wherep is a prime number, is simply thering of integersmodulop. That is, one can perform operations (addition, subtraction, multiplication) using the usual operation on integers, followed by reduction modulop. For instance, in GF(5),4 + 3 = 7 is reduced to 2 modulo 5. Division is multiplication by the inverse modulop, which may be computed using theextended Euclidean algorithm.

A particular case isGF(2), where addition isexclusive OR (XOR) and multiplication isAND. Since the only invertible element is 1, division is theidentity function.

Elements of GF(pⁿ) may be represented aspolynomials of degree strictly less thann over GF(p). Operations are then performed modulom(x) wherem(x) is anirreducible polynomial of degreen over GF(p), for instance usingpolynomial long division. Addition is the usual addition of polynomials, but the coefficients are reduced modulop. Multiplication is also the usual multiplication of polynomials, but with coefficients multiplied modulop and polynomials multiplied modulo the polynomialm(x).^[1] This representation in terms of polynomial coefficients is called amonomial basis (a.k.a. 'polynomial basis').

There are other representations of the elements of GF(pⁿ); some are isomorphic to the polynomial representation above and others look quite different (for instance, using matrices). Using anormal basis may have advantages in some contexts.

When the prime is 2, it is conventional to express elements of GF(pⁿ) asbinary numbers, with the coefficient of 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 gives the coefficients of a basis of a field, thus representing an element of the field. For example, the following are equivalent representations of the same value in a characteristic 2 finite field:

There are many irreducible polynomials (sometimes calledreducing polynomials) that can be used to generate a finite field, but they do not all give rise to the same representation of the field.

Amonicirreducible polynomial of degreen having coefficients in the finite field GF(q), whereq =p^t for some primep and positive integert, is called aprimitive polynomial if all of its roots areprimitive elements of GF(qⁿ).^[2][3] In the polynomial representation of the finite field, this implies thatx is a primitive element. There is at least one irreducible polynomial for whichx is a primitive element.^[4] In other words, for a primitive polynomial, the powers ofx generate every nonzero value in the field.

In the following examples it is best not to use the polynomial representation, as the meaning ofx changes between the examples. The monic irreducible polynomialx⁸ +x⁴ +x³ +x + 1 overGF(2) is not primitive. Letλ be a root of this polynomial (in the polynomial representation this would bex), that is,λ⁸ +λ⁴ +λ³ +λ + 1 = 0. Nowλ⁵¹ = 1, soλ is not a primitive element of GF(2⁸) and generates a multiplicative subgroup of order 51.^[5] The monic irreducible polynomialx⁸ +x⁴ +x³ +x² + 1 overGF(2) is primitive, and all 8 roots are generators ofGF(2⁸).

All GF(2⁸) have a total of 128 generators (seeNumber of primitive elements), and for a primitive polynomial, 8 of them are roots of the reducing polynomial. Havingx as a generator for a finite field is beneficial for many computational mathematical operations.

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 modulo 2, subtraction modulo 2, and XOR are identical. Thus,

Under regular addition of polynomials, the sum would contain a term 2x⁶. This term becomes 0x⁶ 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:

In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2ⁿ)Galois fields, making these fields especially popular choices for applications.

Multiplication in a finite field is multiplicationmodulo anirreducible 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 (standardised as AES) uses the characteristic 2 finite field with 256 elements, which can also be called the Galois field GF(2⁸). It employs the following reducing polynomial for multiplication:

x⁸ +x⁴ +x³ +x + 1.

For example, {53} • {CA} = {01} in Rijndael's field because

	(x6 +x4 +x + 1)(x7 +x6 +x3 +x)
=	(x13 +x12 +x9 +x7) + (x11 +x10 +x7 +x5) + (x8 +x7 +x4 +x2) + (x7 +x6 +x3 +x)
=	x13 +x12 +x9 +x11 +x10 +x5 +x8 +x4 +x2 +x6 +x3 +x
=	x13 +x12 +x11 +x10 +x9 +x8 +x6 +x5 +x4 +x3 +x2 +x

and

	x13 +x12 +x11 +x10 +x9 +x8 +x6 +x5 +x4 +x3 +x2 +x modx8 +x4 +x3 +x1 + 1
=	(11111101111110 mod 100011011)
=	{3F7E mod 11B} = {01}
=	1 (decimal)

The latter can be demonstrated throughlong division (shown using binary notation, since it lends itself well to the task. Notice thatexclusive OR is applied in the example and not arithmetic subtraction, as one might use in grade-school long division.):

          11111101111110 (mod) 100011011^100011011          01110000011110          ^100011011           0110110101110^100011011            010101110110^100011011             00100011010^100011011               000000001

(The elements {53} and {CA} aremultiplicative inverses of one another since their product is1.)

Multiplication in this particular finite field can also be done using a modified version of the "peasant's algorithm". Each polynomial is represented using the same binary notation as above. Eight bits is sufficient because only degrees 0 to 7 are possible in the terms of each (reduced) polynomial.

This algorithm uses threevariables (in the computer programming sense), each holding an eight-bit representation.a andb are initialized with the multiplicands;p accumulates the product and must be initialized to 0.

At the start and end of the algorithm, and the start and end of each iteration, thisinvariant is true:ab +p is the product. This is obviously true when the algorithm starts. When the algorithm terminates,a orb will be zero sop will contain the product.

• Run the following loop eight times (once per bit). It is OK to stop whena orb is zero before an iteration:
  1. If the rightmost bit ofb is set, exclusive OR the productp by the value ofa. This is polynomial addition.
  2. Shiftb one bit to the right, discarding the rightmost bit, and making the leftmost bit have a value of zero. This divides the polynomial byx, discarding thex⁰ term.
  3. Keep track of whether the leftmost bit ofa is set to one and call this valuecarry.
  4. Shifta one bit to the left, discarding the leftmost bit, and making the new rightmost bit zero. This multiplies the polynomial byx, but we still need to take account ofcarry which represented the coefficient ofx⁷.
  5. Ifcarry had a value of one, exclusive ora with the hexadecimal number0x1b (00011011 in binary).0x1b corresponds to the irreducible polynomial with the high term eliminated. Conceptually, the high term of the irreducible polynomial andcarry add modulo 2 to 0.
• p now has the product

This algorithm generalizes easily to multiplication over other fields of characteristic 2, changing the lengths ofa,b, andp and the value0x1b appropriately.

Themultiplicative inverse for an elementa of a finite field can be calculated a number of different ways:

• By multiplyinga by every number in the field until the product is one. This is abrute-force search.
• Since the nonzero elements of GF(pⁿ) form afinite group with respect to multiplication,a^pn−1 = 1 (fora ≠ 0), thus the inverse ofa isa^pn−2. This algorithm is a generalization of themodular multiplicative inverse based onFermat's little theorem.
• Multiplicative inverse based on theFermat's little theorem can also be interpreted using the multiplicative Norm function infinite field. This new viewpoint leads to an inverse algorithm based on the additive Trace function infinite field.^[6]
• By using theextended Euclidean algorithm.
• By makinglogarithm andexponentiation tables for the finite field, subtracting the logarithm frompⁿ − 1 and exponentiating the result.
• By making amodular multiplicative inverse table for the finite field and doing a lookup.
• By mapping to acomposite field where inversion is simpler, and mapping back.
• By constructing a special integer (in case of a finite field of a prime order) or a special polynomial (in case of a finite field of a non-prime order) and dividing it bya.^[7]

When developing algorithms for Galois field computation on small Galois fields, a common performance optimization approach is to find ageneratorg and use the identity:

${\displaystyle ab=g^{{\log }_g(ab)}=g^{{\log }_g(a)+{\log }_g(b)}}$

to implement multiplication as a sequence of table look ups for the log_g(a) andg^y functions and an integer addition operation. This exploits the property that every finite field contains generators. In the Rijndael field example, the polynomialx + 1 (or {03}) is one such generator. A necessary but not sufficient condition for a polynomial to be a generator is to beirreducible.

An implementation must test for the special case ofa orb being zero, as the product will also be zero.

This same strategy can be used to determine the multiplicative inverse with the identity:

${\displaystyle a^{-1}=g^{{\log }_g\left(a^{-1}\right)}=g^{-{\log }_g(a)}=g^{|g|-{\log }_g(a)}}$

Here, theorder of the generator, |g|, is the number of non-zero elements of the field. In the case of GF(2⁸) this is2⁸ − 1 = 255. That is to say, for the Rijndael example:(x + 1)²⁵⁵ = 1. So this can be performed with two look up tables and an integer subtract. Using this idea for exponentiation also derives benefit:

${\displaystyle a^n=g^{{\log }_g\left(a^n\right)}=g^{n{\log }_g(a)}=g^{n{\log }_g(a)(\mathrm{mod}|g|)}}$

This requires two table look ups, an integer multiplication and an integer modulo operation. Again a test for the special casea = 0 must be performed.

However, in cryptographic implementations, one has to be careful with such implementations since thecache architecture of many microprocessors leads to variable timing for memory access. This can lead to implementations that are vulnerable to atiming attack.

For binary fields GF(2ⁿ), field multiplication can be implemented using a carryless multiply such asCLMUL instruction set, which is good forn ≤ 64. A multiplication uses one carryless multiply to produce a product (up to 2n − 1 bits), another carryless multiply of a pre-computed inverse of the field polynomial to produce a quotient = ⌊product / (field polynomial)⌋, a multiply of the quotient by the field polynomial, then an xor: result = product ⊕ ((field polynomial) ⌊product / (field polynomial)⌋). The last 3 steps (pclmulqdq, pclmulqdq, xor) are used in theBarrett reduction step for fast computation of CRC using thex86 pclmulqdq instruction.^[8]

Whenk is acomposite number, there will existisomorphisms from a binary field GF(2^k) to an extension field of one of its subfields, that is, GF((2^m)ⁿ) wherek =mn. Utilizing one of these isomorphisms can simplify the mathematical considerations as the degree of the extension is smaller with the trade off that the elements are now represented over a larger subfield.^[9] To reduce gate count for hardware implementations, the process may involve multiple nesting, such as mapping from GF(2⁸) to GF(((2²)²)²).^[10]

Here is someC code which will add and multiply numbers in the characteristic 2 finite field of order 2⁸, used for example by Rijndael algorithm or Reed–Solomon, using theRussian peasant multiplication algorithm:

/* Add two numbers in the GF(2^8) finite field */uint8_tgadd(uint8_ta,uint8_tb){returna^b;}/* Multiply two numbers in the GF(2^8) finite field defined * by the modulo polynomial relation x^8 + x^4 + x^3 + x + 1 = 0 * (the other way being to do carryless multiplication followed by a modular reduction) */uint8_tgmul(uint8_ta,uint8_tb){uint8_tp=0;/* accumulator for the product of the multiplication */while(a!=0&&b!=0){if(b&1)/* if the polynomial for b has a constant term, add the corresponding a to p */p^=a;/* addition in GF(2^m) is an XOR of the polynomial coefficients */if(a&0x80)/* GF modulo: if a has a nonzero term x^7, then must be reduced when it becomes x^8 */a=(a<<1)^0x11b;/* subtract (XOR) the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */elsea<<=1;/* equivalent to a*x */b>>=1;}returnp;}

This example hascache, timing, and branch prediction side-channel leaks, and is not suitable for use in cryptography.

ThisD program will multiply numbers in Rijndael's finite field and generate aPGM image:

/**Multiply two numbers in the GF(2^8) finite field definedby the polynomial x^8 + x^4 + x^3 + x + 1.*/ubytegMul(ubytea,ubyteb)purenothrow{ubytep=0;foreach(immutableubytecounter;0..8){p^=-(b&1)&a;automask=-((a>>7)&1);// 0b1_0001_1011 is x^8 + x^4 + x^3 + x + 1.a=cast(ubyte)((a<<1)^(0b1_0001_1011&mask));b>>=1;}returnp;}voidmain(){importstd.stdio,std.conv;enumwidth=ubyte.max+1,height=width;autof=File("rijndael_finite_field_multiplication.pgm","wb");f.writefln("P5\n%d %d\n255",width,height);foreach(immutabley;0..height)foreach(immutablex;0..width){immutablecharc=gMul(x.to!ubyte,y.to!ubyte);f.write(c);}}

This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.

• Zech's logarithm

• Lidl, Rudolf; Niederreiter, Harald (1983),Finite Fields, Addison-Wesley,ISBN 0-201-13519-1 (reissued in 1984 by Cambridge University PressISBN 0-521-30240-4).
• Mullen, Gary L.; Panario, Daniel (2013),Handbook of Finite Fields, CRC Press,ISBN 978-1-4398-7378-6
• Hankerson, Darrel; Vanstone, Scott; Menezes, Alfred (2004),Guide to Elliptic Curve Cryptography, Springer,ISBN 978-0-387-21846-5

• Gordon, G. (1976). "Very simple method to find the minimum polynomial of an arbitrary nonzero element of a finite field".Electronics Letters.12 (25):663–664.Bibcode:1976ElL....12..663G.doi:10.1049/el:19760508.
• da Rocha, V. C.; Markarian, G. (2006). "Simple method to find trace of arbitrary element of a finite field".Electronics Letters.42 (7):423–325.Bibcode:2006ElL....42..423D.doi:10.1049/el:20060473.
• Trenholme, Sam."AE's Galois field".
• Planck, James S. (2007)."Fast Galois Field Arithmetic Library in C/C++".
• Wikiversity: Reed–Solomon for Coders – Finite Field Arithmetic

• Arithmetic
• Finite fields

• CS1 maint: bot: original URL status unknown
• Articles with short description
• Short description matches Wikidata
• Articles with example D code
• Articles with example C code