Шешікті өрісте арифметика

Arithmetic in a field with a finite number of elements
In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers. There are infinitely many different finite fields. Their number of elements 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 codes and Reed–Solomon error correction, in cryptography algorithms such as the Rijndael (AES) encryption algorithm, in tournament scheduling, and in the design of experiments.

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 of degree n having coefficients in the finite field GF(q), where 1=q = p^(t) for some prime p and positive integer t, is called a primitive polynomial if all of its roots are primitive elements of GF(q^(n)). In the polynomial representation of the finite field, this implies that x is a primitive element. There is at least one irreducible polynomial for which x is a primitive element. In other words, for a primitive polynomial, the powers of x generate every nonzero value in the field. In the following examples it is best not to use the polynomial representation, as the meaning of x changes between the examples. The monic irreducible polynomial x^(8) + x^(4) + x^(3) + x + 1 over GF(2) is not primitive. Let λ be a root of this polynomial (in the polynomial representation this would be x), that is, 1=λ^(8) + λ^(4) + λ^(3) + λ + 1 = 0. Now 1=λ^(51) = 1, so λ is not a primitive element of GF(28) and generates a multiplicative subgroup of order 51. The monic irreducible polynomial x^(8) + x^(4) + x^(3) + x^(2) + 1 over GF(2) is primitive, and all 8 roots are generators of GF(2^(8)). All GF(28) have a total of 128 generators (see Number of primitive elements), and for a primitive polynomial, 8 of them are roots of the reducing polynomial. Having x as a generator for a finite field is beneficial for many computational mathematical operations.

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.

For binary fields GF(2n), field multiplication can be implemented using a carryless multiply such as CLMUL instruction set, which is good for n ≤ 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 the Barrett reduction step for fast computation of CRC using the x86 pclmulqdq instruction.

When k is a composite number, there will exist isomorphisms from a binary field GF(2k) to an extension field of one of its subfields, that is, GF((2m)n) where 1=k = m n. 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(28) to GF(((22)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 that maps an element of GF(2k) to GF((2m)n), satisfying: 1=map(a + b) = map(a) + map(b) and 1=map(a b) = map(a) map(b), where the operations on the left side occur in GF(2k) before mapping and the operations on the right side occur in GF((2m)n) after mapping. 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(2k) treated as a k row by 1 bit matrix. Define α as a primitive element of GF(2k), and β as a primitive element of GF((2m)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((2m)n), the reducing polynomial for GF((2m)n) is usually primitive and β = x in GF((2m)n). In order to meet the compatibility constraint for addition and multiplication, a search is done to choose any primitive element α of GF(2k) that will meet the constraint. In the case where reducing polynomial for GF(2k) is primitive, an alternate mapping method is possible: the 1 bit coefficients of the reducing polynomial for GF(2k) are interpreted as m bit elements 0 or 1 of GF(2m), and there will be m primitive factors of degree n, any of which can be used as the reducing polynomial for GF((2m)n). Mapping to a composite field can be generalized to map GF(pk) to a composite field such as GF((pm)n), for p any prime.