Number Theory

Number theory is a branch of pure maths which is dedicated to the study of the integers and arithmetic functions, according to the Wikipedia definition. It encompasses computational complexity, and modular arithmetic, which are used in cryptographic applications.

Computational Complexity Theory

This is a branch of theory of computation, where we classify computational problems by their difficulty. A computational problem is a task that can be solved by a computer automatically, by the application of mathematical steps in an algorithm.

Big-O Notation

This is used to classify algorithms by how their runtime or size requirements change with the input size. This is useful when we analyze algorithms, as we can get an upper bound for the runtime.

For example, take the function $T(n) = n^2 + n + 2$. It has a big-O notation of $O(n^2)$ as the largest term in the equation is of the order $n^2$. We also have $\Omega$ and $o$ to define average case and worst case scenarios with tighter bounds, respectively.

Complexity of Common Problems

When choosing an algorithm to solve a problem, we often consider their complexities. For example, a naïve implementation of adding two $n$ digit numbers together could be in the order of $n$, as each digit would have to be added to the other digit, then a carry bit set, then repeated with the next digit up in the chain.

Some horrible pseudocode:

num1 = 123456789
num2 = 987654321

add num1 num2:
  i = iterate length of longest:
    result = num1[end-i] + num2[end-i]
    if result >= 10:
      carry = 1
    else:
      carry = 0
    output = num1[end-i]

Of course, in hardware, this has been parallelized on die, and we can now natively add and multiply 64-bit numbers in $O(1)$ time. The same can be said for multiplication, but if we consider this as a naïve problem, then it would be $O(n^2)$, as each integer has to multiply every other integer in the other number, then we have to add all these together.

For an $n$-letter transposition cipher, a brute force search would require a search on each of the permutations possible, which would be $n!$.

For an $n$ letter shift, again by brute force, if we assume that the alphabet is 26 characters, then we require 25 possible shifts. The number of letters shifted is not dependant on the length of the message, so we can go through all 25 possible shifts in constant time, and see which is best.

Modular Arithmetic

Unlike normal arithmetic, which works on a system that is infinite on a number line, modular arithmetic works in a wrap around fashion, where at a specific value (the modulus) the system wraps around. Modular arithmetic is mathematically distinct from modules, which is a mathematical concept surrounding vector spaces.

In normal arithmetic, we have the sets $\mathbb{Z,Q,R,C}$, where $\mathbb{Z} = \{0, \pm 1, \pm 2, \dots\}$ (integers), $\mathbb{Q} = a/b | (a,b \in \mathbb{Z}, b \ne 0)$ (rational numbers), $\mathbb{R}$ (reals), and $\mathbb{C} = a+bj | (a,b \in \mathbb{R})$ (complex).

In modular arithmetic, we append a subscript integer to $\mathbb{Z}$, such as $\mathbb{Z}_{12}$, which contains the elements $\{0,1,2,3,4,5,6,7,8,9,10,11\}$.

We can then represent any number $a$ as some number $b \mod n$, where $n$ is the modulus and $b$ is a number within that module. We can also represent any $a = b + kn$, where $k$ is any integer.

For example, we can represent $13$ as $1 \mod 12 = 1 + 1 \times 12$, and similarly $26$ as $2 \mod 12 = 2 + 2 \times 12$.

The Mod Congruence

The definition of this is let $a_1, a_2$ be integers and $b$ a positive integer. $a_1$ is congruent to $a_2 \mod b$, or $a_1 \equiv a_2 \mod b$ if $(a_1 - a_2)$ is a multiple of $b$. Sometimes this congruence is given in terms of $a, b$ and $m$, where $m$ is the modulus.

This property allows us to manipulate expressions which involve the $\textrm{mod}$ function. We can then view modular arithmetic with reference to a fixed base, creating a number system where we can carry out all the calculations.

Example: Congruence of $113$ in $\mathbb{Z}_{24}$

To get $113 \mod 24$, we divide 113 by 24, to get the quotient and the remainder. This remainder is usually given as the fractional part of the answer, so we then multiply it by 24, giving $113 = 17$ in $\mathbb{Z}_{24}$.

