Euklidischer Algorithmus

[programmer13]

public class ExtendedEuklid
{
public int g, u, v;
public ExtendedGcd(int a, int b)

{
ExtendetEuklid(a, b);
}

public void ExtendetEuklid(int a, int b)
{
int q, r, s, t;u=t=1;v=s=0;
while (b>0)
{
q=a/b;
r=a-q*b; a=b; b=r;
r=u-q*s; u=s; s=r;
r=v-q*t; v=t; t=r;
}
g=a;
}

Hallo zusammen,

hatte das Thema hier schon einmal reingestellt, konnte aber kurz danach nicht mehr auf mein Account zugreifen. Wie ihr schon seht, ist das der erweiterte euklidische Algorithmus.
Zu meiner Frage: Ich verstehe nicht, was das Extented bedeutet.
Der Quelltextist aus dem Netz. Könnt ihr mir ihn evtl. zeilenweise ausführlich erklären?
Ich bekomms nämlich alleine nicht hin.
Würdet ihr Sachen anders schreiben bzw. einfacher?
Wäre euch sehr dankbar

 

[Neele]

Hallo,

zunächst wäre es hilfreich, wenn du

• jeden Befehl in eine Zeile schreiben würdest, also hinter jedes Semikolon ein Zeilenumbruch;
• die Zeilen entsprechend einrücken würdest;
• lauffähigen Code hochladen würdest (hier fehlt zum Beispiel eine Main-Methode, mit der man den Code testen kann);
• den alten Thread verlinken würdest, für den Fall, dass es da noch Antworten gibt.

Das erhöht die Chancen auf eine Antwort erheblich.

Der Code sähe dann so aus:

public class ExtendedEuklid {
  public int g, u, v;

  public ExtendedGcd(int a, int b) {
    ExtendetEuklid(a, b);
  }

