Uitgebreid algoritme van Euclides

Het uitgebreide algoritme van Euclides is een uitbreiding van het algoritme van Euclides, die niet alleen de grootste gemene deler g.g.d. 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 {ggd} (a,b)$,

waarin ggd staat voor grootste gemene deler. De uitbreiding bestaat daarin dat behalve de berekening van de g.g.d. van de getallen $a$ en $b$ met het algoritme van Euclides, ook de g.g.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.

Aan de hand van een voorbeeld zal duidelijk worden hoe het algoritme tot stand komt.

Een veelgebruikte toepassing van het algoritme is de RSA publiekesleutelmethode voor encryptie. In RSA hebben $a$ en $b$ geen gemeenschappelijk deler en geldt dus $\mathrm {ggd} (a,b)=1$. Omdat $b\equiv 0{\bmod {(}}b)$ volgt direct uit de Bézout identiteit dat $x$ de modulaire multiplicatieve inverse van $a$ modulo $b$ is. Om soortgelijke reden is $y$ de modulaire multiplicatieve inverse van $b$ modulo $a$. Een publieke sleutel voor RSA encryptie is de modulaire multiplicatieve inverse van de geheime sleutel voor RSA decryptie modulo $(p-1)(q-1)$, waarin $p$ en $q$ grote priemgetallen zijn.

Voorbeeld

Bepaal eerst $\mathrm {ggd} (1140,900)$ met behulp van het algoritme van Euclides. Schrijf de integer deling van $n\geq m$ als $n//m=\lfloor n/m\rfloor$ en de rest als $n\%m$, bijvoorbeeld $7//3=2$ en $7\%3=1$. Dan:

${\begin{matrix}&1140&=&(1140//900)\times 900&+&1140\%900&=&1\times 900&+&240\\&900&=&(900//240)\times 240&+&900\%240&=&3\times 240&+&180\\&240&=&(240//180)\times 180&+&240\%180&=&1\times 180&+&60\\&180&=&(180//60)\times 60&+&180\%60&=&3\times 60&+&0\\\end{matrix}}$

Dus $\mathrm {ggd} (1140,900)=60$. Schrijf nu de g.g.d. als lineaire combinatie van 1140 en 900 (de Bézout ontbinding). Doe daartoe berekening van de g.g.d. in omgekeerde volgorde:

${\begin{matrix}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{matrix}}$

Daarmee is ggd(1140,900) = 60 uitgedrukt als gehele lineaire combinatie van 1140 en 900.

Toepassing

In het RSA algoritme voor asymmetrische cryptografie is het nodig de geheime sleutel $d$ te berekenen als modulaire inverse van de publieke sleutel $e$, dat wil zeggen dat $d$ is gegeven door

$e\times d\equiv 1{\bmod {(}}n)$,

voor zeker natuurlijk getal $n$. Het uitgebreide algoritme van Euclides kan deze modulaire inverse leveren. Om dit te laten zien aan de hand van het voorbeeld van een Bézout ontbinding uit de vorige sectie, merken we op dat in RSA $e$ en $n$ geen gemeenschappelijke delers hebben; dit relatief priem zijn is een voorwaarde voor het bestaan van een modulaire inverse. Als alle getallen in de Bézout identiteit van ggd(1140, 900) gedeeld worden door 60 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. Nu wordt de geheime sleutel $d$ bepaald door

$15\times d\equiv 1{\bmod {(}}19)$.

Reduceer mod(19) de termen in bovenstaande Bézout identiteit van ggd(19, 15) = 1 en gebruik $4\times 19\equiv 0{\bmod {(}}19)$ en dus

$15\times (-5)\equiv 1{\bmod {(}}19)$.

Hieruit volgt dat $d=-5$ de inverse van 15 is mod(19). Als een geheime sleutel tussen 1 en 19 gewenst is dan kan gebruikt worden dat $d=-5\equiv 14{\bmod {(}}19)$.