Intermezzo: Algebraic Structures

17 Dec 2021

Notes Cryptography Intermezzo: Algebraic Structures

§ 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:

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

A simple example of a group would be $(\mathbb{Z})^{+}$ , where $\mathbb{Z}$ is the set of integers and $(\cdot)^{+}$ means that the set is equipped with addition.

Abelian (Commutative) Group

An abelian group is equipped with a group operation $\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.

Integers Modulo $n$

The structure we'll see most in this course are the integers modulo $n$ , written as

\mathbb{Z}/n\mathbb{Z}

This object represents every integer's remainder after division by $n$ .

My notes use $\mathbb{Z}_n$ and $\mathbb{Z}/n\mathbb{Z}$ interchangably; while they exhibit the same algebraic properties ( $\mathbb{Z}_n \simeq \mathbb{Z}/n\mathbb{Z}$ ), strictly speaking they are not the same algebraic object.

§ 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:

$\forall x, x \ast 0 = 0$ .
$x \ast (y + z) = x \ast y + x \ast z$ (distributive).
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.

Finite Field

A finite field (also known as a Galois field) is any field with a finite number of elements.

A finite field with order $p$ is denoted as

\mathbb{F}_p

Another common notation, especially if the text prefers to refer to a "Galois field",

\mathrm{GF}(p)

In this course we focus on those which have prime or "prime power" order.

Prime Power

Given a prime $p$ and $k \in \mathbb{N}$ , then the resulting number

m = p^k

is said to be a prime power.

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}$ .