Euclidean algorithm

Euclidean algorithm (tsz. Euclidean algorithms)

1. (informatika) euklideszi algoritmus

Az Euklideszi algoritmus egy hatékony módszer két szám legnagyobb közös osztójának (LNKO) meghatározására. Az algoritmust Euklidész dolgozta ki körülbelül Kr. e. 300-ban, és ma is széles körben használják az informatikában, különösen számelméleti problémákban és titkosítási algoritmusokban.

Az algoritmus azon az elven alapul, hogy két szám legnagyobb közös osztója (LNKO) nem változik, ha a nagyobb számból kivonjuk a kisebbet. Ez a tulajdonság azt eredményezi, hogy az LNKO megtalálható úgy is, hogy az egyik számot a másik maradékával helyettesítjük, és ezt az eljárást ismételjük, amíg az egyik szám nulla nem lesz. A fennmaradó nem nulla szám az LNKO.

Matematikai formában, ha két szám ${\textstyle a}$ és ${\textstyle b}$, akkor: $${\displaystyle \gcd(a,b)=\gcd(b,a\mod b)}$$ Ha ${\textstyle b=0}$, akkor ${\textstyle \gcd(a,b)=a}$.

Az algoritmus iteratív és rekurzív módon is megvalósítható. Az alábbiakban mindkét verziót bemutatjuk.

Az iteratív verzió egy egyszerű ciklussal valósítja meg az algoritmust:

#include <iostream>

int euclidean_gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a, b;
    std::cout << "Adja meg az első számot: ";
    std::cin >> a;
    std::cout << "Adja meg a második számot: ";
    std::cin >> b;
    
    std::cout << "LNKO: " << euclidean_gcd(a, b) << std::endl;
    return 0;
}

A rekurzív verzió az alábbi módon néz ki:

#include <iostream>

int euclidean_gcd_recursive(int a, int b) {
    if (b == 0)
        return a;
    return euclidean_gcd_recursive(b, a % b);
}

int main() {
    int a, b;
    std::cout << "Adja meg az első számot: ";
    std::cin >> a;
    std::cout << "Adja meg a második számot: ";
    std::cin >> b;
    
    std::cout << "LNKO: " << euclidean_gcd_recursive(a, b) << std::endl;
    return 0;
}

Az Euklideszi algoritmus hatékonysága rendkívül jó. A legrosszabb esetben az algoritmus futási ideje ${\textstyle O(\log N)}$, ahol ${\textstyle N}$ a nagyobbik bemeneti szám. Ez azt jelenti, hogy a számjegyek számának növekedésével az algoritmus futási ideje arányosan nő, de nagyon lassan.

Példa erre a Fibonacci-számok használata: ha ${\textstyle a}$ és ${\textstyle b}$ egymást követő Fibonacci-számok, akkor az algoritmus maximális számú lépést tesz meg.

A kiterjesztett Euklideszi algoritmus nemcsak az LNKO-t határozza meg, hanem megoldja az alábbi egyenletet is: $${\displaystyle ax+by=\gcd(a,b)}$$ Ez különösen fontos a számelméletben és a titkosítási algoritmusokban (például az RSA-ban).

Íme egy C++ implementáció:

#include <iostream>

int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

int main() {
    int a, b, x, y;
    std::cout << "Adja meg az első számot: ";
    std::cin >> a;
    std::cout << "Adja meg a második számot: ";
    std::cin >> b;
    
    int gcd = extended_gcd(a, b, x, y);
    std::cout << "LNKO: " << gcd << ", x: " << x << ", y: " << y << std::endl;
    return 0;
}

Az Euklideszi algoritmust számos helyen használják: - Titkosítás: Az RSA algoritmusban a nyilvános és privát kulcsok kiszámításánál. - Számelmélet: Egész számok közötti relációk és oszthatósági problémák megoldására. - Kriptográfia: Moduláris inverz számításoknál. - Számítógépes grafika: Például a legnagyobb közös osztó használatával képarányok egyszerűsítésére.

Vegyünk egy példát az algoritmus működésére: Két szám: ${\textstyle a=252}$, ${\textstyle b=105}$

Lépések az iteratív módszerrel: 1. ${\textstyle 252\mod 105=42}$ → új ${\textstyle a=105}$, új ${\textstyle b=42}$ 2. ${\textstyle 105\mod 42=21}$ → új ${\textstyle a=42}$, új ${\textstyle b=21}$ 3. ${\textstyle 42\mod 21=0}$ → LNKO = 21

Tehát az LNKO 21.

Az Euklideszi algoritmus egy gyors és hatékony módszer az LNKO meghatározására. Az iteratív és rekurzív megvalósítás egyaránt könnyen alkalmazható, és a kiterjesztett változat további hasznos információkat nyújt az egész számok közötti lineáris egyenletek megoldásához.

• Euclidean algorithm - Szótár.net (en-hu)
• Euclidean algorithm - Sztaki (en-hu)
• Euclidean algorithm - Merriam–Webster
• Euclidean algorithm - Cambridge
• Euclidean algorithm - WordNet
• Euclidean algorithm - Яндекс (en-ru)
• Euclidean algorithm - Google (en-hu)
• Euclidean algorithm - Wikidata
• Euclidean algorithm - Wikipédia (angol)