Laajennettu euklidinen algoritmi

Laajennettu euklidinen algoritmi on algoritmi, jolla voidaan laskea sellaiset kokonaisluvut xxx ja yyy, että

ax+by=gcd(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b)

edellyttäen, että aaa ja bbbbb.

Tällaisten kokonaislukujen olemassaolo taataan Bézout’n lemman avulla.

Lisätty Eukleideen algoritmi voidaan nähdä modulaarisen eksponentioinnin käänteislukuna.

Kääntämällä Eukleideen algoritmin askeleet toisin päin on mahdollista löytää nämä kokonaisluvut xxx ja yyy. Koko idea on aloittaa GCD:stä ja edetä rekursiivisesti taaksepäin. Tämä voidaan tehdä käsittelemällä lukuja muuttujina, kunnes saadaan lauseke, joka on alkulukujen lineaarinen yhdistelmä. Teemme tämän edellä käyttämämme esimerkin avulla.

Aloitamme GCD:stä. Kirjoitamme sen uudelleen kahden edellisen termin suhteen:

2=26-2×12.2 = 26 – 2 \times 12 .2=26-2×12.

Korvaamme 121212:n ottamalla edellisen rivimme (38=1×26+12)(38 = 1 \ kertaa 26 + 12)(38=1×26+12) ja kirjoittamalla sen 12:n termein:

2=26-2×(38-1×26).2 = 26 – 2 \ kertaa (38 – 1\ kertaa 26). 2=26-2×(38-1×26).

Kerätään samankaltaiset termit, 262626:t, ja saadaan

2=3×26-2×38.2 = 3 \ kertaa 26 – 2 \ kertaa 38. 2=3×26-2×38.

Kertaa prosessi:

2=3×(102-2×38)-2×38.2 = 3 \times (102 – 2 \times 38) – 2 \times 38.2=3×(102-2×38)-2×38.

Lopputulos on vastauksemme:

2=3×102-8×38.2 = 3 \times 102 – 8 \times 38.2=3×102-8×38.

Siten xxx ja yyy ovat 333 ja -8-8-8.

Etsitään kaksi kokonaislukua aaa ja bbb siten, että 1914a+899b=gcd(1914,899).1914a + 899b = \gcd(1914,899). 1914a+899b=gcd(1914,899).

Käytä ensin Eukleideen algoritmia GCD:

1914=2×899+116899=7×116+87116=1×87+2987=3×29+0.\begin{aligned}1914 &= 2\ kertaa 899 + 116 \\\899 &= 7 \ kertaa 116 + 87 \\\116 &= 1 \ kertaa 87 + 29 \\\87 &= 3 \ kertaa 29 + 0.\end{aligned}191489911687=2×899+116=7×116+87=1×87+29=3×29+0.

Tästä viimeinen nollasta poikkeava jäännös (GCD) on 292929.Nyt käytämme laajennettua algoritmia:

29=116+(-1)×8787=899+(-7)×116.\begin{aligned} 29 &= 116 + (-1)\times 87\\\87 &= 899 + (-7)\times 116.\end{aligned}2987=116+(-1)×87=899+(-7)×116.

Korvaamalla 878787 ensimmäisessä yhtälössä saadaan

29=116+(-1)×(899+(-7)×116)=(-1)×899+8×116=(-1)×899+8×(1914+(-2)×899)=8×1914+(-17)×899=8×1914-17×899.\begin{aligned}29&= 116 + (-1)\times (899 + (-7)\times 116) \\&= (-1)\times 899 + 8\times 116 \\\&= (-1)\times 899 + 8\times ( 1914 + (-2)\times 899 )\\\&= 8\times 1914 + (-17) \times 899 \\\&= 8\times 1914 – 17 \times 899.\end{aligned}29=116+(−1)×(899+(−7)×116)=(−1)×899+8×116=(−1)×899+8×(1914+(−2)×899)=8×1914+(−17)×899=8×1914−17×899.

Koska nyt kirjoitimme GCD:n kahden kokonaisluvun lineaarikombinaationa, lopetamme algoritmin ja päätämme

a=8,b=-17. □ a = 8, b =-17. \ _\neliöa=8,b=-17. □