Fields

• Definition Field
• Example
• Finite Fields and Their Efficient Implementations

In many applications, a particular kind of integral domain called a $field$ is necessary.

Definition Field

Field.A commutative division ring is called a $field$. That is, a set $\mathbb{A}$ with operations called addition "+" and multiplication "$\cdot$" which satisfy the following axioms:

• $(\mathbb{A},+)$ is an abelian group.
• $(\mathbb{A}\backslash \{0\},\cdot )$ is an abelian group.
• Multiplication is distributive over addition.

Example

• $\mathbb{Q},\mathbb{R},\mathbb{C}$ are all fields;
• if $p$ is a prime number, $Z_p$ is a field, usually denote this field by ${\mathbb{F}}_p$;
  • ${\mathbb{F}}_p$ is a $finitefield$. The elements of ${\mathbb{F}}_p$ are the set of natural numbers $\{0,1,2,3,4,...,p-1\}$. The $order$ of the set is $p$. That is, the number of elements in this set is $p$.
  • The identity for addition "+" is 0
  • The identity for multiplication "$\cdot$" is 1
  • Add$(x,y)$ = $(x+y)(\mathrm{mod}p)$
  • Sub$(x,y)$ = $(x-y)(\mathrm{mod}p)$
  • Mul$(x,y)$ = $(x\cdot y)(\mathrm{mod}p)$
  • Div$(x,y)$ = $(x\cdot y^{-1})=(x\cdot y^{p-2})(\mathrm{mod}p)$
• 2 is a prime nummber, so ${\mathbb{F}}_2$ is a field whose elements are $\{0,1\}$.
  • $0+0=0$
  • $0+1=1+0=1$
  • $1+1=0$
  • $0\ast 0=0$
  • $0\ast 1=1\ast 0=0$
  • $1\ast 1=1$
  • You'll find that addition is equivalent to XOR, and multiplication is equivalent to AND.
• 7 is a prime number, so there is a field whose elements are $\{0,1,2,3,4,5,6\}$.
  • $\frac{1}{2}=1\cdot 2^{7-2}(\mathrm{mod}7)=2^5(\mathrm{mod}7)=32(\mathrm{mod}7)=4$
• let q = 21888242871839275222246405745257275088696311157297823662689037894645226208583, q is a prime number, so there is a field whose elements are $\{0,1,2,...,21888242871839275222246405745257275088696311157297823662689037894645226208582\}$.

Finite Fields and Their Efficient Implementations

The efficient implementation of finite fields can be referenced at: http://cacr.uwaterloo.ca/hac/about/chap14.pdf.