03. Number Theory and Finite Fields

Discrete mathematics: cyroptology deals with finite objects (e.g. alphabets, blocks of characters)

Modular arithmetic; deals with finite number of values.

Basic Number Theory

Factorization

$\mathbb{Z} = \{ \dots, -3, -2, -1, 0, 1, 2, 3, \dots \}$ is the set of integers.

Given $a, b \in \mathbb{Z}$, $a$ divides $b$ if there exists $k \in \mathbb{Z}$ such that $ak = b$. In this case, $a$ is a factor of $b$: $a|b$.

An integer $p > 1$ is prime iff its only divisors are $1$ and $p$.

Properties

If $a|b$ and $a|c$, then $a|(b+c)$.

If $p$ is prime and $p|ab$, $p|a$ OR $p|b$.

Division algorithm

Given $a, b \in \mathbb{Z}$ such that $a > b$, then there exists $q, r \in \mathbb{Z}$ such that:

$q$ is the quotient and $0 \ge r \gt b$ is the remainder. $r \lt \frac{a}{2}$.

Greatest Common Divisor

$d$ is the GCD of $a$ and $b$; $gcd(a, b) = d$ if:

• $d|a$ and $|b$
• If $c|a$ and $c|b$, then $c|d$
• $d \gt 0$

$a$ and $b$ are relatively prime if $gcd(a, b) = 1$

Euclidean Algorithm

To find $d = gcd(a, b)$:

Hence, $d = r_k = gcd(a, b)$.

In psuedo-code:

def gcd(a, b):
  r[-1] = a
  r[0] = b
  k = 0
  while r[k] != 0:
    q[k] = floor(r[k - 1]/r[k])
    r[r + 1] = r[k - 1] - q[k]r[k]
    k = k + 1
  
  k = k - 1
  return r[k]

Back-Substitution

Find $x$, $y$ in $ax + by = d = r_k$.

Can be rewritten as:

$r_{k - 2} = r_{k - 1}q_k + r_k$ can be rewritten as $r_k = r_{k - 2} - r_{k - 1}q_k$. $r_{k - 1}$ can be substituted with the value above. Hence, this process can be repeated until you have $r_{k - 1}$ in terms of the original values.

Example: $gcd(17, 3)$:

Back-substitution:

The result shows that $3^{-1} \equiv 6 \pmod{17}$.

Modular Arithmetic

$b$ is a residue of $a \pmod n$ if $a - b = kn$ for some integer $k$:

Given $a \equiv b \pmod n$ and $c \equiv d \pmod n$:

$b \pmod n$ denotes the unique value $a$ in the complete set of residues $\{ 0, 1, \dots, n-1\}$ such that:

In other words, $b \pmod n$ is the remainder after dividing $a$ by $n$.

Residue Class

The set $\{ r_0, r_1, \dots, r_{n - 1}\}$ is a complete set of residues modulo $n$ if for every $a \in \mathbb{N}$, $a \equiv r_i \pmod n$ for exactly one $r_i$.

The set $\{ 0, 1, \dots, n - 1\}$ is denoted as $\mathbb{Z}_n$.

Groups

A group $\mathbb{G}$ is a set with binary operation $\cdot$ and:

• Closure: $a \cdot b \in \mathbb{G}$ for any and all $a, b \in \mathbb{G}$
• Identity: there is an element $1$ such that $a \cdot 1 = 1 \cdot a = a$ for any and all $a \in \mathbb{G}$
• Inverse: there is an element $b$ such that $a \cdot b = 1$ for any and all $a \in \mathbb{G}$
• Associativity: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for any and all $a, b, c \in \mathbb{G}$

A group is abelian when it is the operation is commutative; $a \cdot b = b\cdot a$ for $a, b \in \mathbb{G}$.

Cyclic Groups

The order $|\mathbb{G}|$ of a group $\mathbb{G}$ is the number of elements in $\mathbb{G}$.

$g^k$ denotes the repeated application of $g \in \mathbb{G}$ using the group operation. e.g. $g^3 = g \cdot g \cdot g$.

The order $|g|$ of $g \in \mathbb{G}$ is the smallest integer $k$ such that $g^k = 1$.

$g$ is a generator for $\mathbb{G}$ if $|g| = |\mathbb{G}|$.

A group is cyclic if it has a generator.

Computing Inverses Modulo $n$

The inverse if $a$ (if it exists) is a value $x$ such that $ax \equiv 1 \pmod n$; it is written as $a^{-1} \pmod n$. This means that $a$ must be coprime to $n$.

Theorem: let $0 \gt a \gt n$; $a$ has an inverse modulo $n$ iff $gcd(a, n) = 1$.

The Euclidean algorithm can be used to find the inverse of $a$.

If $x$ such that $ax \equiv 1 \pmod n$, there is an integer $y$ such that $ax = 1 + yn$.