  public void ExtendetEuklid(int a, int b) {
    int q, r, s = 0, t = 1;
    int u = t;
    int v = s;
    while (b > 0) {
    q = a / b;
    r = a - q * b; 
    a = b;  
    b = r;
    r = u - q * s; 
    u = s;  
    s = r;
    r = v - q * t;  
    v = t; 
    t = r;
  }
  g = a;
}

Das "Extended" steht für "erweitert" und soll lediglich klar machen, dass es sich um den erweiterten euklidischen Algorithmus handelt. Es ist nur der Name der Methode und hat keine Auswirkungen darauf, was passiert.

Vielleicht solltest du dir auch das hier: http://www.java-forum.org/forum-faq-beitraege/7407-man-fragen-richtig-stellt.html mal durchlesen, um deine Chance auf hilfreiche Antworten zu erhöhen.

Liebe Grüße, Neele

 

[Tobse]

Ich kann Neele nur zustimmen. Aber mal abgesehen davon, ist der Code auch mit main() Methode alles andere als Lauffähig; der Compiler wird jeden mit Fehlermeldungen bombardieren, der versucht, das ding zu kompilieren. Der Code ist Semanisch total sinnlos. Wo hast du diesen Schwachsinn her?

 

[programmer13]

Hallo,

Gebt bei Google "Erweiterter euklidischer Algorithmus Java Programm" ein, und der zweite Treffer zeigt den obigen Quelltext.
Ich weiß nicht, ob man einfach die Seite verlinken darf.

Der andere Thread handelte vom einfachen euklidischen Algorithmus, bringt uns also nicht wirklich weiter.

 

[Neele]

"Der zweite Eintag bei google" - das funktioniert leider häufig nicht, siehe hier: Raus aus der Filterblase Ihrer Suchmaschine!

Statt einfach blind etwas aus dem Internet zu kopieren, wie wäre es, wenn du den Code, so gut du kannst, selber schreibst, vllcht auf Basis dessen, was in dem anderen Thread herausgekommen ist, oder als Pseudocode? Davon ausgehend könntest du sehr viel konkretere Fragen stellen können als nur "was tut das?" und würdest ganz nebenbei noch etwas lernen. Denn wie der erweiterte euklidische Algorithmus funktioniert, hast du doch verstanden, oder?

LG, Neele

 

[programmer13]

Ich habe nochmals im Netz geforscht, und folgendes gefunden:

[B]public[/B] [B]class[/B] RSA_dSuche
{
  [B]public[/B] [B]int[/B] sucheD ([B]int[/B] p, [B]int[/B] q, [B]int[/B] e)
  [I]// Probierverfahren: v wird solange erhöht, bis d=(1 + v*phi)/e ganzzahlig ist[/I]
  {
    [B]int[/B] phi = (p-1)*(q-1);
    [B]int[/B] v = 0;
    [B]do[/B] {
      v++;
    } [B]while[/B] ((1 + v*phi) mod e != 0);
    [B]return[/B] ((1 + v*phi)/e);   [I]// = d[/I]
  }

  [B]public[/B] [B]int[/B] sucheD ([B]int[/B] p, [B]int[/B] q, [B]int[/B] e)
  [I]// nach dem Erweiterten Euklid-Algorithmus (iterativ)[/I]
  [I]// r, s, t  = aktuelle Werte, stützen sich auf/iterativ aus Vor- und Vorvorgänger![/I]
  [I]// r_1, s_1, t_1 = Vorgänger: eine Zeile höher/ein Durchlauf früher,[/I]
  [I]// r_2, s_2, t_2 = Vorvorgänger: zwei Zeilen höher/zwei Durchläufe früher,[/I]
  {
    [B]int[/B] phi = (p-1)*(q-1);
    [B]int[/B] r_2 = phi;     [B]int[/B] s_2 = 0;    [B]int[/B] t_2 = 1;   [I]// Startwerte[/I]
    [B]int[/B] r_1 = e;       [B]int[/B] s_1 = 1;    [B]int[/B] t_1 = 0;
    [B]int[/B] r, b, s, t;
    [B]do[/B]
    {
      r = r_2 mod r_1;                   [I]// aktuelle Werte aus Vorgängern berechnen[/I]
      b = r_2 / r_1;
      s = s_2 - s_1*b;
      t = t_2 - t_2*b;

      r_2 = r_1;    s_2 = s_1;    t_2 = t_1; [I]// neue Werte werden zu alten[/I]
      r_1 = r;     s_1 = s;     t_1 = t;
    } [B]while[/B] (r > 1);
    [B]int[/B] d = s;                         [I]// Bestimmung von d[/I]
    [B]while[/B] (d < 0)    [I]// falls s noch nicht positiv, d = s + u*phi, u so groß wie nötig[/I]
    {
      d = d + phi;
    }
    [B]return[/B] (d);
  }  
}

Könnt ihr mir es jetzt erklären?
Ja, ich weiß wie der euklidische Algorithmus funktioniert, aber bekomme es beim Besten Gewissen nicht hin.
Am Besten Zeile nach Zeile, damit ich es verstehe.
Ich habe bereits selbst probiert, es zu programmieren, komme aber nicht weit.

 

[VfL_Freak]

Moin,

hier mal zwei etwas ausführlichere Erklärungen, die ich über Google fand (habe jetzt keine große Lust, das alles abzutippen :bae

http://ls11-www.cs.uni-dortmund.de/people/rahmann/teaching/ss2008/EleganteAlgorithmen/skript.pdf
Erweiterter euklidischer Algorithmus

Gruß Klaus

 

[programmer13]

Hallo,

Habe nun einen richtigen und lauffähigen Quelltext gefunden, den ich verwenden möchte.

[B]public[/B] [B]int[/B] sucheD ([B]int[/B] p, [B]int[/B] q, [B]int[/B] e)
  [I]// r, s, t  = aktuelle Werte, kommen aus Vor- und Vorvorgänger[/I]
  [I]// r_1, s_1, t_1 = Vorgänger: ein Durchlauf höher,[/I]
  [I]// r_2, s_2, t_2 = Vorvorgänger: zwei Durchläufe früher,[/I]
  {
    [B]int[/B] phi = (p-1)*(q-1);
    [B]int[/B] r_2 = phi;     [B]int[/B] s_2 = 0;   [B]int[/B] t_2 = 1;   [I]// Startwerte[/I]
    [B]int[/B] r_1 = e;       [B]int[/B] s_1 = 1;    [B]int[/B] t_1 = 0;
    [B]int[/B] r, b, s, t;
    [B]do[/B]
    {
      r = r_2 % r_1;                   [I]// aktuelle Werte aus Vorgängern berechnen[/I]
      b = r_2 / r_1;
      s = s_2 - s_1*b;
      t = t_2 - t_2*b;

      r_2 = r_1; s_2 = s_1; t_2 = t_1; [I]// neue Werte werden zu alten[/I]
      r_1 = r;   s_1 = s;   t_1 = t;
    }  
[B]                 while[/B] (r > 1);
    [B]int[/B] d = s;                         [I]// Bestimmung von d[/I]
    [B]while[/B] (d < 0)    [I]// falls s noch nicht positiv, d = s + u*phi, u so groß wie nötig[/I]
    {
      d = d + phi;
    }
    [B]return[/B] (d);
  }  
}

% ist sowas wie Modulo, also der Rest der Teilung.

Ich kann es mir leider nicht genau erklären.
Könnt ihr es mir erklären?
Wäre auch für jeden Tipp dankbar.

Was genau errechnet dieser Abschnitt?

 r = r_2 % r_1;                   [I]// aktuelle Werte aus Vorgängern berechnen[/I]
      b = r_2 / r_1;
      s = s_2 - s_1*b;
      t = t_2 - t_2*b;

      r_2 = r_1; s_2 = s_1; t_2 = t_1; [I]// neue Werte werden zu alten[/I]
      r_1 = r;   s_1 = s;   t_1 = t;
    }

r= phi mod e ??
b =phi / e ??

 

[Denni173]

Ich frage mich was Du eigentlich berechnen möchtest mit diesem Programm bzw. zu welchen Zweck?
Es erscheint mir seltsam das du dich mit den Euklidischen Algorthmen befasst, ohne solides Basiswissen in der Mathematik!

r= phi mod e (r = Pi modulo e ) heisst nichts anderes als das die Zahl Pi (3.1415... durch e dividiert wird und der Rest dieser Division dem Wert r übergeben wird!

Wenn es einen Sinn für Dich ergeben soll wirst du diesen Algorithmus selbst implementieren müssen.
Das geht bereits schon mit den Java-Basics. Dort wird auch der Modulo Operant erklärt.

So wird dir leider keiner helfen können oder wollen, Sorry !

Greetings D.

 

[Tobse]

r= phi mod e [... ] heisst nichts anderes als das die Zahl Pi (3.1415... durch e dividiert wird und der Rest dieser Division dem Wert r übergeben wird!

So sehr ich dir mit dem Posting grundlegend Recht gebe, das ist totaler Bullshit. Man siehe Posting #8 im Code, 7. Zeile: phi = (p-1)*(q-1)