# Maths for Cryptography

Following are the basic mathematical elements required for an understanding of cryptography.

## Primes and Coprimes

### Basics

If you don't know what a prime is you probably shouldn't be doing this course.

$\pi\left(x\right)$ is the number of primes less than or equal to x.

For $x \geq 17$ this can be approximated by $${x \over ln x} < \pi\left(x\right) < 1.25506 \cdot {x \over ln x}$$

### Coprimes

Integers $a, b$ are *coprime* or *relatively prime* if they have no common factors (nothing divides them both).

This is usually tested for using the Greatest Common Denominator algorithm (or *gcd*), where $coprime(a, b) \iff gcd(a, b) = 1$

#### Euler totient

$\phi\left(n\right)$ denotes how many natural numbers (positive integers) that are less than $n$ are coprime with $n$

$\phi\left(n\right)$ is known as the *Euler Totient function*

If we know the prime factors of $n$ then $\phi\left(n\right)$ can be calculated as $$\phi\left(n\right) = n\prod_{p} \left(1-{1\over p}\right)$$

where $p$ is a distinct prime factor of $n$

### Smoothness

An integer $n$ is said to be $B-smooth$ for some $B$ (e.g. 50-smooth) if all of its prime factors are less than or equal to $B$

Note this generally means that $B$ is the lowest such number for $n$, meaning it is $n$'s largest prime factor *but* this is not always the case.

If $B$ is much smaller than $n$ then we tend to say "$n$ is smooth".

#### Importance

There exist quick algorithms for factoring smooth numbers, even when they are large, so one must avoid using smooth numbers in techniques that rely upon prime factorisation for security.

## Modulo Arithmetic

The set $Z_n = \left\{0, ..., n-1\right\}$ contains the integers that can exist in a $mod\ n$ equation.

For example $Z_5 = \left\{0, 1, 2, 3, 4\right\}$

Each of the numbers $x$ in $Z_n$ can also be considered an equivalence class of all numbers that are congruent to $x$ ($mod\ n$).

### Multiplicative inverse

If $a$ is in $Z_n$ then the multiplicative inverse of $a\ mod\ n$ is a unique $x\in Z_n$ such that $ax \equiv 1\ (mod\ n)$

$x$ only exists if $a$ and $n$ are coprime ($gcd\left(a, b\right) = 1$)

$Z^*_n$ consists of all numbers in $Z_n$ that are coprime with $n$.

It is important to note here that this includes $1$.

$Z^*_n$ is closed under multiplication and, as should be obvious, contains $\phi\left(n\right)$ elements.

If $n$ is prime then $Z^*_n = Z_n\backslash0$

(so $Z^*_n$ contains all non-zero elements of $Z_n$)

### Fermat's Little Theorem

This can be stated in two ways:

- If $p$ is prime then $a^p \equiv a (mod\ n)$
- If $p$ is prime and $p$ is coprime with $a$ then $a^{p-1} \equiv 1 (mod\ n)$

This theorem can be used as a simple probabilistic primality test amongst other uses.

### Euler's Theorem

If $a$ and $n$ are coprime then $$a^{\phi\left(n\right)} \equiv 1\ (mod\ n)$$

This theorem can be used to reduce large powers when working $mod\ n$
$$ 5^{79}\ mod\ 6 = (5^2 \times 5^2)^{19} \times 5^3 $$

as $5^2 = 25 \equiv 1\ mod\ 6$, this is $$\left(1 \times 1\right)^{19} \times 5^3 = 125 \equiv 5\ (mod\ 6)$$

In general if $x \equiv y\ (mod\ n)$ then $a^x \equiv a^y\ (mod\ n)$ or if $x$ and $y$ are equivalent $mod\ n$ then so is a number to the power of each.

### Cyclic Groups

#### Order

For $a \in Z^*_n$ ($a$ is coprime with $n$ and $a < n$) the *order* of $a$
is that if you start with $t = 1$ and increment $t$ repeatedly, then the order of $a$ is the first value for $t$ for which $a^t \equiv 1\ (mod\ n)$

If this $a \geq 2$ and its order ($t$) is $\phi\left(n\right)$ then $Z^*_n$ is cyclic.
This means that when you were raising $a$ to the incrementing $t$ you will have touched every element in $Z^*_n$ before reaching $t$.

Or equivalently every element in $Z^*_n$ is reachable from every other
such element by simple exponentiation.

Such an $a$ is called a generator for $Z^*_n$ because one can create all
of $Z^*_n$ from it. Note that not all $b \in $Z^*_b$ will be generators.

It turns out $Z^*_n$ is cyclic iff $n$ is either $2$, $4$, a power of an
odd prime, or twice a power of an odd prime.

#### Discrete Logarithms

The discrete logarithm of $b$ with respect to $g$ (for some generator $g$)
is the $x$ such that $g^x \equiv b\ (mod\ n)$.

There is an efficient algorithm for computing discrete logarithms in $Z^*_p$
if $p-1$ is smooth. I'm not entirely sure on this because the slides are
ambiguous. They say "if $p-1$ has smooth factors" but factors are primes
and primes aren't smooth? I'm also assuming $p$ is prime, otherwise it
would be $n$.

Back to Computer Security