In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, finite field arithmetic is
arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
in a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
(a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
containing a finite number of
elements) contrary to arithmetic in a field with an infinite number of elements, like the field of
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s.
There are infinitely many different finite fields. Their
number of elements is necessarily of the form ''p
n'' where ''p'' is a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
and ''n'' is a
positive integer
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...
, and two finite fields of the same size are
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
. The prime ''p'' is called the
characteristic of the field, and the positive integer ''n'' is called the
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
of the field over its
prime field
In mathematics, the characteristic of a ring , often denoted , is defined to be the smallest number of times one must use the ring's multiplicative identity (1) in a sum to get the additive identity (0). If this sum never reaches the additive iden ...
.
Finite fields are used in a variety of applications, including in classical
coding theory
Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are stud ...
in
linear block code
In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks.
There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definit ...
s such as
BCH code
In coding theory, the Bose–Chaudhuri–Hocquenghem codes (BCH codes) form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called ''Galois field''). BCH codes were invented in 1959 ...
s and
Reed–Solomon error correction
Reed–Solomon codes are a group of error-correcting codes that were introduced by Irving S. Reed and Gustave Solomon in 1960.
They have many applications, the most prominent of which include consumer technologies such as MiniDiscs, CDs, DVDs, B ...
, in
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
algorithms such as the
Rijndael (
AES) encryption algorithm, in tournament scheduling, and in the
design of experiments
The design of experiments (DOE, DOX, or experimental design) is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. The term is generally associ ...
.
Effective polynomial representation
The finite field with ''p''
''n'' elements is denoted GF(''p''
''n'') and is also called the Galois field of order ''p''
''n'', in honor of the founder of finite field theory,
Évariste Galois
Évariste Galois (; ; 25 October 1811 – 31 May 1832) was a French mathematician and political activist. While still in his teens, he was able to determine a necessary and sufficient condition for a polynomial to be solvable by radicals, ...
. GF(''p''), where ''p'' is a prime number, is simply the
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
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), is reduced to 2 modulo 5. Division is multiplication by the inverse modulo ''p'', which may be computed using the
extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
.
A particular case is GF(2), where addition is
exclusive OR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
(XOR) and multiplication is
AND
or AND may refer to:
Logic, grammar, and computing
* Conjunction (grammar), connecting two words, phrases, or clauses
* Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition
* Bitwise AND, a boolea ...
. Since the only invertible element is 1, division is the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
.
Elements of GF(''p''
''n'') may be represented as
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s of degree strictly less than ''n'' over GF(''p''). Operations are then performed modulo ''R'' where ''R'' is an
irreducible polynomial
In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted ...
of degree ''n'' over GF(''p''), for instance using
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 generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, becaus ...
. The addition of two polynomials ''P'' and ''Q'' is done as usual; multiplication may be done as follows: compute as usual, then compute the remainder modulo ''R''. This representation in terms of polynomial coefficients is called a
monomial basis
In mathematics the monomial basis of a polynomial ring is its basis (as a vector space or free module over the field or ring of coefficients) that consists of all monomials. The monomials form a basis because every polynomial may be uniquely writt ...
(a.k.a. 'polynomial basis').
There are other representations of the elements of GF(''p''
''n''); some are isomorphic to the polynomial representation above and others look quite different (for instance, using matrices). Using a
normal basis In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any f ...
may have advantages in some contexts.
When the prime is 2, it is conventional to express elements of GF(''p''
''n'') as
binary numbers, with the coefficient of each term in a polynomial represented by one bit in the corresponding element's binary expression. Braces ( "" ) 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:
Primitive polynomials
There are many irreducible polynomials (sometimes called reducing polynomials) that can be used to generate a finite field, but they do not all give rise to the same representation of the field.
A
monic irreducible polynomial
In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted ...
of degree having coefficients in the finite field GF(), where for some prime and positive integer , is called a primitive polynomial if all of its roots are
primitive elements of GF(). In the polynomial representation of the finite field, this implies that is a primitive element. There is at least one irreducible polynomial for which is a primitive element. In other words, for a primitive polynomial, the powers of generate every nonzero value in the field.
In the following examples it is best not to use the polynomial representation, as the meaning of changes between the examples. The monic irreducible polynomial over
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...
is not primitive. Let be a root of this polynomial (in the polynomial representation this would be ), that is, . Now , so is not a primitive element of GF(2
8) and generates a multiplicative subgroup of order 51.
Consider the field element (in the polynomial representation this would be ). Now . As all the roots of this primitive polynomial are primitive elements, is a primitive element of GF(2
8) ( and no smaller power does). GF(2
8) has 128 generators (see
Number of primitive elements). Having as a generator for a finite field is beneficial for many computational mathematical operations.
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,
Under regular addition of polynomials, the sum would contain a term 2''x''
6. 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:
In computer science applications, the operations are simplified for finite fields of characteristic 2, also called GF(2
''n'')
Galois field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtra ...
s, making these fields especially popular choices for applications.
Multiplication
Multiplication in a finite field is multiplication
modulo an
irreducible
In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole.
Emergence ...
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 (AES) 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
8). It employs the following reducing polynomial for multiplication:
:''x''
8 + ''x''
4 + ''x''
3 + ''x'' + 1.
For example, • = in Rijndael's field because
:
and
:
The latter can be demonstrated through
long division
In arithmetic, long division is a standard division algorithm suitable for dividing multi-digit Hindu-Arabic numerals (Positional notation) that is simple enough to perform by hand. It breaks down a division problem into a series of easier steps ...
(shown using binary notation, since it lends itself well to the task. Notice that
exclusive OR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
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 and are
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 Multiplication, multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a rat ...
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 may refer to:
* Variable (computer science), a symbolic name associated with a value and whose associated value may be changed
* Variable (mathematics), a symbol that represents a quantity in a mathematical expression, as used in many ...
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 and invariance may refer to:
Computer science
* Invariant (computer science), an expression whose value doesn't change during program execution
** Loop invariant, a property of a program loop that is true before (and after) each iteratio ...
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 is 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.
*# 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 ''x''
0 term.
*# Keep track of whether the leftmost bit of a is set to one and call this value carry.
*# Shift a one bit to the left, discarding the leftmost bit, and making the new rightmost bit zero. This multiplies the polynomial by x, but we still need to take account of carry which represented the coefficient of ''x''
7.
*# If carry had a value of one, 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 carry 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 of a, b, and p and the value
0x1b
appropriately.
Multiplicative inverse
See also
Itoh–Tsujii inversion algorithm The Itoh–Tsujii inversion algorithm is used to invert elements in a finite field. It was introduced in 1988, first over GF(2''m'') using the normal basis representation of elements, however, the algorithm is generic and can be used for other bases ...
.
The
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 Multiplication, multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a rat ...
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 search
In computer science, brute-force search or exhaustive search, also known as generate and test, is a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the soluti ...
.
* Since the nonzero elements of GF(''p
n'') form a
finite group
Finite is the opposite of infinite. It may refer to:
* Finite number (disambiguation)
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked ...
with respect to multiplication, (for ), thus the inverse of ''a'' is ''a''.
* By using the
extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's ide ...
.
* By making
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 o ...
and
exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
tables for the finite field, subtracting the logarithm from ''p
n''−1 and exponentiating the result.
* By making a
modular multiplicative inverse In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer is an integer such that the product is congruent to 1 with respect to the modulus .. In the standard notation of modular arithmetic this congr ...
table for the finite field and doing a lookup.
* By mapping to a
composite 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 by ''a''.
Implementation tricks
Generator based tables
When developing algorithms for Galois field computation on small Galois fields, a common performance optimization approach is to find a
generator
Generator may refer to:
* Signal generator, electronic devices that generate repeating or non-repeating electronic signals
* Electric generator, a device that converts mechanical energy to electrical energy.
* Generator (circuit theory), an eleme ...
''g'' and use the identity:
:
to implement multiplication as a sequence of table look ups for the log
''g''(''a'') and ''g''
''y'' functions and an integer addition operation. This exploits the property that every finite field contains generators. In the Rijndael field example, the polynomial (or ) is one such generator. A necessary but not sufficient condition for a polynomial to be a generator is to be
irreducible
In philosophy, systems theory, science, and art, emergence occurs when an entity is observed to have properties its parts do not have on their own, properties or behaviors that emerge only when the parts interact in a wider whole.
Emergence ...
.
An implementation must test for the special case of ''a'' or ''b'' being zero, as the product will also be zero.
This same strategy can be used to determine the multiplicative inverse with the identity:
:
Here, the
order of the generator, , is the number of non-zero elements of the field. In the case of GF(2
8) this is . That is to say, for the Rijndael example: . So this can be performed with two look up tables and an integer subtract. Using this idea for exponentiation also derives benefit:
:
This requires two table look ups, an integer multiplication and an integer modulo operation. Again a test for the special case must be performed.
However, in cryptographic implementations, one has to be careful with such implementations since the
cache architecture of many microprocessors leads to variable timing for memory access. This can lead to implementations that are vulnerable to a
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. Every logical operation in a computer takes time to execute, and ...
.
Carryless multiply
For binary fields GF(2
''n''), field multiplication can be implemented using a carryless multiply such as
CLMUL instruction set Carry-less Multiplication (CLMUL) is an extension to the x86 instruction set used by microprocessors from Intel and AMD which was proposed by Intel in March 2008 and made available in the Intel Westmere processors announced in early 2010. Mathema ...
, which is good for ''n'' ≤ 64. A multiplication uses one carryless multiply to produce a product (up to 2''n'' − 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 the Barrett reduction step for fast computation of CRC using the
x86
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introd ...
pclmulqdq instruction.
Composite field
When ''k'' is a
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
, there will exist
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
s from a binary field GF(2
''k'') to an extension field of one of its subfields, that is, GF((2
''m'')
''n'') where . 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. To reduce gate count for hardware implementations, the process may involve multiple nesting, such as mapping from GF(2
8) to GF(((2
2)
2)
2). There is an implementation constraint, the operations in the two representations must be compatible, so explicit use of the isomorphism is needed. More precisely, the isomorphism will be denoted by map(), it is a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
that maps an element of GF(2
''k'') to GF((2
''m'')
''n''), satisfying: and , where the operations on the left side occur in GF(2
''k'') before mapping and the operations on the right side occur in GF((2
''m'')
''n'') after mapping.
/ref> The isomorphism is usually implemented with a ''k'' row by ''k'' bit matrix, used to perform a matrix multiply over GF(2) of an element of GF(2''k'') treated as a ''k'' row by 1 bit matrix. Define ''α'' as a primitive element of GF(2''k''), and ''β'' as a primitive element of GF((2''m'')''n''). Then ''β''''j'' = map(''α''''j'') and ''α''''j'' = map−1(''β''''j''). The values of ''α'' and ''β'' determine the mapping matrix and its inverse. Since the actual math is performed in GF((2''m'')''n''), the reducing polynomial for GF((2''m'')''n'') is usually primitive and ''β'' = ''x'' in GF((2''m'')''n''). In order to meet the compatibility constraint for addition and multiplication, a search is done to choose any primitive element ''α'' of GF(2''k'') that will meet the constraint. In the case where reducing polynomial for GF(2''k'') is primitive, an alternate mapping method is possible: the 1 bit coefficients of the reducing polynomial for GF(2''k'') are interpreted as ''m'' bit elements 0 or 1 of GF(2''m''), and there will be ''m'' primitive factors of degree ''n'', any of which can be used as the reducing polynomial for GF((2''m'')''n''). Mapping to a composite field can be generalized to map GF(''p''''k'') to a composite field such as GF((''p''''m'')''n''), for ''p'' any prime.
Program examples
C programming example
Here is some C (programming language), C code which will add and multiply numbers in the characteristic 2 finite field of order 28, used for example by Rijndael algorithm or Reed–Solomon, using the Russian peasant multiplication algorithm:
/* Add two numbers in the GF(2^8) finite field */
uint8_t gadd(uint8_t a, uint8_t 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_t gmul(uint8_t a, uint8_t b)
This example has cache, timing, and branch prediction side-channel leaks, and is not suitable for use in cryptography.
D programming example
This D program will multiply numbers in Rijndael's finite field and generate a PGM image:
/**
Multiply two numbers in the GF(2^8) finite field defined
by the polynomial x^8 + x^4 + x^3 + x + 1.
*/
ubyte gMul(ubyte a, ubyte b) pure nothrow
void main()
This example does not use any branches or table lookups in order to avoid side channels and is therefore suitable for use in cryptography.
See also
* Zech's logarithm
Zech logarithms are used to implement addition in finite fields when elements are represented as powers of a generator \alpha.
Zech logarithms are named after Julius Zech, and are also called Jacobi logarithms, after Carl G. J. Jacobi who used ...
References
Sources
* (reissued in 1984 by Cambridge University Press ).
*
External links
*
*
*
* {{cite web, url=http://web.eecs.utk.edu/~plank/plank/papers/CS-07-593/, title=Fast Galois Field Arithmetic Library in C/C++, first1=James S., last1=Planck, year=2007
* Wikiversity: Reed–Solomon for Coders – Finite Field Arithmetic
Arithmetic
Arithmetic
Arithmetic () is an elementary part of mathematics that consists of the study of the properties of the traditional operations on numbers— addition, subtraction, multiplication, division, exponentiation, and extraction of roots. In the 19th ...
Articles with example D code
Articles with example C code