Naar inhoud springen

Uitgebreid algoritme van Euclides

Uit Wikipedia, de vrije encyclopedie

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 en bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele en :

,

waarin ggd staat voor grootste gemene deler. De uitbreiding bestaat daarin dat behalve de berekening van de g.g.d. van de getallen en met het algoritme van Euclides, ook de g.g.d. wordt uitgedrukt als gehele lineaire combinatie van en .

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 en geen gemeenschappelijk deler en geldt dus . Omdat volgt direct uit de Bézout identiteit dat de modulaire multiplicatieve inverse van modulo is. Om soortgelijke reden is de modulaire multiplicatieve inverse van modulo . Een publieke sleutel voor RSA encryptie is de modulaire multiplicatieve inverse van de geheime sleutel voor RSA decryptie modulo , waarin en grote priemgetallen zijn.

Bepaal eerst met behulp van het algoritme van Euclides. Schrijf de integer deling van als en de rest als , bijvoorbeeld en . Dan:

Dus . 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:

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

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

,

voor zeker natuurlijk getal . 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 en 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:

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

.

Reduceer mod(19) de termen in bovenstaande Bézout identiteit van ggd(19, 15) = 1 en gebruik en dus

.

Hieruit volgt dat de inverse van 15 is mod(19). Als een geheime sleutel tussen 1 en 19 gewenst is dan kan gebruikt worden dat .