Number Theory Primer

Notation

Some standard notation in number theory in crypto:

$N$ denotes a positive integer

$p$ dentoes a prime

$\mathbb{Z}_N = \{0,1,2,\dots ,N-1\}$ ie the set of integers 0 to $N-1$

We can do addition and multiplication mod $N$ in $\mathbb{Z}$ (it is a ring).

This is very common notation in crypto (even if not in other branches of maths).

So eg $9 + 8 = 5$ in $\mathbb{Z}_{12}$

Arithmetic in $\mathbb{Z}_N$ works as you expect (associativity, distributivity etc).

GCD

Greatest common divisor is the largest number that divides the two numbers.

Note that for all integers $x,y$ there exists integers $a,b$ such that = $a \cdot x + b \cdot y = gcd(x,y)$

For example: $gcd(12,18) = 6$ and $2 \times 12 - 1 \times 18 = 6$, so $a = 2, b = -1$.

a and b can be found efficiently using an extended version of Euclid’s agorithm.

If gcd(x,y) = 1 the numbers are relatively prime.

Modular Inversion

Over the rationals, inverse of 2 is just 1/2. What about $\mathbb{Z}_N$?

The inverse of $x \in \mathbb{Z}_N = y \in \mathbb{Z}_N$ such that $x \times y = 1 \mod N$.

We denote $y$ as $x^{-1}$.

So which elements have a modular inverse in $\mathbb{Z}_N$?

x has an inverse iff $gcd(x,N) = 1$

We can use extended Euclid to find the inverse, since $a \cdot x + b \cdot N = 1$ and $x^{-1} = a$ in $\mathbb{Z}_N$

Invertible elements:

We’ll define $\mathbb{Z}_N^*$ as the set of invertible elements in $\mathbb{Z}_N$

We can solve modular linear equations as follows:

Solve: $a \cdot x + b = 0$ in $\mathbb{Z}_N$

Solution: $x = -b \cdot a^{-1}$ in $\mathbb{Z}_N$

Fermat’s Theorem

Let $p$ be a prime, then:

\[\forall x \in \mathbb{Z}^*_p: x^{p-1} = 1 \mod \mathbb{Z}_p\]XS

EG: $p=5 \; 3^4 = 81 = 1 \mod \mathbb{Z}_5$

Euler proved a more general version of this.

This gives us another algorithm for finding an inverse of x mod a prime since:

$x \cdot x^{p-2} = 1$ therefore $x^{-1} = x^{p-2} \mod \mathbb{Z}_p$

This is slower than Euclid though, and only works with primes.

Generating random primes via Fermat

Suppose we want to generate a large random prime, say prime $p$ of length 1025 bits - $p \approx 2^{1024}$

Here’s a simple algorithm:

We choose a random integer $p \in [2^{1024}, 2^{1025} - 1]$
Test if $2^{p-1} = 1 \mod \mathbb{Z}_p$
If so output $p$ and stop, if not go back to step 1

This is not the best algorithm to do it though. It’s not guaranteed that the number is a prime (though extremely likely).

We do have better algorithms for this, and good verification algorithms. But this is a useful example.

Cyclic Groups

Euler showed that $\mathbb{Z}_p^*$ is a cyclic group that is:

\[ \exists g \in \mathbb{Z}_p^* \; s.t. \; \{1,g,g^2,g^3, \dots , g^{p-2} \} = \mathbb{Z}_p^*\]

$g$ is called a generator of \mathbb{Z}_p^*$

So the powers of $g$ give us $\mathbb{Z}_p^*$

EG: $p=7, g=3$

Not every element is a generator (eg 2 is not a generator of $\mathbb{Z}_7^*$

The group generated by g (denoted by $\lt g \gt$) is the set generated by a particular element of $\mathbb{Z}_p^*$

The order of $g \in \mathbb{Z}_p^*$ is the size of $\lt g \gt$.

This is equivalent to the smallest power $a$ such that $g^a = 1 \mod p$

Euler’s Generalization of Fermat

For an integer $N$ define $\phi (N) = | \mathbb{Z}_N^* |$

IE phi is the size of the set of co-primes with N.

So if N is prime, then $\phi (N) = N -1$

One thing to note (for RSA) if $N = p \cdot q$ where $p,q$ are prime (N is the product of two primes). Then:

$\phi (N) = N - p - q +1 = (p-1)(q-1)$

This is because there are $p$ elements divisible by $q$, and $q$ elements divisible by $p$ so we subtract those from $N$.

now we’ve subtracted 0 twice so we have to add one. This gives us the number of co-primes of N.

Euler went further and showed that:

\[\forall x \in \mathbb{Z}_N^*: x^{\phi (N)} = 1 \mod N\]

This is a generalization of Fermat’s theorem. Euler’s applies to composites, not just primes.

EG: $5^{\phi (12)} = 5^4 = 625 = 1 \mod 12$

This is the basis of the RSA cryptosystem.

Alex's Notes