Uitgebreid algoritme van Euclides

Het uitgebreide algoritme van Euclides is een uitbreiding van het algoritme van Euclides, dat niet alleen de grootste gemene deler ggd van twee natuurlijke getallen $a$ en $b$ bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele $x$ en $y$:

$ax+by=\mathrm{g}\mathrm{g}\mathrm{d}(a,b)$

De uitbreiding bestaat daarin dat behalve de berekening van de $\mathrm{g}\mathrm{g}\mathrm{d}$ van de getallen $a$ en $b$ met het algoritme van Euclides, ook de $\mathrm{g}\mathrm{g}\mathrm{d}$ wordt uitgedrukt als gehele lineaire combinatie van $a$ en $b$. Het bewijs van de stelling van Bachet-Bézout steunt op de constructie door het algoritme.

RSA algoritme

Een veelgebruikte toepassing is het RSA-algoritme, meestal afgekort tot RSA, in de encryptie. Het is daarin op een gegeven moment nodig de geheime sleutel $d$ te berekenen als modulaire inverse van de publieke sleutel $e$, dat wil zeggen dat $d$ door

$e\times d\equiv 1mod(n)$,

wordt gegeven voor zeker natuurlijk getal $n$. Deze geheime sleutel kan met het algoritme van Euclides worden berekend. Om dit te laten zien aan de hand van het voorbeeld van een ontbinding van Bézout, merken we op dat in RSA $e$ en $n$ geen gemeenschappelijke delers hebben. Het is een voorwaarde voor het bestaan van een geheime sleutel, dat $e$ en $n$ onderling ondeelbaar zijn.

Voorbeeld

Neem het voorbeeld met de getallen 1140 en 900. Bepaal eerst $\mathrm{g}\mathrm{g}\mathrm{d}(1140,900)$ met behulp van het algoritme van Euclides. Schrijf de deling van $n\ge m$ als $n//m=\lfloor n/m\rfloor$ en de rest als $n\mathrm{m}\mathrm{o}\mathrm{d}m$, bijvoorbeeld $7//3=2$ en $7\mathrm{m}\mathrm{o}\mathrm{d}3=1$. Dan:

$\begin{array}{cccccccccc}& 1140& =& (1140//900)\times 900& +& 1140\mathrm{m}\mathrm{o}\mathrm{d}900& =& 1\times 900& +& 240\\ & 900& =& (900//240)\times 240& +& 900\mathrm{m}\mathrm{o}\mathrm{d}240& =& 3\times 240& +& 180\\ & 240& =& (240//180)\times 180& +& 240\mathrm{m}\mathrm{o}\mathrm{d}180& =& 1\times 180& +& 60\\ & 180& =& (180//60)\times 60& +& 180\mathrm{m}\mathrm{o}\mathrm{d}60& =& 3\times 60& +& 0\end{array}$

Dus $\mathrm{g}\mathrm{g}\mathrm{d}(1140,900)=60$. Schrijf nu de $\mathrm{g}\mathrm{g}\mathrm{d}$ als lineaire combinatie van 1140 en 900. Bereken daartoe de $\mathrm{g}\mathrm{g}\mathrm{d}$ in omgekeerde volgorde:

$\begin{array}{ccc}60& =& 240-1\times 180\\ 180& =& 900-3\times 240& & & 60& =& 240-1\times (900-3\times 240)& =& -1\times 900+4\times 240\\ 240& =& 1140-1\times 900& & & 60& =& -900+4\times (1140-1\times 900)& =& 4\times 1140-5\times 900\end{array}$

Daarmee is $\mathrm{g}\mathrm{g}\mathrm{d}(1140,900)=60$ geschreven als gehele lineaire combinatie van 1140 en 900. Deze tweede stap wordt de ontbinding van Bézout genoemd.

Als de getallen in de $\mathrm{g}\mathrm{g}\mathrm{d}(1140,900)$ door 60 worden gedeeld resulteert dit in:

$1=4\times 19-5\times 15$

Neem nu het voorbeeld dat de publieke sleutel $e$ = 15 en $n$ = 19, deze getallen hebben inderdaad geen gemeenschappelijke deler. De geheime sleutel $d$ wordt bepaald door

$15\times d\equiv 1mod(19)$.

Reduceer $\mathrm{m}\mathrm{o}\mathrm{d}19$ de termen in de bovenstaande ontbinding van $\mathrm{g}\mathrm{g}\mathrm{d}(19,15)=1$ en gebruik $4\times 19\equiv 0mod(19)$ dus

$15\times (-5)\equiv 1mod(19)$.

Hieruit volgt dat $d=-5$ de inverse van 15 is $\mathrm{m}\mathrm{o}\mathrm{d}19$. Als er een geheime sleutel tussen 1 en 19 wordt gezocht, kan het worden gebruikt dat $d=-5\equiv 14mod(19)$.