\require{AMSmath}

Dit is een reactie op vraag 34397

Re: Modulo rekenen cryptografie

Als ik in plaats van 4, 5 zou nemen zou het dan wel lukken?

b.v.d. Jop

Jop
Leerling bovenbouw havo-vwo - woensdag 23 februari 2005

Antwoord

dag Jop,

Ja, dat klopt.
In het algemeen geldt: als a en b geen gemeenschappelijke delers hebben (ofwel de grootste gemene deler van a en b is 1, als dat je wat zegt), dan is er een getal D te vinden zodat
a·D = 1 modulo b
In dit speciale geval kun je door proberen wel een waarde voor D vinden. Bedenk dat 2·22 = 44 en dat is 1 minder dan 45, wat weer een veelvoud van 5 is.
Voor algoritmes om dergelijke veelvouden te vinden kun je binnen Wisfaq zoeken op het algoritme van Euclides. Zie bijvoorbeeld
Het uitgebreide algoritme van Euclides

Anneke
woensdag 23 februari 2005

©2001-2024 WisFaq