4. Der erweiterte Euklidische Algorithmus

Der erweiterte Euklidische Algorithmus

  • K

    Hallo Leute,

    ich habe zwei Implementierungen vom erweiterten euklidischen Algorithmus. Die eine (im folgenden Programm mit der Funktion "euklid" bezeichnet) stammt von Prof. Hauck und funktioniert soweit. Die andere stammt aus dem Knuth Band 2 (im folgenden Programm deshalb als "knuth" bezeichnet"). Leider liefert letztere nicht immer das richtige Ergebnis, ist aber effizienter, weil sie nur eine Division benötigt, im Gegensatz zur ersten, die drei Divisionen benötigt pro Schleifendurchlauf. (Für mich ist das wichtig, weil ich das später mit VHDL auf einem FPGA implementieren möchte).
    Meine Frage ist also: Wo ist der Fehler in meiner Implementierung von Knuth?

    Es geht dabei darum die modulare Inverse einer Zahl x zu finden, also in diesem Fall a, sodass a ≡ x mod n ist. Oder anders ausgedrückt: 1 ≡ x*a mod n

    Hier das Prog in Cpp:

    #include <iostream>

using namespace std;

int knuth(int r, int s)
{
    int v,u,q,temp,n;
    n=s;
    v=0;
    u=1;
    while(r!=0)
    {
        q=s/r;
        temp=s-q*r;
        s=r;
        r=temp;
        temp=v-q*r;
        v=u;
        u=temp;
    }
    if(v<0) v+=n;
    return v;
}

int euklid(int x, int b)
{
    int s,s2,t1,s1,t,t2,temp,g,r,y;
    s=s2=t1=0;
    s1=t=t2=1;
    y=b;
    while(temp!=0)
    {
        g=x/y;
        r=x%y;
        s=s1-g*s2;
        t=t1-g*t2;
        s1=s2;
        s2=s;
        t1=t2;
        t2=t;
        x=y;
        y=r;
        temp=x%y;
    }
    if (s<0) s+=b;
    return s;
}

int main()
{
    int r,s;
    cout << "x eingeben: ";
    cin >> r;
    cout << "n eingeben: ";
    cin >> s;
    cout << "Inverse laut Knuth: " << knuth(r,s) << endl;
    cout << "Inverse laut Euklid: " << euklid(r,s) << endl;
    return 0;
}
    0
  • M

    Was wäre denn ein Beispiel, wo was Falsches rauskommt?

    0
  • K

    Schaue ich mir http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm an, so sehe ich nur 2 Divisionen:

    quotient := a div b
  (a, b) := (b, a mod b)

    Die zweite (a mod b) kann eingespart werden, da man das ganzzahlige Vielfache (a div b) bereits hat: a = b * q + r mit q = a div b und r = a mod b => r = a - b * q. Alle Angaben ohne Gewaehr. Jedoch ist dieser Algorithmus eher sequentiell, vielleicht gibt es eine parallele Variante die besser fuer FPGAs geeignet ist.

    Bei Wikipedia fehlt die Zeile if(v<0) v+=n; und dort wird mit 4 lokalen Variablen gearbeitet, nicht nur mit zwei (temp zaehlt nicht). Naja, braucht man wahrscheinlich nicht. In deinem Fall wuerde ich noch sicherstellen, dass s > r beim Funktionsaufruf ist.

    0
Anmelden zum Antworten