高级算法 (Fall 2018)/Finite Field Basics

From EtoneWiki
Jump to: navigation, search

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 .