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 ${\displaystyle a}$ en ${\displaystyle b}$ bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele ${\displaystyle x}$ en ${\displaystyle y}$:

${\displaystyle 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 ${\displaystyle a}$ en ${\displaystyle b}$ met het algoritme van Euclides, ook de g.g.d. wordt uitgedrukt als gehele lineaire combinatie van ${\displaystyle a}$ en ${\displaystyle 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 ${\displaystyle a}$ en ${\displaystyle b}$ geen gemeenschappelijk deler en geldt dus ${\displaystyle \mathrm {ggd} (a,b)=1}$. Omdat ${\displaystyle b\equiv 0{\bmod {(}}b)}$ volgt direct uit de Bézout identiteit dat ${\displaystyle x}$ de modulaire multiplicatieve inverse van ${\displaystyle a}$ modulo ${\displaystyle b}$ is. Om soortgelijke reden is ${\displaystyle y}$ de modulaire multiplicatieve inverse van ${\displaystyle b}$ modulo ${\displaystyle a}$. Een publieke sleutel voor RSA encryptie is de modulaire multiplicatieve inverse van de geheime sleutel voor RSA decryptie modulo ${\displaystyle (p-1)(q-1)}$, waarin ${\displaystyle p}$ en ${\displaystyle q}$ grote priemgetallen zijn.