# Public Key Mathematics

- Recap: in rings and fields, multiplicative inverse might exist such that

$$
a\cdot a^{-1} \equiv 1 \space (mod \space p)
$$

- Modular inverse exists when $gcd(a,p)=1$
- For prime fields, $gcd(a,p)=1, \forall a \neq 0 \in GF(p)$

#### Euclidean Algorithm

- The Euclidean algorithm calculates the greatest common divisor of two numbers $gcd(r_0, r_1)$
    - This is the largest number that divides both $r_0$ and $r_1$
- If $gcd(x,y)=1$ then $x$ and $y$ are **coprime** (sometimes called relatively prime)
- The Euclidean algorithm is based around the fact:
    - $gcd(r_0, r_1) = gcd(r_1, r_0 - r_1)$

![1646755531.png](img/1646755531.png)

- Computing $(x-y)\cdot gcd(r_0, r_1)$ is easier as it's a smaller number
- Doing this repeatedly is slow, we can use $gcd(r_0,r_1) = gcd(r_1, r_0\space mod \space r_1)$

![1646755650.png](img/1646755650.png)

##### Example

$r_0 = 57 \\
r_1 = 12$

- At each step we convert $r_0$ and $r_1$ into the form $r_0=q\cdot r_1 + r_2$

$r_0=q\cdot r_1 + r_2 \\57=4\cdot 12 + 9\\ r_1=q\cdot r_2 + r_3 \\ 12=1\cdot 9 + 3 \\ 9 = 3\cdot 3 + 0$

- When the algorithm gets to 0, it is finished, therefore $gcd(57,12)=3$

![1646756075.png](img/1646756075.png)

#### Bézout’s Identity

- Bézout’s identity tells us that the greatest common divisor of two numbers can be expressed as the sum of multiples of these numbers
- $gcd(r_0,r_1) = s\cdot r_0 + t\cdot r_1$
    - e.g. $gcd(99,20)=-1\cdot 99+5\cdot 20=1$
    - $gcd(141,50)=11\cdot 141+-31\cdot 50=1$

##### Extended Euclidean Algorithm

- The extended Euclidean algorithm calculates the $gcd(r_0,r_1)$ as normal, and in addition calculates $s$ and $t$.

| Euclidean Algorithm                | Extended Euclidean Algorithm                                 |
| ---------------------------------- | ------------------------------------------------------------ |
| $r_0=q_1\cdot r_1+r_2$             | $r_2=r_0-q_1\cdot r_1 \quad \rightarrow \quad r_2=s_2\cdot r_0-t_2\cdot r_1$ |
| $r_1=q_2\cdot r_2+r_3$             | $r_3=r_1-q_2\cdot r_2  \quad \rightarrow \quad r_3=s_3\cdot r_0-t_3\cdot r_1$ |
| $r_2=q_3\cdot r_3+r_4$             | $r_4=r_2-q_3\cdot r_3   \quad \rightarrow \quad r_4=s_4\cdot r_0-t_4\cdot r_1$ |
| …                                  | …                                                            |
| $r_{l-2}=q_{l-1}\cdot r_{l-1}+r_l$ | $r_l=r_{l-2}-q_{l-1}\cdot r_{l-1}   \quad \rightarrow \quad r_l=s_l\cdot r_0-t_l\cdot r_1$ |
| $r_{l-1}=q_{l}\cdot r_{l}+0$       |                                                              |

###### Example

![1646757043.png](img/1646757043.png)

###### Formula

![1646757908.png](img/1646757908.png)

![1646758001.png](img/1646758001.png)

#### Modular Inverses

$$
\begin{split}
& a\cdot a^{-1} \equiv 1 \mod n \\
& gcd(n,a) = s\cdot n + t\cdot a = 1 \\
& s\cdot n + t\cdot a = 1 \\
& s\cdot 0 + t\cdot a \equiv 1 \space mod \space n \\
& t\cdot a \equiv 1 \space mod \space n \\
& t \equiv a^{-1} \space mod \space n
\end{split}
$$

Where $t$ is our multiplicative inverse