Motivation§

It’s useful to know about some algebraic structures and their properties, because cryptography is heavily dependent on them.

Groups§

Group

A group $G$ is a set $X$ equipped with a function,

$$ \ast : X \times X \rightarrow X $$

$$ \ast : (x, y) \rightarrowtail x \ast y, $$

that satisfies the following properties:

  1. $x \ast (y \ast z) = (x \ast y) \ast z$ (associativity)
  2. $\exists e\forall x, e \ast x = x \ast e = x$ (identity)
  3. $\forall x \exists y, x \ast y = y \ast x = e$ (inverse)

A simple example of a group would be $(\mathbb{Z})^{+}$, i.e. the set of integers $\mathbb{Z}$ with an addition function.

Abelian (Commutative) Group

A group with a function $\ast$ that exibits commutativity, i.e.

$$ \forall x \forall y, x \ast y = y \ast x. $$

The aforementioned group, $(\mathbb{Z})^{+}$ is also an example of an abelian group, i.e. the order in which you add integers does not matter.

Fields§

Field

A field is a set $X$ equipped with two group operations,

$$ \begin{array}{l c l} \ast : \left(X \setminus {0}\right) \times \left(X \setminus {0}\right) \rightarrow X \setminus {0} & \quad & + : X \times X \rightarrow X\\ \ast : (x, y) \rightarrowtail x \ast y && + : (x, y) \rightarrowtail x + y, \end{array} $$

that satisfy the following properties:

  1. $\forall x, x \ast 0 = 0$.
  2. $x \ast (y + z) = x \ast y + x \ast z$ (distributive).
  3. Both $\ast$ and $+$ are commutative group operations.

An example of a field would be the real numbers, $\mathbb{R}$, with addition and multiplication. When $p$ prime, $(\mathbb{Z}_p, +, \cdot)$ also forms a field, typically constructed as the quotient of a polynomial ring by an irreductible element.

A finite field of order 4 (a “prime power” as $2^2 = 4$), denoted as $\mathbb{F}_4$, can be constructed as $\mathbb{Z}_2[x]/\left(x^2 + x + 1\right)$. While a finite field of a prime order $p$, denoted as $\mathbb{F}_p$, can be constructed just by the integers modulo $p$, i.e. $\mathbb{Z}/p\mathbb{Z}$.

Note that we use $\mathbb{Z}_n$ and $\mathbb{Z}/n\mathbb{Z}$ interchangably in this course; while they exhibit the same algebraic properties (group isomorphism), they are not the same algebraic object.