The underlying maths is actually quite simple, it's just that we're wrapping it in theory seemingly for the sake of theory here. It's also useful to know how to do the computation without the modulus function available to us, especially considering we will likely be asked to compute some modulus in the exam, and the calculators required by the university do not have a native modulus function.

Mathematical Properties of Modular Arithmetic

Addition in $\mathbb{Z}_n$

Take, for example, $100 + 30$ in $\mathbb{Z}_{24}$. We calculate this as normal, e.g., $100+30 = 130$, then take the modulus of this (normally), or divide through by $24$, then take the fractional part of the answer and multiply that by $24$.

This gives $100 + 30 = 10$ in $\mathbb{Z}_{24}$. We can use the mod congruence to see that $130 = 10 + 5 \times 24$.

Multiplication in $\mathbb{Z}_n$

Multiplication is similar to addition, and we simply multiply the values together, then divide through by the modulus, to obtain the quotient and remainder (as a fraction), which we can then multiply through by the modulus to get the value in the module. Take, for example, $392 \times 514$ in $\mathbb{Z}_{1024}$. We multiply through normally, yielding $392 \times 514 = 201488$, which we can then divide by $1024$: $201488 \div 1024 = 196.765625 = 196 \frac{49}{64}$. We can then multiply the $\frac{49}{64} \times 1024 = 784$ in $\mathbb{Z}_{1024}$.

Modular Inversion

When we consider the rationals $\mathbb{R}$, the inverse of $2$ is $\frac{1}{2}$. In $\mathbb{Z}_n$, this is another element in $\mathbb{Z}_n$, such that the inverse of $x$ in $\mathbb{Z}_n$ is $y$, such that $xy=1$, denoted $x^{-1}$. This is called the multiplicative inverse.

For $x=3$ in $\mathbb{Z}_7$, the multiplicative inverse of this would be an integer such that $3y = 1 \mod 7$. In this instance $y$ could equal $5$, as $3 \times 5 = 15 = 1 \mod 7$. Also $0 \le y \le 6$.

Division in $\mathbb{Z}_n$

Division is slightly harder to do in modular arithmetic. For example, $\frac{2}{3}$ in $\mathbb{Z}_7$ would be $\frac{2}{3} = 2 \times \frac{1}{3} = 2 \times 5$ (by multiplicative inverse) $= 10 = 3$ in $\mathbb{Z}_7$.

It would be good to know if all elements have an inverse in $\mathbb{Z}_n$. We can use a lemma that for all integers $x,y$, there exist integers $a,b$ such that $ax + by = \gcd(x,y)$.

The theorem for this is that $x$ in $\mathbb{Z}_n$ has an inverse if and only if $\gcd(x,N) = 1$.

Example: Compute $10 \div 8$ in $\mathbb{Z}_{11}$

We split this into constituent components:

\[ \begin{align} \frac{10}{8} \text{ in } \mathbb{Z}_{11} &= 10 \times \frac{1}{8}\\ &= 10 \times \text{ multiplicative inverse of } \frac{1}{8}\\ \text{ multiplicative inverse of } 1/8:\\ 8y &= 1 \mod 11\\ 8(7) &= 56 = 1 \mod 11\\ \frac{10}{8} \text{ in } \mathbb{Z}_{11} &= 10 \times 7\\ &= 70\\ &= 4 \text{ in } \mathbb{Z}_{11} \end{align} \]

Euclid's Algorithm

This is an algorithm to generate the greatest common divisor of two numbers efficiently. The algorithm is based on the observation that

\[ \gcd(r_0,r_1) = \gcd(r_0-r_1, r_1) \]

where we have $r_0,r_1$ are positive integers and $r_0 > r_1$. For example, take $\gcd(77,44) = 11$, this gives:

\[ \begin{align} &= \gcd((77-44),44) = \gcd(33,44) = \gcd(44,33)\\ &= \gcd((44-33),33) = \gcd(11,33) = \gcd(33,11)\\ &= \gcd((33-11),11) = \gcd(22,11)\\ &= \gcd((22-11),11) = \gcd(11,11)\\ &= 11 \end{align} \]

Using this observation, we can obtain a lemma for the GCD as:

\[ \gcd(r_0,r_1) = \gcd(r_1, r_0 \mod r_1) \]

This can be applied iteratively to find the GCD for large numbers, as

