Finite field arithmetic
Encyclopedia
Arithmetic in a finite field
is different from standard integer 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 cardinality
) is necessarily of the form pn where p is a prime number
and n is a positive 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
in linear block codes such as BCH
and RS and in cryptography
algorithms such as the Rijndael encryption algorithm.
. GF(p), where p is a prime number, is simply the ring of integers modulo
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 the extended 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(pn) may be represented as polynomial
s of degree strictly less than n over GF(p). Operations are then performed modulo R where R is an irreducible polynomial
of degree n over GF(p), for instance using polynomial 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(pn) 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: x6 + x4 + x + 1
Binary: {01010011}
Hexadecimal: {53}
In a finite field with characteristic 2, addition modulo 2, subtraction modulo 2, and XOR are identical. Thus,
Polynomial: (x6 + x4 + x + 1) + (x7 + x6 + x3 + x) = x7 + x4 + x3 + 1
Binary: {01010011} + {11001010} = {10011001}
Hexadecimal: {53} + {CA} = {99}
Notice that under regular addition of polynomials, the sum would contain a term 2x6, but that this term becomes 0x6 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:
Note: In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2n) Galois fields, making these fields especially popular choices for applications.
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.
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 modulo x8 + x4 + x3 + 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. Notice that exclusive OR is applied in the example and not arithmetic subtraction, as one might use in grade-school long division.):
11111101111110 (mod) 100011011
^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". 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 three variable
s (in the computer programming sense), each holding an eight-bit representation. a and b 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, this invariant
is true: a b + p is the product. This is obviously true when the algorithm starts. When the algorithm terminates, a or b will be zero so p will contain the product.
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.
for an element a of a finite field can be calculated a number of different ways:
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(28) finite field with the reducing polynomial x8 + x4 + x3 + x + 1 is not primitive, although x + 1 is a generator in this field. The GF(28) finite field with the reducing primitive polynomial
x8 + x4 + x3 + x2 + 1, however, is a primitive field.
Primitive finite fields are used, for example, by Linear feedback shift register
s.
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)
p ^= a;
hi_bit_set = (a & 0x80);
a <<= 1;
if (hi_bit_set)
a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */
b >>= 1;
}
return p;
}
Addition: (A + B) mod Characteristic
Subtraction: (A - B) mod Characteristic
Multiplication: (A * B) mod Characteristic
Note that this code is vulnerable to timing attack
s when used for cryptography
.
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
is different from standard integer arithmetic
Arithmetic
Arithmetic or arithmetics is the oldest and most elementary branch of mathematics, used by almost everyone, for tasks ranging from simple day-to-day counting to advanced science and business calculations. It involves the study of quantity, especially as the result of combining numbers...
. 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 cardinality
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
) is necessarily of the form pn where p is a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
and n is a positive integer, and two finite fields of the same size are isomorphic
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
. The prime p is called the characteristic
Characteristic (algebra)
In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...
of the field, and the positive integer n is called the dimension
Dimension (vector space)
In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...
of the field over its prime field.
Finite fields are used in a variety of applications, including in classical coding theory
Coding theory
Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...
in linear block codes such as BCH
BCH code
In coding theory the BCH codes form a class of parameterised error-correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose and Ray-Chaudhuri...
and RS and in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
algorithms such as the Rijndael encryption algorithm.
Effective polynomial representation
The finite field with pn elements is denoted GF(pn) and is also called the Galois Field, in honor of the founder of finite field theory, Évariste GaloisÉvariste Galois
Évariste Galois was a French mathematician born in Bourg-la-Reine. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, thereby solving a long-standing problem...
. GF(p), where p is a prime number, is simply the ring of integers modulo
Modulo
In the mathematical community, the word modulo is often used informally. Generally, to say "A is the same as B modulo C" means, more-or-less, "A and B are the same except for differences accounted for or explained by C"....
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 the extended Euclidean algorithm
Extended Euclidean algorithm
The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
.
A particular case is GF(2), where addition is exclusive OR
XOR gate
The XOR gate is a digital logic gate that implements an exclusive or; that is, a true output results if one, and only one, of the inputs to the gate is true . If both inputs are false or both are true , a false output results. Its behavior is summarized in the truth table shown on the right...
(XOR) and multiplication is AND
AND gate
The AND gate is a basic digital logic gate that implements logical conjunction - it behaves according to the truth table to the right. A HIGH output results only if both the inputs to the AND gate are HIGH . If neither or only one input to the AND gate is HIGH, a LOW output results...
. Since the only invertible element is 1, division is the identity function
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...
.
Elements of GF(pn) may be represented as polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
s of degree strictly less than n over GF(p). Operations are then performed modulo R where R is an irreducible polynomial
Irreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
of degree n over GF(p), for instance using polynomial long division
Polynomial long division
In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalised version of the familiar arithmetic technique called 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(pn) as binary numbers
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
, 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
Binary
Hexadecimal
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 modulo 2, subtraction modulo 2, and XOR are identical. Thus,
Polynomial
Binary
Hexadecimal
Notice that under regular addition of polynomials, the sum would contain a term 2x6, but that this term becomes 0x6 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:
| p1 | p2 | p1 + p2 (normal algebra) | p1 + p2 in GF(2n) |
| x3 + x + 1 | x3 + x2 | 2x3 + x2 + x + 1 | x2 + x + 1 |
| x4 + x2 | x6 + x2 | x6 + x4 + 2x2 | x6 + x4 |
| x + 1 | x2 + 1 | x2 + x + 2 | x2 + x |
| x3 + x | x2 + 1 | x3 + x2 + x + 1 | x3 + x2 + x + 1 |
| x2 + x | x2 + x | 2x2 + 2x | 0 |
Note: In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2n) Galois fields, making these fields especially popular choices for applications.
Multiplication
Multiplication in a finite field is multiplication moduloModulo
In the mathematical community, the word modulo is often used informally. Generally, to say "A is the same as B modulo C" means, more-or-less, "A and B are the same except for differences accounted for or explained by C"....
an irreducible
Irreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
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(28). It employs the following reducing polynomial for multiplication:- x8 + x4 + x3 + 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 modulo x8 + x4 + x3 + x + 1 = (11111101111110 mod 100011011) = 1, which can be demonstrated through long division
Long division
In arithmetic, long division is a standard procedure suitable for dividing simple or complex multidigit numbers. It breaks down a division problem into a series of easier steps. As in all division problems, one number, called the dividend, is divided by another, called the divisor, producing a...
(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.):
11111101111110 (mod) 100011011
^100011011
1110000011110
^100011011
110110101110
^100011011
10101110110
^100011011
0100011010
^000000000
100011010
^100011011
00000001
(The elements {53} and {CA} happen to be multiplicative inverse
Multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
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". 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 three variable
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
s (in the computer programming sense), each holding an eight-bit representation. a and b 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, this invariant
Invariant (computer science)
In computer science, a predicate is called an invariant to a sequence of operations provided that: if the predicate is true before starting the sequence, then it is true at the end of the sequence.-Use:...
is true: a b + p is the product. This is obviously true when the algorithm starts. When the algorithm terminates, a or b will be zero so p will contain the product.
- Run the following loop eight times (once per bit). It is OK to stop when a or b are zero before an iteration:
- If the rightmost bit of b is set, exclusive OR the product p by the value of a. This is polynomial addition.
- Keep track of whether the leftmost bit of a is set to one
- Shift a one bit to the left, discarding the old leftmost bit, and making the new rightmost bit zero. This multiplies the polynomial by x, but we still need to take account of the old leftmost bit which represented the coefficient of x7.
- If a
' s leftmost bit had a value of one prior to this shift, exclusive or a with the hexadecimal number 0x1b (00011011 in binary). 0x1b corresponds to the irreducible polynomial with the high term eliminated. Conceptually, the high term of the irreducible polynomial and the former leftmost bit of a add modulo 2 to 0. - Shift b one bit to the right, discarding the rightmost bit, and making the leftmost bit have a value of zero. This divides the polynomial by x, discarding the x0 term.
- p now has the product
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 inverseMultiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
for an element a of a finite field can be calculated a number of different ways:
- By multiplying a by every number in the field until the product is one. This is a Brute-force searchBrute-force searchIn computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...
.
- For
one can take advantage of the analog of Fermat's little theorem, 
(for 
), thus the inverse of 
is 
- By using the Extended Euclidean algorithmExtended Euclidean algorithmThe extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
- By making a logarithmLogarithmThe logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
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 ("poly"nomial) x is a generatorGenerating set of a group
In abstract algebra, a generating set of a group is a subset that is not contained in any proper subgroup of the group. Equivalently, a generating set of a group is a subset such that every element of the group can be expressed as the combination of finitely many elements of the subset and their...
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(28) finite field with the reducing polynomial x8 + x4 + x3 + x + 1 is not primitive, although x + 1 is a generator in this field. The GF(28) finite field with the reducing primitive polynomial
Primitive polynomial
In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF...
x8 + x4 + x3 + x2 + 1, however, is a primitive field.
Primitive finite fields are used, for example, by Linear feedback shift register
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
s.
C Programming Example
Here is some CC (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
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)
p ^= a;
hi_bit_set = (a & 0x80);
a <<= 1;
if (hi_bit_set)
a ^= 0x1b; /* x^8 + x^4 + x^3 + x + 1 */
b >>= 1;
}
return p;
}
Arthimatic example (where the Characteristic is different than 2)
Addition: (A + B) mod Characteristic
Subtraction: (A - B) mod Characteristic
Multiplication: (A * B) mod Characteristic
Note that this code is vulnerable to timing attack
Timing attack
In cryptography, a timing attack is a side channel attack in which the attacker attempts to compromise a cryptosystem by analyzing the time taken to execute cryptographic algorithms...
s when used for cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.