\documentclass[a4paper,twoside,12pt]{article}
\usepackage[margin=3cm]{geometry}

\usepackage[latin1]{inputenc}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{bm}
\usepackage{bbm}
\usepackage{mathrsfs}
\usepackage[T1]{fontenc}
\usepackage{ae}
\usepackage[danish]{babel}
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{mathdots,placeins,booktabs,array}
\usepackage{color}
\usepackage{alltt}
\usepackage{enumitem}
\usepackage{fixme}
\usepackage{framed}

\newcommand{\N}{\mathbbm{N}}
\newcommand{\Z}{\mathbbm{Z}}
\newcommand{\Q}{\mathbbm{Q}}
\newcommand{\R}{\mathbbm{R}}
\newcommand{\T}{\mathbbm{T}}
\providecommand{\abs}[1]{\left\lvert #1 \right\rvert}
\renewcommand{\pmod}[1]{\, (\operatorname{mod } #1)}
\renewcommand{\bar}{\overline}

\newcommand{\1}{\mathbbm{1}}


\newcommand{\Mat}{\operatorname{Mat}}
\newcommand{\AP}{\operatorname{AP}}
\newcommand{\trace}{\operatorname{trace}}
\newcommand{\diam}{\operatorname{diam}}

\usepackage{amsthm}

\theoremstyle{plain}%default
\newtheorem{thm}{Sætning} %nummereringen foelger section
\newtheorem*{thm*}{Theorem} % thm* er nu uden nummer
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{example}[thm]{Eksempel}

\theoremstyle{remark}
\newtheorem{obs}[thm]{Observation}
\newtheorem{remark}[thm]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem*{claim*}{Claim}

\theoremstyle{exerc}
\newtheorem{exerc}{Opgave}


\newcommand{\refthm}[1]{theorem~\ref{#1}}
\newcommand{\refprop}[1]{Proposition~\ref{#1}}
\newcommand{\reflemma}[1]{lemma~\ref{#1}}
\newcommand{\refcor}[1]{Corrolary~\ref{#1}}
\newcommand{\refdefn}[1]{Definition~\ref{#1}}
\newcommand{\refremark}[1]{Remark~\ref{#1}}
\newcommand{\refexample}[1]{Example~\ref{#1}}

	\usepackage{tikz}

\newcommand\calculator{\tikz{
\node (c) [inner sep=0pt, draw, fill=black, anchor=south west]{\phantom{N}};
\begin{scope}[x=(c.south east),y=(c.north west)]
   \fill[white] (.1,.7) rectangle (.9,.9);
   \foreach \x in {.1, .33, .55, .79}{
   \foreach \y in {.1, .24, .38, .53}{
   \fill[white] (\x,\y) rectangle +(.11,.07);}}
\end{scope}
}}

\title{\Huge{\bf{Kryptologi og RSA}}}
\date{}
\author{Jonas Lindstrøm Jensen (jonas@imf.au.dk)}

\begin{document}
\maketitle

\section{Introduktion}
Der har formodentlig eksisteret kryptologi lige så længe, som vi har haft et sprog. Ønsket om at kunne sende beskeder, som uvedkommende ikke skal kunne læse, opstår i hvert fald i mange situationer, og forskellige metoder til at opnå dette, har været anvendt op gennem historien. En klassiske metode, der går tilbage til Romerne, går ud på, at man erstatter hvert bogstav med det bogstav, der står fx tre pladser længere henne i alfabetet, og hvis man rammer enden, starter man fordra. Så istedet for {\color{blue}{\verb|ANGRIB|}} sender man beskeden {\color{red}{\verb|DQJULE|}}. Afsender og modtager skal så inden blive enige om, hvor langt man rykker bogstaverne. Siden er der blevet udviklet mange metoder, og i denne lille note vil vi fokusere på en af de nyeste, nemlig RSA. Metoden er opkaldt efter opfinderne Ron Rivest, Adi Shamir og Leonard Adleman. Vi vil i denne note først præsentere nogle klassiske krypteringsmetoder, derefter forklare den nødvendige talteori for at forstå RSA, og til sidst forklare, hvorledes RSA fungerer.


\section{Kryptologi}
Kryptologi er læren om, hvorledes man kan maskere meddelelser, således at kun rette vedkommende skal kunne læse den. Vi vil her præsentere nogle metoder til, hvorledes det kan gøres. Afsender og modtager bliver enige om en nøgle, der bruges både til at \emph{kryptere} og \emph{dekryptere} beskeden, og pointen er naturligvis, at andre helst ikke skal kunne regne nøglen ud, og dermed kunne dekryptere beskeden.\footnote{En mere fuldstændig gennemgang af kryptologi findes i bogen ``Kryptologi -- fra viden til videnskab'' af Peter Landrock og Knud Nissen, (ABACUS,1990).}

\subsection*{Cæsar-kryptering}
Denne metode omtalte vi i introduktionen. Her krypteres en besked ved at hvert bogstav erstattes med det bogstav, der står $n$ pladser pladser længere henne i alfabetet, hvor man starter forfra, hvis man når slutningen af alfabetet. Hvis $n = 3$ får vi altså
\begin{alltt}\begin{center}
{\color{blue}{ANGRIB}}
{\color{red}{DQJULE}}
\end{center}\end{alltt}
Nøglen er her $n$, og modtageren rykker nu alle bogstaver $n$ pladser tilbage, og får den oprindelige besked. Denne form for kryptering er ret nem at bryde, idet man jo bare kan prøve de 27 muligheder der er -- hvis der er 28 bogstaver i alfabetet, og man rykker et bogstav 28 pladser, får man jo det samme bogstav.

\subsection*{Kryptering ved substitution}
Her bliver afsender og modtager enige om, hvilket bogstav hvert bogstav skal ændres til. Hvis vi vælger
\begin{alltt}\begin{center}
{\color{blue}ABCDEFGHIJKLMNOPQRSTUVWXYZÆØÅ}
{\color{red}QWERTYUIOPÅASDFGHJKLÆØZXCVBNM}
\end{center}\end{alltt}
får vi fx
\begin{alltt}\begin{center}
{\color{blue}{MØD MIG VED HULEN KLOKKEN FIRE}}
{\color{red}{SNR SOU ØTR IÆATD ÅAFÅÅTD YOJT}}
\end{center}\end{alltt}
Denne form for kryptering er noget sværere at bryde, idet der jo er $28 \cdot 27 \cdot 26 \cdots 2 \cdot 1 = 28! \approx 8.84 \cdot 10^{30}$ forskellige måder vi kan gøre det på (hvorfor?). Dog har en uvedkommende modtager stadig en god chance for at bryde koden, idet alle bogstaver ikke optræder lige ofte i en tekst. Det mest almindelige bogstav er {\color{blue}{\verb|E|}}, så det bogstav der optræder oftest i den krypterede tekst svarer højst sandsynlig til {\color{blue}{\verb|E|}}, og ved at gætte sig lidt frem, kan man ofte bryde denne form for kryptering alligevel.

\subsection*{Vigin\`{e}re-kryptering}
Der er blevet udviklet adskillige krypteringsmetoder, hvor man forsøger at undgå, at man kan finde {\color{blue}{\verb|E|}}'et. En af disse er Vigin\`{e}re-kryptering opkaldt efter Blaise de Vigen\`{e}re (1523-1596). Her er nøglen et ord, fx {\color{green} \verb|ABE|}. Dette ord skrives gentagne gange over den tekst, man vil kryptere, og hvert bogstav i teksten rykkes så det antal pladser i alfabetet, svarende til den plads bogstavet over har i alfabetet.
\begin{alltt}\begin{center}
{\color{green} ABE ABE ABE ABEAB EABEABE ABEA}
{\color{blue} MØD MIG VED HULEN KLOKKEN FIRE}
{\color{red} NAI NKL WGI IWQFP PMQPLGS GKWF}
\end{center}\end{alltt}
Det er lidt mere kringlet at bryde denne kode, og koder af denne type blev også benyttet under Anden Verdenskrig, fx brugte Tyskernes berømte Enigma-maskine en metode svarende lidt til denne, men dog med en nøgle, der var meget, meget længere, hvilket gjorde det sværere at bryde krypteringen. Det lykkedes at bryde krypteringen, og det fik betydning under krigen.\footnote{Se ``The Code Book'' af Simon Singh for en historisk gennemgang af kryptologi og mere om Enigma-maskinen.}

\subsection*{RSA} De tre krypteringsmetoder vi har præsenteret ovenfor har det til fælles, at her er nøglen man bruger til at kryptere og dekryptere nøjagtigt den samme. Modsat hvad man skulle tro, er det dog ikke nødvendigt, at nøglerne er ens, og i RSA skal man bruge to forskellige nøgler. Det giver nogle andre anvendelsesmuligheder end med de systemer, vi hidtil har set på.

\section{Talteori}
Det er nødvendigt at kunne lidt talteori for at forstå RSA, så det vil vi præsentere i dette afsnit. Hvis du gerne vil se flere detaljer om talteori, så se Johan P. Hansen og Henrik Spalks bog ``Algebra og talteori'', Gyldendal (2002).

Hvis man har to positive hele tal, $n$ og $q$, kan man dividere $n$ med $p$. Hvis $q$ går op i $n$ giver det et helt tal og hvis ikke, så er der en \emph{rest}, der nødvendigvis må være mindre end $q$ (hvorfor?). Hvis to tal $n$ og $m$ giver samme rest ved division med $q$, så skriver vi
\[ n \equiv m \pmod q \]
og siger at $n$ og $m$ er kongruent modulo $q$.

\begin{framed}
\begin{example} Lad $q = 4$. Så giver $7$ og $15$ begge en rest på $3$ ved division med $4$, så derfor er
\[ 7 \equiv 15 \pmod 4. \]
\end{example}
\end{framed}
Man kan også se eksemplet ovenfor sålede: Skriv tallene i en spiral, så der hver gang bruges fire tal til at nå en omgang rundt. To tal er så kongruente, hvis de ligger på samme 'arm',
\begin{figure}[!ht]
\begin{center}
\includegraphics{spiral.pdf}
\end{center}
\end{figure}

Vi er i den heldige situation, at kongruens opfører sig næsten lige som det lighedstegn i kender. Fx kan man stadig bevare en kongruens, hvis man lægger det samme tal til på begge sider.

\begin{framed}
\begin{example}
Vi ved fra ovenstående eksempel at
\[ 7 \equiv 13 \pmod 3, \]
men det gælder også at
\[ 8 \equiv 14 \pmod 3 \]
eller at
\[ 14 \equiv 26 \pmod 3. \]
Man kan desuden erstatte et tal med et vilkårligt andet tal, der giver samme rest ved division med 3, fx er
\[ 7 + 16 \equiv 1 + 1 \equiv 2 \pmod 3. \]
\end{example}
\end{framed}

Vi får brug for lidt flere begreber, blandt andet følgende to.

\begin{itemize}
\item \emph{Indbyrdes primiske}:  To tal er indbyrdes primiske, hvis der ikke er andre tal end $1$, der går op i begge tal.
\item \emph{Eulers $\phi$-funktion}: For et tal $n$ angiver $\phi(n)$ hvor mange af tallene $m =1,2,\ldots,n$ der er indbyrdes primisk med $n$.
\end{itemize}

\begin{framed}
\begin{example}
Det ses at $4$ og $9$ er indbyrdes primiske, men at $4$ og $6$ ikke er det, idet $2$ går op i begge tal. Hvis $n=9$ ser vi, at $1,2,4,5,7$ og $8$ er indbyrdes primiske med $9$, så $\phi(9) = 6$.
\end{example}
\end{framed}

Hvis nu $p$ er et primtal\footnote{Husk at $p$ er et primtal hvis kun $1$ og $p$ går op i $p$.}, så er $\phi(p) = p-1$ idet alle tallene $1,2,\ldots,p-1$ er indbyrdes primiske med $p$. Det gælder også at hvis $p$ og $q$ er forskellige primtal, så er $\phi(pq) = (p-1)(q-1)$.

Vi får også brug for Eulers sætning opkaldt efter Leonard Euler (1707--1783).
\begin{thm} Lad $a$ og $n$ være indbyrdes primiske. Så er
\[ a^{\phi(n)} \equiv 1 \mod n. \]
\end{thm}

\begin{framed}
\begin{example} I sidste eksempel så vi, at $\phi(9) = 6$ og at $2$ er indbyrdes primisk med $9$. Så her er $a=2, n=9$ og $\phi(n) = 6$ og Eulers sætning siger så, at
\[ 2^6 \equiv 1 \mod 9. \]
Det er heldigvis sandt idet $2^6 = 64$.
\end{example}
\end{framed}

\begin{remark}[\calculator] Hvis du har en TI-89 (eller anden grafregner fra Texas-Intrument) kan du finde resten af division af $n$ med $q$ ved ar bruge kommandoen \verb|mod|, der findes under \verb|Math|, ved at skrive \verb|mod(n,q)|. Grafregnere af andre mærker har helt sikkert en tilsvarende funktion. Hvis du ikke kan finde den, kan du gøre således:
Udregn først $n/q$. Hvis det ikke giver et helt tal, husk da det af resultatet der står før kommaet, kald det $m$. Resten kan nu findes som
\begin{alltt}\begin{center}
n - q*m
\end{center}\end{alltt}
Hvis vi har $n = 219$ og $q = 7$ får vi
\begin{alltt}\begin{center}
n/q = 31.287
\end{center}\end{alltt}
så vi lader $m = 31$, og resten er nu
\begin{alltt}\begin{center}
219 - 7*31 = 2
\end{center}\end{alltt}
\end{remark}

\section{RSA}
Vi er nu klar til at forklare, hvorledes RSA fungerer. En typisk situation hvor RSA benyttes er, hvis en kunde vil sende information til sin bank, fx i forbindelse med netbank. Husk på at ideen med systemet er, at der skal bruges forskellige nøgler til at kryptere og dekryptere en besked. På den måde kan banken gøre den nøgle, der kan bruges til at kryptere med, fuldstændigt offentlig, hvorimod de holder den anden nøgle hemmelig.

Matematisk set foregår det således: Banken vælger to store primtal, $p$ og $q$, som de holder hemmelige. De offentliggører produktet af de to, $m = pq$ og et tal $k$ der er indbyrdes primisk med $\phi(m)$. Så situationen er altså:

\[ \text{\bf{Offentlig: }} m, k \qquad \text{\bf{Hemmelig: }} p,q, \phi(m). \]

En kunde vil gerne sende beskeden ${\color{blue} B} < m$, og sender istedet ${\color{red} C} < m$ hvor 
\[ {\color{red} C} \equiv {\color{blue} B}^k \pmod m. \]
Bemærk at vores meddelelse her er et tal, hvor vi tidligere så på en tekst. Det er dog ikke svært at lave en tekst om til tal -- fx ved at erstatte hvert bogstav med dens plads i alfabetet.

\begin{framed}
\begin{example}
Banken vælger primtallene $3$ og $5$ og offentliggører produktet $15$. Idet $\phi(15) = \phi(3 \cdot 5) = (3-1)(5-1) = 8$ kan de vælge $k = 3$.

En kunde vil gerne sende beskeden ${\color{blue} 2}$ og sender istedet ${\color{red} 8}$ idet ${\color{blue} 2}^3 \equiv {\color{red} 8} \pmod{15}$.
\end{example}
\end{framed}

Nu skal banken gerne kunne finde frem til den oprindelige besked. Først finder de to positive tal $u,v$ således at\footnote{Det kan gøres vha. en metode kaldet \emph{Euklids algoritme}}
\[ ku - \phi(m) v = 1 \]
og dermed
\[ ku = 1+\phi(m)v. \]
Banken kan nu finde den oprindelige besked $B$ ved at udregne $C^u$ idet
\[ {\color{red} C}^u = ({\color{blue} B}^k)^u = {\color{blue} B}^{ku} = {\color{blue} B}^{1+\phi(m)v} = {\color{blue} B}{\color{blue} B}^{\phi(m)v} = {\color{blue} B} ({\color{blue} B}^{\phi(m)})^v = {\color{blue} B} \cdot 1^v \equiv {\color{blue} B} \pmod m \]
hvor vi i kongruensen til sidst benytter Eulers sætning fra sidste kapitel.

\begin{framed}
\begin{example}
Banken modtager fra foregående eksempel beskeden ${\color{red} 8}$. Idet $\phi(15) = 8$ skal de nu finde $u,v$ så
\[ 3u - 8v = 1. \]
De kan fx vælge $u=3$ og $v=1$ -- så er
\[ {\color{red} 8}^3 = 512 \equiv {\color{blue} 2} \pmod{15} \]
som jo var den oprindelige besked.
\end{example}
\end{framed}


\section{Sikkerhed}
I eksemplet ovenfor, vil det være ret nemt at bryde krypteringen, for som i måske bemærkede, så er $m$ og $k$ offentligt kendte, og man kan dekryptere en besked hvis man kender $u$ som findes ved hjælpe af $k$ og $\phi(m)$. Tidligere fandt vi $\phi(m)$ for nogle små eksempler, og i teorien er det da også muligt at udregne $\phi(m)$, bare man kender $m$. I praksis er $m$ dog et tal på adskillige hundrede cifre, så det vil tage alt for lang tid at prøve med alle divisorere. Den eneste grund til at banken kan udregne $\phi(m)$ er, at de kender $p$ og $q$ og de ved at $\phi(m) = (p-1)(q-1)$. At gange to kæmpestore tal sammen virker måske uoverskueligt, men det er enormt meget nemmere end at udregne $\phi(m)$.

En anden måde at angribe systemet på er, hvis man man finde $p$ og $q$. For små tal, er det ikke så svært, fx kan man i vores eksemepl nemt se, at $15 = 3 \cdot 5$, men ligesom for beregning af $\phi(m)$, bliver det et meget tungt stykke arbejde for kæmpestore tal. Efterhånden som computere bliver hurtigere, har det være nødvendigt at øge størrelsen af $m$, men indtil nogen kommer op med en banebrydende ny måde at finde $\phi(m)$, er systemet ganske sikkert.

\section{Opgaver}
\begin{exerc} Krypter teksten {\color{blue}{\verb|HEJ MED DIG|}} med Cæsar-kryptering og nøglen $n=2$. \end{exerc}

\begin{exerc} Krypter teksten {\color{blue}{\verb|HEJ MED DIG|}} med Vigin\`{e}re-kryptering hvor nøglen er {\color{green}{\verb|BAD|}}. \end{exerc}

\begin{exerc}
Følgende er krypteret vha. substitution -- altså hvor hvert bogstav erstattes af et bestemt andet bogstav. Hvad er den oprindelige tekst?
\begin{alltt}
\color{red}

QWZVSMW NGBØB VZJQFBØB KLGBRBØ ZW VBØBQ CKHLEWBØB

XGSRBØ ZJMØBXBW ZN RSØEQ KØHB KM ZJVØB KJVQSJVBVB

LØKMØZHHBØ QZHWSVSM BØ ZJWZGGBW ZN NKØQPM LÅ ZW

NØZJZØØB VZJQFBØJBQ FKVBØ KM ABHHBGSMB KLGUQJSJMBØ

RBV ADBGL ZN NZGQFB BHZSGQ KM ADBHHBQSVBØ QWBMBW

HZØFZJW
\end{alltt}
(Hint: Det mest brugte bogstav på dansk er E, og det næstmest almindelige er R.)
\end{exerc}


\begin{exerc} Hvilken rest får man hvis man deler
\[ \text{(i) } 7 \text{ med } 3, \quad \text{(ii) } 13 \text{ med } 7, \quad \text{(iii) } 10 \text{ med } 9 \text{?} \]
\end{exerc}

\begin{exerc} Hvilke af følgende udsagne er sande?
\begin{enumerate}
\item{(i)} $3 \equiv 5 \pmod 2$,
\item{(ii)} $12 \equiv 18 \pmod 4$,
\item{(iii)} $1001 \equiv 100000001 \pmod 5$?
\end{enumerate}
\end{exerc}

\begin{exerc} Beregn $\phi(10), \phi(13)$ og $\phi(143)$. \end{exerc}

\begin{exerc} Vælg $p = 3$ og $q = 11$ og krypter meddelsen ${\color{blue} B} = {\color{blue} 3}$ med $k = 7$, og dekrypter derfter beskeden igen. \end{exerc}

\begin{exerc} Som ond hacker har du opsnappet beskeden ${\color{red} C} = {\color{red} 2}$. Du ved at $m = 55$ og at $k = 7$, da de jo var offentlige. Hvad var den oprindelige besked? \end{exerc}

\newpage
\begin{appendix}
\section{Euklids algoritme}
\subsection{Introduktion}
I afsnittet om RSA skulle vi på et tidspunkt finde $u,v$ således at
\[ ku - \phi(m)v = 1. \]
Husk at vi valgte $k$ således at $k$ og $\phi(m)$ er indbyrdes primiske, og faktisk er det altid muligt, hvis $x$ og $y$ er indbyrdes primiske tal, at finde $u,v$ så
\[ xu + yv = 1. \]
Det gøres ved hjælpe af Euklids algoritme. Algoritmen finder faktisk det største tal $d$, der går op i både $x$ og $y$, og finder hele tal $u$ og $v$ således at
\[ xu + yv = d, \]
og hvis $x$ og $y$ er indbyrdes primiske, er dette tal jo netop $1$.

\subsection{Algoritmen}
Lad os illustrere metoden med et eksempel. Lad $x=42$ og $y=15$, og lav følgende tabel.
\[ \begin{array}{|c|c|c|c|}
\hline
1 & 0 & 42 & \\
\hline
0 & 1 & 15 & \\
\hline
\end{array} \]
I feltet nederst til højre skriver vi nu, hvor mange gange $15$ går op i $42$, i dette tilfælde $2$,
\[ \begin{array}{|c|c|c|c|}
\hline
\color{red}{1} & \color{blue}{0} & \color{yellow}{42} &  \\
\hline
\color{purple}{0} & \color{cyan}{1} & \color{orange}{15} & \color{green}{2} \\
\hline
\end{array} \]
Vi har her givet tallene farve for at vise, hvorledes de bruges til at udregne tallene i næste række. Tallene i næste række findes på følgende måde
\[ {\color{red}{1}} - {\color{green}{2}} \cdot {\color{purple}{0}} = {\color{magenta}{1}}, \]
\[ {\color{blue}{0}} - {\color{green}{2}} \cdot {\color{cyan}{1}} = {\color{violet}{-2}}, \]
\[ {\color{yellow}{42}} - {\color{green}{2}} \cdot {\color{orange}{15}} = {\color{gray}{12}}, \]
og ${\color{gray} 12}$ går ${\color{olive}1}$ gang op i ${\color{orange} 15}$. Tabellen ser nu således ud
\[ \begin{array}{|c|c|c|c|}
\hline
\color{red}{1} & \color{blue}{0} & \color{yellow}{42} &  \\
\hline
\color{purple}{0} & \color{cyan}{1} & \color{orange}{15} & \color{green}{2} \\
\hline
\color{magenta}{1} & \color{violet}{-2} & \color{gray}{12} & \color{olive}{1} \\
\hline
\end{array} \]
Nu rykker vi alle farverne en tak ned,
\[ \begin{array}{|c|c|c|c|}
\hline
\color{black}{1} & \color{black}{0} & \color{black}{42} &  \\
\hline
\color{red}{0} & \color{blue}{1} & \color{yellow}{15} & \color{black}{2} \\
\hline
\color{purple}{1} & \color{cyan}{-2} & \color{orange}{12} & \color{green}{1} \\
\hline
\end{array} \]
og finder tallene i næste række som vi gjorde før
\[ {\color{red}{0}} - {\color{green}{1}} \cdot {\color{purple}{1}} = {\color{magenta}{-1}}, \]
\[ {\color{blue}{1}} - {\color{green}{1}} \cdot ({\color{cyan}{-2}}) = {\color{violet}{3}}, \]
\[ {\color{yellow}{15}} - {\color{green}{1}} \cdot {\color{orange}{12}} = {\color{gray}{3}}, \]
og ${\color{gray} 3}$ går ${\color{olive} 4}$ gang op i ${\color{orange} 12}$. Tabellen ser nu således ud
\[ \begin{array}{|c|c|c|c|}
\hline
\color{black}{1} & \color{black}{0} & \color{black}{42} &  \\
\hline
\color{red}{0} & \color{blue}{1} & \color{yellow}{15} & \color{black}{2} \\
\hline
\color{purple}{1} & \color{cyan}{-2} & \color{orange}{12} & \color{green}{1} \\
\hline
\color{magenta}{-1} & \color{violet}{3} & \color{gray}{3} & \color{olive}{4} \\
\hline
\end{array} \]
Vi udregner rykker nu farverne en tak,
\[ \begin{array}{|c|c|c|c|}
\hline
\color{black}{1} & \color{black}{0} & \color{black}{42} &  \\
\hline
\color{black}{0} & \color{black}{1} & \color{black}{15} & \color{black}{2} \\
\hline
\color{red}{1} & \color{blue}{-2} & \color{yellow}{12} & \color{black}{1} \\
\hline
\color{purple}{-1} & \color{cyan}{3} & \color{orange}{3} & \color{green}{4} \\
\hline
\end{array} \]
og finder tallene i næste række
Tallene i næste række findes som før
\[ {\color{red}{1}} - {\color{green}{4}} \cdot ({\color{purple}{-1}}) = {\color{magenta}{5}}, \]
\[ {\color{blue}{-1}} - {\color{green}{4}} \cdot {\color{cyan}{3}} = {\color{violet}{-14}}, \]
\[ {\color{yellow}{12}} - {\color{green}{4}} \cdot {\color{orange}{3}} = {\color{gray}{0}}, \]
da vi nu er nået ${\color{gray} 0}$ er algoritmen færdig, og tabellen kommer til at se således ud,
\[ \begin{array}{|c|c|c|c|}
\hline
\color{black}{1} & \color{black}{0} & \color{black}{42} &  \\
\hline
\color{black}{0} & \color{black}{1} & \color{black}{15} & \color{black}{2} \\
\hline
\color{red}{1} & \color{blue}{-2} & \color{yellow}{12} & \color{black}{1} \\
\hline
\color{purple}{-1} & \color{cyan}{3} & \color{orange}{3} & \color{green}{4} \\
\hline
\color{magenta}{5} & \color{violet}{-14} & \color{gray}{0} & \\
\hline
\end{array} \]
Tabellen skal nu aflæses på følgende måde:
\begin{itemize}
\item Det største tal, der går op i både $42$ og $15$ er $d = {\color{orange} 3}$.
\item Lad $u = {\color{purple}-1}$ og $v = {\color{cyan} 3}$ idet ${\color{purple}-1} \cdot 42 + {\color{cyan} 3} \cdot 15 = {\color{orange} 3}$. 
\end{itemize}

\subsection{Opgaver}
\begin{exerc} Gennemfør Euklids algoritme for tallene $x = 38$ og $y = 9$.\end{exerc}
\begin{exerc} Gennemfør Euklids algoritme for tallene $x = 32$ og $y = 12$.\end{exerc}
\end{appendix}

\end{document}