高级算法 (Fall 2018)/Finite Field Basics
Field
Let be a set, closed under two binary operations (addition) and (multiplication). It gives us the following algebraic structures if the corresponding set of axioms are satisfied.
Structures | Axioms | Operations | ||||||
---|---|---|---|---|---|---|---|---|
field | commutative ring |
ring | abelian group |
group | monoid | semigroup | 1. Addition is associative: | |
2. Existence of additive identity 0: | ||||||||
3. Everyone has an additive inverse: | ||||||||
4. Addition is commutative: | ||||||||
5. Multiplication distributes over addition: and | ||||||||
6. Multiplication is associative: | ||||||||
7. Existence of multiplicative identity 1: | ||||||||
8. Multiplication is commutative: | ||||||||
9. Every non-zero element has a multiplicative inverse: |
The semigroup, monoid, group and abelian group are given by , and the ring, commutative ring, and field are given by .
Examples:
- Infinite fields: , , are fields. The integer set is a commutative ring but is not a field.
- Finite fields: Finite fields are called Galois fields. The number of elements of a finite field is called its order. A finite field of order , is usually denoted as or .
- Prime field : For any integer , under modulo- addition and multiplication forms a commutative ring. It is called quotient ring, and is sometimes denoted as . In particular, for prime , is a field. This can be verified by Fermat's little theorem.
- Boolean arithmetics : The finite field of order 2 contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication.
- Other examples: There are other examples of finite fields, for instance where . This field is isomorphic to . In fact, the following theorem holds for finite fields of given order.
Theorem - A finite field of order exists if and only if for some prime number and positive integer . Moreover, all fields of a given order are isomorphic.
Polynomial over a field
Given a field , the polynomial ring consists of all polynomials in the variable with coefficients in . Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms.
Proposition (polynomial ring) - is a ring.
The degree of a polynomial is the exponent on the leading term, the term with a nonzero coefficient that has the largest exponent.
Because is a ring, we cannot do division the way we do it in a field like , but we can do division the way we do it in a ring like , leaving a remainder. The equivalent of the integer division for is as follows.
Proposition (division for polynomials) - Given a polynomial and a nonzero polynomial in , there are unique polynomials and such that and .
The proof of this is by induction on , with the basis , in which case the theorem holds trivially by letting and .
As we turn (a ring) into a finite field by taking quotients , we can turn a polynomial ring into a finite field by taking modulo a "prime-like" polynomial, using the division of polynomials above.
Definition (irreducible polynomial) - An irreducible polynomial, or a prime polynomial, is a non-constant polynomial that cannot be factored as for any non-constant polynomials and .