Number Theory

Relatively prime numbers and greatest common divisor

Naturals $\mathcal{N}=\{0,1,2,\dots \}$ Integers $\mathcal{Z}=\{0,1,-1,\dots \}$ Primes $\mathcal{P}=\{2,3,5,7,\dots \}$

To factor a number $a$ is to write it as a product of other numbers, $a=b\times c\times d$. Multiplying is trivial, but factoring is hard. We cannot factor most numbers with more than 1024 bits.

Prime Factorisation

The prime factorisation of a number $a$ amounts to writing it as a product of primes:

$$a=\prod _{p\in \mathcal{P}}=2^{a_2}\times 3^{a_3}\times 5^{a_5}\times \dots \text{ where }{a}_p\in \mathcal{N}$$Link to original

Divides notation

$a\ne 0$ divides $b$ (written $a\mid b$) if there is an $m$ such that $m\times a=b$. e.g. $3|6$

Link to original

Not divides notation

$a$ does not divide $b$ (written $a\nmid b$) if there is no $m$ such that $m\times a=b$. e.g. $3\nmid 7$

Link to original

Relatively prime numbers

Two natural numbers, $a$ and $b$, are relatively prime if they have no common divisors / factors apart from $1$, i.e. if $gcd(a,b)=1$ (greatest common divisor).

Link to original

(Extended) Euclid’s algorithm

We can quickly compute $gcd$ using Euclid’s algorithm.

It is based on the theorem that $gcd(a,b)=gcd(b,a\text{ mod }b)$ for any non-negative integer $a$ and any positive integer $b$.

Euclid's algorithm

The algorithm works as follows: $\text{Euclid}(a,b)$

• if $b=0$ then
  • return $a$
• else
  • return $\text{Euclid}(b,a\text{ mod }b)$

Link to original

Example

\begin{aligned} gcd(60, 14)&: 60 &&= (4 \times 14) + \color{red} 4 \

gcd(14, {\color{red} 4})&: 14 &&= (3 \times {\color{red} 4}) + {\color{blue} 4} \ gcd({\color{red} 4}, {\color{blue} 2})&: {\color{red} 4} &&= 2 \times {\color{blue} 2} \end{aligned}

Extended Euclid's algorithm

Extended Euclid’s algorithm also computes $x,y\in \mathcal{Z}$ (integer coefficients) such that:

$$d=gcd(a,b)=(x\times a)+(y\times b)$$

The algorithm works as follows: $\text{Extended-Euclid}(a,b)$

• if $b=0$ then
  • return $(a,1,0)$
• else
  • $(d^{\prime },x^{\prime },y^{\prime })\leftarrow \text{Extended-Euclid}(b,a\text{ mod }b)$
  • $(d,x,y)\leftarrow (d^{\prime },y^{\prime },x^{\prime }-(\lfloor a/b\rfloor \times y^{\prime }))$
  • return $(d,x,y)$

Where $q=\lfloor a/b\rfloor$ is the quotient of the division (for $a=(q\times b)+r$).

Link to original

Example

Using our earlier example, $2=14-3\times (60-(4\times 14))=(-3\times 60)+(13\times 14)$.

$\text{Extended-Euclid}(99,78)=3=(99\times (-11))+(78\times 14)$

Modular arithmetics

Remainder (modular arithmetic notation)

$\forall an.\exists qr.(a=(q\times n)+r)$ where $0\le r<n$. Here $r$ is the remainder which we write as $r=a\text{ mod }n$.

Link to original

Congruent Modulo

$a,b\in \mathcal{Z}$ are congruent modulo $n$, if $a\text{ mod }n=b\text{ mod }n$. We write this as $a{=}_{n}b$ (i.e. they have the same remainder when divided by some $n$).

Link to original

Modulo operator properties

The modulo operator has the following properties:

• Reflexivity: $a{=}_{n}a$
• Symmetry: if $a{=}_{n}b$ then $b{=}_{n}a$
• Transitivity: if $a{=}_{n}b$ and $b{=}_{n}c$ then $a{=}_{n}c$
• $(a\bullet b){=}_n(a\text{ mod }n)\bullet (b\text{ mod }n)$ for $\bullet \in \{+,-,\times \}$

  $(a\bullet b)\text{ mod }n=(a\text{ mod }n)\bullet (b\text{ mod }n)\text{ mod }n$ $\begin{array}{rl}2& =(5\times 6)\text{ mod }4\\ & =[(5\text{ mod }4)\times (6\text{ mod }4)]\text{ mod }4\\ & =(1\times 2)\text{ mod }4\\ & =2\text{ mod }4\\ & =2\end{array}$

• if $a\times b{=}_{n}a\times c$ and $a$ is relatively prime to $n$, then $b{=}_{n}c$.

  $8\times 4{=}_{3}8\times 1$ $8$ is relatively prime to $3$ so $4{=}_{3}1$

• if $a_1{=}_n{b}_1$ and $a_2{=}_n{b}_2$ then $\begin{array}{rl}(a_1+a_2)& {=}_n(b_1+b_2)\\ & \text{and}\\ (a_1\times a_2)& {=}_n(b_1\times b_2)\end{array}$

Link to original

Given $a=q\times n+r$ with $q=\lfloor a/n\rfloor$ and $0\le r<n$ and $r=a\text{ mod }n$:

For any integer $a$, we can rewrite as: $a=\lfloor a/n\rfloor \times n+(a\text{ mod }n)$

Theorems

Theorem: suppose that $a,b\in \mathcal{Z}$ are relatively prime. There is a $c\in \mathcal{Z}$ satisfying $(b\times c){=}_{a}1$, i.e. we can compute $b^{-1}\text{ mod }a$.