\[ \begin{align} \gcd(r_0,r_1) &= \gcd(r_0-r_1,r_1)\\ &= \gcd(r_0-2r_1,r_1)\\ &= \gcd(r_0-mr_1,r_1) \end{align} \]

given that $r_0 - mr_1 > 0$. Within modular arithmetic, this value of $m$ can be determined easily, as $r_0 - mr_1 = r_0 \mod r_1$, so instead of doing the usual swapping of terms in the GCD, we can simply take $\gcd(r_0,r_1) = \gcd(r_0\mod r_1, r_1)$, swapping $r_0$ and $r_1$ when $r_0 \mod r_1 < r_1$.

Example: Calculate $\gcd(60,22)$

First, we take $60 \mod 22 = 16$. We can then put this into the equation for $\gcd(60, 22) = \gcd(22,16)$.

We can then apply the GCD equation again, with $\gcd(22,16) = \gcd(16,22\mod 16)$. This yields:

\[ \begin{align} \gcd(60,22) &= \gcd(22, 60 \mod 22) &&= \gcd(22,16)\\ &= \gcd(16, 22 \mod 16) &&= \gcd(16,6) \\ &= \gcd(6,16\mod6) &&= \gcd(6,4)\\ &= \gcd(4, 6 \mod 4) &&= \gcd(4,2)\\ &= \gcd(2, 4\mod2) &&= \gcd(2,0)\\ &= 2 \end{align} \]

Modular Inversion Using Euclidean Algorithm

Needs Expansion

This section still confuses me, and probably needs rewriting.

Tip

The way this is done in the lectures is quite confusing, there is a good resource here, which shows how to do the multiplicative inverse in a much clearer way.

In $\mathbb{Z}_n$, we can check if there is an inverse by checking if $\gcd(x,n) = 1$. To do this, we need to find $a,b$ such that $ax + bN = 1$. This can be done with the extended Euclidean Algorithm. Following this, we can see that $a$ is the inverse of $x$ in $\mathbb{Z}_n$.

To find the multiplicative inverse of $8 \mod 11$, where $x=8,N=11$, we can perform the Euclidean algorithm to verify that the $\gcd$ is indeed $1$, as is the requirement for a multiplicative inverse to exist. We can organise our work in terms of $8 \mod 11 \to 11 = 8(1) + 3$ (by the earlier property $a= b+kn$), which gives us the quotient ($8$) and the remainder ($3$).

\[ \begin{align} 11 &= 8(1) + 3 & 3 &= 11 - 8(1)\\ 8 &= 3(2) + 2 & 2 &= 8 - 3(2)\\ 3 &= 2(1) + 1 & 1 &= 3 - 2(1)\\ 2 &= 1(2) \end{align} \]

Following this process of verifying the GCD, and solving for the remainders, we can then back solve to get the multiplicative inverse:

\[ \begin{align} 1 &= 3 - 2(1)\\ &= 3 - (8-3(2))(1)\\ &= 3 - (8 - (3(2)))\\ &= 3(3) - 8\\ &= (11-8(1))(3)-8\\ &=11(3) - 8(4)\\ &= 11(3) + 8(-4)\\ \therefore 1 &\equiv 8(-4) \mod 11\text{, or:}\\ 1 &\equiv 8(7) \mod 11 \end{align} \]

7 is the inverse of $8 \mod 11$.

Fermat's Little Theorem

Modular Inversion

Fermat's little theorem is used to distinguish the theorem from his last theorem. The theorem is as follows:

\[ \begin{align} \forall x \in (\mathbb{Z}_p)^*: x^{p-1} &= 1 \text{ in } \mathbb{Z}_p\\ \text{ where }&p\text{ is prime}\\ &(\mathbb{Z}_p)^* \text{ is the set of invertible elements in }\mathbb{Z}_p \end{align} \]

If we take, for example, $p=5$, we can show that $3^{5-1} = 3^4 = 81 = 1$ in $\mathbb{Z}_5$. This theorem can help us to compute inverses, although it takes $O(n^3)$ to complete, as opposed to the Euclid time.

If the modulus is a prime number, then we can use the theorem to compute inverses. For example, earlier, we computed $10/8$ in $\mathbb{Z}_{11}$. We can do this with Fermat's little theorem:

