全部博文(2005)
分类:
2010-02-09 20:50:43
Arithmetic in a is different from standard integer . 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 ) is necessarily of the form pn where p is a and n is a , and two finite fields of the same size are . The prime p is called the of the field, and the positive integer n is called the of the field over its .
Finite fields are used in a variety of applications, including in classical in such as and and in algorithms such as the encryption algorithm.
Contents[] |
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, . GF(p), where p is a prime number, is simply the of integers 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 .
A particular case is GF(2), where addition is (XOR) and multiplication is . Since the only invertible element is 1, division is the .
Elements of GF(pn) may be represented as of degree strictly less than n over GF(p). Operations are then performed modulo R where R is an of degree n over GF(p), for instance using . 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 , 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 + 1Binary: {01010011}Hexadecimal: {53}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 operator. Thus,
Polynomial: (x6 + x4 + x + 1) + (x7 + x6 + x3 + x) = x7 + x4 + x3 + 1Binary: {01010011} + {11001010} = {10011001}Hexadecimal: {53} + {CA} = {99}Notice that under regular addition of polynomials, the sum would contain a term 2x3, but that this term becomes 0x3 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) , making these fields especially popular choices for applications.
Multiplication in a finite field is multiplication an 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.
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 (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.):
(The elements {53} and {CA} happen to be of one another since their product is .)
Multiplication in this particular finite field can also be done using a modified version of the "". 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 (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 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.
The for an element a of a finite field can be calculated a number of different ways:
A finite field is considered a primitive finite field if the element x is a 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 x8 + x4 + x3 + x2 + 1, however, is a primitive field.
Primitive finite fields are used, for example, by .
Here is some code which will add, subtract, and multiply numbers in Rijndael's finite field:
/* Add two numbers in a GF(2^8) finite field */Note that this code is vulnerable to when used for .