Proof: From Extended Euclid’s Algorithm, there exist $x,y\in \mathcal{Z}$ where $1=(a\times x)+(b\times y)$. Since $a|(a\times x)$, we have $(b\times y)\text{ mod }a=1$. Assertion follows with $c=y$.

Fermat's little theorem

Theorem: for $a$ and $n$ relatively prime and $n$ prime: $a^{n-1}{=}_{n}1$

Proof:

Euler Totient Function

Complete set of residues

When doing arithmetic modulo $n$, complete set of residues is $0,\dots ,n-1$.

Link to original

Reduced set of residues

The reduced set of residues consists of those numbers (residues) that are relatively prime to $n$. For instance, for $n=10$:

• complete set of residues: $\{0,1,2,3,4,5,6,7,8,9\}$
• reduced set of residues: $\{1,3,7,9\}$

Link to original

Euler Totient Function

Number of elements in reduced set of residues is called the Euler Totient Function $\varphi (n)$.

Link to original

Properties of Euler Totient Function

Properties of Euler Totient Function:

• $\varphi (1)=1$
• $\varphi (p)=p-1$ if $p$ is prime
• $\varphi (p\times q)=\varphi (p)\times \varphi (q)=(p-1)\times (q-1)$ if $p$ and $q$ are prime and $p\ne q$

Link to original

So this means Fermat’s little theorem (for $a$ and $n$ relatively prime and $n$ prime) can be rewritten into $a^{\varphi (n)}{=}_{n}1$ for all $a$, $n$ such that $n$ is prime and $gcd(a,n)=1$.

RSA Algorithm

Rivest Shamir Aldeman Block Cipher

The RSA algorithm is a block cipher in which the plaintext and ciphertext are integers between $0$ and $n-1$ for some $n$.

• Typically $n$ is $1024$ bits ($309$ decimal digits)

The security of the algorithm comes from the difficulty of factoring large numbers. Keys are functions of pairs of large, $\ge 100$ digit, prime numbers.

Link to original

Named after inventors Rivest, Shamir, Aldeman

RSA Algorithm

RSA Algorithm

• Let $n$ be a number known by sender and receiver.
• Plaintext is encrypted in blocks, with each block having a binary value less than $n$. Block size must be less than or equal to ${\log }_2(n)+1$. Each block represents a number $M$ such that $M<n$.

We define RSA encryption and decryption of $M$ for some (properly) chosen values of $e$ and $d$

$$\begin{array}{rl}C& =M^e\text{ mod }n\\ M& =C^d\text{ mod }n\\ & =(M^e{)}^d\text{ mod }n\\ & =M^{ed}\text{ mod }n\end{array}$$

It is a public-key encryption algorithm with:

• public key $PU=(e,n)$
• private key $PR=(d,n)$

For the algorithm to work, the following requirements must be met:

1. It is possible to find values of $e$, $d$, $n$ such that $M^{ed}\text{ mod }n=M$ for all $M<n$.
2. It is relatively easy to calculate $M^e\text{ mod }n$ and $C^d\text{ mod }n$ for all values of $M<n$.
3. It is infeasible to determine $d$ given $e$ and $n$.

Link to original

Correctness of RSA

We must show that there exist $e,d,n$ such that $M^{ed}\text{ mod }n=M$ for all $M<n$. It can be shown that the equation holds if $e$ and $d$ are multiplicative inverses $\text{mod }\varphi (n)$, i.e.:

$$\begin{array}{rl}d& {=}_{\varphi (n)}{e}^{-1}\text{ if and only if}\\ de& {=}_{\varphi (n)}1\\ ed\text{ mod }\varphi (n)& =1\end{array}$$

But this is only true if $d$ (and $e$) is relatively prime to $\varphi (n)$, i.e. $gcd(\varphi (n),d)=1$.

Correctness of RSA (cont.)

Since $ed\text{ mod }\varphi (n)=1$, there exists $k\in \mathbb{N}$ such that $ed=1+k\varphi (n)$. Now consider whether or not $\text{gcd}(M,p)=1$, i.e. whether $p\mid M$.

Case 1: if $gcd(M,p)=1$ then by Fermat’s theorem $M^{p-1}{=}_{p}1$ Raising both sides to the power $k(q-1)$ and multiplying by $M$ yields $M^{1+k(p-1)(q-1)}{=}_p{M}^{1+k\varphi (n)}{=}_{p}M$

Case 2: if $gcd(M,p)=p$ then last congruence is trivially valid since each side is congruent to $0\text{ mod }p$. Hence in both cases $M^{ed}{=}_{p}M$ By the same argument $M^{ed}{=}_{q}M$ and since $p$ and $q$ are distinct primes, by the Chinese Remainder Theorem it follows that $M^{ed}{=}_{n}M$ and hence:

$$C^d{=}_n(M^e{)}^d{=}_{n}M$$

Chinese Remainder Theorem

Algorithm Steps

Generation of public / private key pair

1. Generate two prime numbers $p$ and $q$, these are kept private and are two (large) distinct primes.
2. Compute $n=p\times q$ and $\varphi (n)=(p-1)\times (q-1)$.
3. Select an $e$, with $1<e<\varphi (n)$, relatively prime to $\varphi (n)$.
4. Compute $d=e^{-1}\text{ mod }\varphi (n)$.
5. Public $(e,n)$, keep $(d,n)$ private, discard $p$ and $q$.

Encryption with key $(e,n)$

1. Break message $M$ into blocks $M_1{M}_2\dots$ with $M_i<n$
2. Compute $C_i=M_i^e\text{ mod }n$

Decryption with key $(d,n)$

1. Compute $M_i=C_i^d\text{ mod }n$

Example of RSA Algorithm

Another Example of RSA Algorithm

Using RSA to process multiple blocks of data