\[ 10/8 = 10 \times 1/8 = 10 \times 8^{-1} \]

Then, we apply the theorem:

\[ 8^{-1} = 8^{11-1-1} = 8^9 = 134217728 = 7\text{ in }\mathbb{Z}_{11} \]

And we can then substitute back in to get:

\[ 10/8 = 10 \times 7 = 70 = 4 \text{ in }\mathbb{Z}_{11} \]

Computing Roots in $\mathbb{Z}_p$

If $p$ is prime and $c \in \mathbb{Z}_p$, when we let $x \in \mathbb{Z}_p | x^e = c$ in $\mathbb{Z}_p$. $x$ is called an $e$th root of $c$.

For example, $7^{1/3} = 6$ in $\mathbb{Z}_{11}$, $3^{1/2} = 5$ in $\mathbb{Z}_{11}$, and $1^{1/3} = 1$ in $\mathbb{Z}_{11}$. To know when these roots exist, of the general form $c^{1/e}$, we need to use some sort of algorithm.

We can make use of another theorem: if $\gcd(e,p-1)=1$, $d$ is the inverse of $e$ in $\mathbb{Z}_{p-1}$ ( $d=e^{-1}$ in $\mathbb{Z}_{p-1}$ and $c^{1/e} = c^d$ in $\mathbb{Z}_p$. This theorem can only be used when $\gcd(e,p-1)=1$, otherwise we have to use something else.

To compute the $e$th root of $c$ in this instance, we find $d$ as the modular inverse of $e$ in $\mathbb{Z}_{p-1}$, then compute $c^{1/e} = c^d$ in $\mathbb{Z}_p$.

The second case we can use if id $\gcd(e,p-1) \ne 1$. In this case, it is harder to find an inverse.

Example: Compute $7^{1/11}$ in $\mathbb{Z}_{17}$

First, we check to see if $\gcd(11, 16)=1$. We can do this with Euclid's algorithm, or in this instance, as the numbers are small, we see that it is $1$. This means that the theorem above applies in this instance.

\[ \begin{align} 16 &= 11 + 5 &\to\quad& 5 = 16 - 11 &\text{(a)}\\ 11 &= 2 \times 5 + 1 &\to\quad&1 = 11 - 2 \times 5 & \text{(b)}\\ 5 &= 5(1) \end{align} \]

We now compute the inverse of $11$ in $\mathbb{Z}_{16}$:

$$ \begin{align} \text{substitute (a) into (b)}\ 1 &= 11 - 2 \times 5\ &= 11 - 2(16 - 11)\ &= 3(11) - 2(16)\ \therefore 1 &\equiv 3 \times 11 \mod 16 \end{align} $$ So $3$ is the multiplicative inverse of $11 \mod 16$. Using this, we can show that $7^{1/11} = 7^3 = 3$ in $\mathbb{Z}_{17}$.

Computing the Square Root in $\mathbb{Z}_p$

For some reason, we have a special case which we can use to compute the square root in $\mathbb{Z}_p$. We introduce the notion of quadratic residue, (or Q.R.), where an element $x \in \mathbb{Z}_p$ is said to be Q.R., if it has a square root in $\mathbb{Z}_p$.

For example, in $\mathbb{Z}_{11}$, $\{1,10\}$ have $\sqrt{1}$, $\{2,9\}$ have $\sqrt{4}$, $\{3,8\}$ have $\sqrt{9}$, $\{4,7\}$ have $\sqrt{5}$, and $\{5,6\}$ have $\sqrt{3}$. In this case, out of $\{0,1,2,3,4,5,6,7,8,9,10\}$, we have the quadratic residues as $\{1,4,9,5,3,0\}$.

It may be confusing that e.g., $9$ appears, but $9^2 = 81 = 4$ in $\mathbb{Z}_{11}$. We can establish which elements are Q.R. through Euler's theorem: let $p$ be an odd prime, if $x$ in $(\mathbb{Z}_p)^*$ 9s a Q.R., then $x^{(p-1)/2} = 1$ in $\mathbb{Z}_p$.

For $\mathbb{Z}_{11}$, we would therefore check each element to the power of 5, as $(p-1)/2 = (11-1)/2 = 5$. Using this, we can go through:

\[ 1^5, 2^5, 3^5, 4^5, \dots, 10^5 \]

From this, we can then assign them as Q.R., where the new element in $\mathbb{Z}_{11}$ is equal to 1. Trivially, $1^5 = 1$, so this would be Q.R. For $2^5 = 32 = 10$ in $\mathbb{Z}_{11}$, so we could assign it a $-1$ in the array of elements that are Q.R.

By computing the square root modular prime, this helps us to compute the order of the elliptic curve groups. The algorithm to compute these square root modular odd primes is dependant on the prime $p$ we use.

In the case $p = 3 \mod 4$, then we can use the theorem that if $c \in (\mathbb{Z}_p)^*$ is Q.R., then $\sqrt{c} = c^{\frac{p+1}{4}}$ in $\mathbb{Z}_p$. The proof of this is:

\[ \begin{align} \left[c^{\frac{p+1}{4}}\right]^2 &= c^{\frac{p+1}{2}} \\ &= \underbrace{c^{\frac{p-1}{2}}}_1 \times C \\ &= \underbrace{(c^{p-1})^{1/2}}_1 \times C\\ &= C \text{ in } \mathbb{Z}_p \end{align} \]

Otherwise, in the case that $p = 1 \mod 4$, there is an algorithm to find the square root with a randomized algorithm with $O(\log^3p)$.

Examples

For case 1, we can have $p = 43$, as $43 = 3 \mod 4$. If we then want to compute $\sqrt{6}$ in $\mathbb{Z}_{43}$, and know that 6 is Q.R. in $\mathbb{Z}_{43}$, we use the theorem: $\sqrt{6} = 6^{(43+1)/4} = 6^{11} = 36$. This is the square root modular odd prime.

Euler Generalization

This is Euler's $\phi$ function. For an integer $N$, we define $\phi(N) = | (\mathbb{Z}_N)^*|$. For example, $\phi(12) = | \{1,5,7,11\}| = 4, \phi(7) = 6$.

To compute this $\phi(N)$, also known as the Euler Totient function, for $N = p$, where $p$ is prime, we can use $\phi(N) = N-1$, and for $N = pq$, where $p,q$ are prime, then $\phi(N) = (p-1)(q-1)$. This is where the number is a composite prime. For $\phi(37) = 36$, and for $\phi(21) = (3-1)(7-1) = 2 \times 6 = 12$.

Recall that Fermat's little theorem is $\forall x \in (\mathbb{Z}_p)^*: x^{p-1} = 1$ in $\mathbb{Z}_p$. Euler's generalization of this is:

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

For example, $5^{\phi(12)} = 5^4 = 625 = 1$ in $\mathbb{Z}_12$. This theorem is what forms the basis for RSA cryptosystems.

Groups

If we let $G$ as a non-empty set, and $*$ is a binary operation on $G$, then we have for every two points $a,b \in G$, a value $a * b$ is defined. We can call $G$ a group if it has the following properties:

Closure: $\forall a,b \in G, (a * b) \in G$
Associativity: $\forall a,b,c \in G, (a * b) * c = a * (b * c)$
Identity: $\exists e \in G | a * e = a = e * a \forall a \in G$
Invertability: $\forall a \in G \exists ai \in G | a * ai = e = ei * a$

The group doesn't have to be closed under all operators, only specific ones. For example, $\mathbb{Z,Q,R,C,Z}_n$ are groups under addition, with $* = +, e = 0, ai = -a$.

If we can find some $*,e,ai$, such that the properties are all satisfied, then we can say that the class is a group under the property.

Proofs

Proving Closure of $\mathbb{Z}_N$ under Addition

Under addition modulo $N$, we can show that $a,b \to a + b \mod N$. Under closure, we can show that if $a,b \in \mathbb{Z}_N \to a + b \mod N \in \mathbb{Z}_N$. Associativity we can show $((a+b\mod N) + c) \mod N = (a+ (b+c \mod N)) \mod N$. Identity $e = 0$, as $a+= \equiv 0 + a \equiv a \mod N$. Finally, under inverse, we can have the inverse $-a$: $-a \equiv N -a \mod N$.

Proving Closure of $\mathbb{Z^*}_{12}$ under Multiplication Modulo 12

Closure: $a,b \in \mathbb{Z}^* \to ab \mod 12 \in \mathbb{Z}^*_{12}$, as $\gcd(a,12) = \gcd(b,12) = 1 \to \gcd(ab\mod 12 , 12) = 1$.
Associativity: $((ab \mod 12)c)\mod 12 = (a(bc \mod 12)) \mod 12$
Identity: $1$ as $a\times 1 \equiv 1 \times a \equiv a \mod 12 \forall a$
Inverse: $\forall a \in Z^*_{12} \exists a -1 \in \mathbb{Z}^*_12 | a \times a - 1 \mod 12 = 1$.

Group Order

The order of a group $G$ is the size $|G|$, or the number of elements in the group. For a group $(\mathbb{Z}_{12}, +)$, there are 12 elements.

Abelian Groups

A group $G$ is commutative if $a*b = b*a \forall a,b \in G$, or where the groups are commutative. For example, for all nonzero elements in $\mathbb{Q,R,C}$, these would be commutative under multiplication, or Abelian.

Cyclic Groups

Groups are cyclic if they have a generator $g$, which is an element $g \in G | a \in G \exists a = g^i$ for some integer $i$. For example, $\mathbb{Z}$ is cyclic as every element has the form $1 + 1 + \cdots + 1$, but $\mathbb{Q,R,C}$ are not cyclic.

Intractable Problems

Discrete Logarithm Problem

The discrete logarithm $\log b a$ is an integer $k$ such that $b^k = a$. We can compute the discrete logarithm in a base for elements of a modulus set:

\[ \begin{align} \text{D}\log_2 \forall \mathbb{Z}_{13}:\\ y = 2^x &: 1,2,3,4,5,6,7,8,9,10,11,12\\ x = D\log_2(y) &: 0,1,4, \dots \end{align} \]

The definition of this in terms of modular arithmetic is to fix a prime $p > 2$ and a $g \in (\mathbb{Z}_p)^*$ of order $q$. Consider a function $y \mapsto g^x$ in $\mathbb{Z}_p$, then consider inverse function $\text{D}\log_g(g^x) = x | x \in \{0,\dots,q-2\}$.

If we are given $g,x$ then we can somewhat easily compute $y$, but given $g,y$ it is hard to compute $x$. The best known algorithm to do this is called the general number field sieve, which has $e^{O(\sqrt[3]{N})}$.

Factoring Problem

This was first stated by Gauss in 1805:

The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic.

The best known algorithm for this is the number field sieve, again with a runtime in the order $e^{O(\sqrt[3]{N})}$. The current record for this factorisation is RSA-768, which has 232 digits, and this took 2 years, 100s of computers. To factorize a 1024-bit integer (with 309 digits), this would take substantially longer.

Despite this, NIST and other security bodies are no longer recommending the use of RSA-1024, and instead requiring keys of 2048-, or 4096-bit lengths.

Number Theory

Computational Complexity Theory

Big-O Notation

Complexity of Common Problems

Modular Arithmetic

The Mod Congruence

Example: Congruence of \(113\) in \(\mathbb{Z}_{24}\)

Mathematical Properties of Modular Arithmetic

Addition in \(\mathbb{Z}_n\)

Multiplication in \(\mathbb{Z}_n\)

Modular Inversion

Division in \(\mathbb{Z}_n\)

Example: Compute \(10 \div 8\) in \(\mathbb{Z}_{11}\)

Euclid's Algorithm

Example: Calculate \(\gcd(60,22)\)

Modular Inversion Using Euclidean Algorithm

Fermat's Little Theorem

Modular Inversion

Computing Roots in \(\mathbb{Z}_p\)

Example: Compute \(7^{1/11}\) in \(\mathbb{Z}_{17}\)

Computing the Square Root in \(\mathbb{Z}_p\)

Examples

Euler Generalization

Groups

Proofs

Proving Closure of \(\mathbb{Z}_N\) under Addition

Proving Closure of \(\mathbb{Z^*}_{12}\) under Multiplication Modulo 12

Group Order

Abelian Groups

Cyclic Groups

Intractable Problems

Discrete Logarithm Problem

Factoring Problem