Euklidův algoritmus
Euklidův algoritmus (EA) slouží k nalezení největšího společného dělitele (NSD) dvou přirozených
čísel pomocí zbytků po celočíselném dělení. Tento algoritmus je pojmenován po starověkém řeckém
filozofovi Eukleidovi, který ho popsal ve svém díle Základy přibližně 300 let př.n.l. Jeho rozšířená
verze se používá k nalezení multiplikativní inverze čísla x mod (n).
Formulace EA vypadá následovně. Máme daná dvě přirozená čísla a0 > a1. Postupně počítáme ai+1 = ai-1 (mod ai). Ve chvíli, kdy an+1 = 0, algoritmus skončí a pak an = NSD (a0, a1).
Příklad: Najít NSD(120,45)
a0 = 120
a1 = 45
a2 = 120 (mod 45) = 30
a3 = 45 (mod 30) = 15 = NSD (120,45)
a4 = 30 (mod 15) = 0
Rozšířený Euklidův algoritmus
Rozšířená varianta Euklidova algoritmu slouží k nalezení multiplikativního inverzního prvku. Ten
existuje, jenom pokud NSD (a, n) = 1 (jinými slovy a, n musí být nesoudělná).
Pro inverzní prvek platí:
a · a-1 = 1 (mod n). Každé číslo
ai+1 je celočíselnou lineární kombinací hodnot a0 a a1:
ai+1 = x · a1 + y · a0. Členy ai+1 počítáme
tak dlouho, dokud není ai+1 = 1. Protože y · a0 mod (a0) = 0,
je hledanou inverzí číslo x: x · a1 = 1 mod (a0).
Příklad: Najít multiplikativní inverzní prvek k 61 (mod 97)
a0 = 97
a1 = 61
a2 = 36 = 97 - 61
a3 = 25 = 61 - 36 = 61 - (97 - 61) = 2·61 - 97
a4 = 11 = 36 - 25 = (97 - 61) - (2·61 - 97) = 2·97 - 3·61
a5 = 3 = 25 - 2·11 = (2·61 - 97) - 2·(2·97 - 3·61) = 8·61 - 5·97
a6 = 2 = 11 - 3·3 = (2·97 - 3·61) - 3·(8·61 - 5·97) = 17·97 - 27·61
a7 = 1 = 3 - 2 = (8·61 - 5·97) - (17·97 - 27·61) = 35·61 - 22·97 => 35·61 = 1 (mod 97)
Multiplikativní inverzní prvek k 61 je x = 35 (mod 97), pokud x vyjde záporné přičte se k němu a0.
Algoritmus na výpočet NSD (a0, a1) a inverze k a1 (mod a0) pokud NSD=1
Komentáře k článku