Hence, starting from $gcd(a, n) = 1$, use back substitution to find $x$ and $y$ in the equation $ax + ny = 1$. the $y$ value gives the inverse.

Group of Primes Modulus $\mathbb{Z}^*_p$

$\mathbb{Z}^*_p = {1, 2, \dots, p - 1}$ is a complete set of residues modulo the prime $p$ with the value $0$ removed.

Properties:

• $|\mathbb{Z}^*_p| = p - 1$
• $\mathbb{Z}^*_p$ is cyclic
• $\mathbb{Z}^*_p$ has many generators (in general)

It can be thought of as the multiplicative group of integers $1, 2, \dots, p - 1$ which have inverses modulo $p$.

Finding Generators

A generator of $\mathbb{Z}^*_p$ is an element of order $p - 1$

Lagrange theorem: the order of any element must exactly divide $p - 1$.

To find a generator of $\mathbb{Z}^*_p$:

• Compute all distinct prime factors $f_1, f_2, \dots, f_r$ of $p - 1$
• $g$ is a generator iff $g^\frac{p - 1}{f_i} \neq 1 \pmod p$ for all $i = 1, 2, \dots, r$

Example

Find a generator for $\mathbb{Z}_{11}^*$.

$|\mathbb{Z}_{11}^*|$ is $10$ as $11$ is prime. $10 = 2 \cdot 5$, so to check if $g \in \mathbb{Z}_{11}^*$ is a generator, check if $g^2 \not\equiv 1 \pmod{11}$, $g^5 \not\equiv 1 \pmod{11}$:

• $1$: not a generator as $1^n \equiv 1 \pmod{11}$
• $2$: $2^5 \equiv 32 \equiv 2 \not\equiv 1 \pmod{11}$ and $2^2 \equiv 4 \not\equiv 1 \pmod{11}$ so $2$ is a generator

Groups of Composite Modulus $\mathbb{Z}^*_p$

For any non-prime $n$, $\mathbb{Z}_n^*$ is a group of residues that have an inverse under multiplication.

Properties:

• $\mathbb{Z}_n^*$ is a group
• $\mathbb{Z}_n^*$ is not cyclic in general
• Finding its order is difficult

e.g. $\mathbb{Z}_6^* = \{1, 5\}$ (elements coprime to $6$).

Example

Find a generator for $\mathbb{Z}_9^*$.

$\mathbb{Z}_9^* = \{ 1, 2, 4, 5, 7, 8, \}$ so $|\mathbb{Z}_9^*| = 6$

• $1$: not a generator as $1^n \equiv 1 \pmod 9$
• $2$:
  • $2^2 \equiv 4 \pmod 9$
  • $2^3 \equiv 8 \pmod 9$
  • $2^4 \equiv 16 \equiv 7 \pmod 9$
  • $2^5 \equiv 32 \equiv 5 \pmod 9$
  • $2^6 \equiv 64 \equiv 1 \pmod 9$
  • $2^7 \equiv 128 \equiv 2 \pmod 9$
  • Hence, the order of $2$ is equal to $|\mathbb{Z}_9^*|$, cycling through all elements in the group before repeating
  • NB: every element is guaranteed to be in $\mathbb{Z}_9^*$ as it is a group and hence has closure over the multiplication operation

Fields

A field $\mathbb{F}$ is a set with two binary operations, $+$ and $\cdot$, with the properties such that:

• $\mathbb{F}$ is an abelian group under the operation $+$ with the identity element $0$
• $\mathbb{F} \backslash \{ 0 \}$ is an abelian group under the operation $\cdot$ with identity element $1$
• Distributivity: $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ for $a, b, c \in \mathbb{F}$

Theorem: only finite fields of size $p^n$ exist, where $p$ is a prime and $n$ is any positive integer.

Finite Field $GF(p)$

For a finite field $GF(p) = \mathbb{Z}_p$:

• Multiplication and addition are done modulo $p$
• Its multiplicative group is exactly $\mathbb{Z}_p^*$

Finite Field $GF(2)$

$GF(2)$ is the simplest field with two elements, $0$ and $1$:

• Addition modulo $2$: XOR ($\oplus$)
• Multiplicative group: $\{ 1 \}$

Finite Field $GF(2^8)$

$GF(2^8)$ is the field used for calculations in AES (block cipher).

Arithmetic in this field is considered as polynomial arithmetic where the field elements are polynomials with binary coefficients. e.g. $0010 1101 \leftrightarrow x^5 + x^3 + x^2 + 1$

Properties:

• Polynomial division can be done easily using shift registers
• Adding two strings: add their coefficients modulo $2$ (XOR)
• Multiplication with respect to a generator polynomial
  • AES uses $m(x) = x^8 + x^4 + x^3 + x + 1$
• Multiplying two strings: multiply them as polynomials, then take remainder of division by $m(x)$