Erweiterter euklidischer Algorithmus

Der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers und der erweiterte euklidische Algorithmus zur Darstellung des größten gemeinsamen Teilers als Linearkombination der Variablen sind wohlbekannt.

Ich finde aber die übliche Darstellung der Berechnung in Tabellenform unübersichtlich, egal ob mit Rückwärtseinsetzen oder mit Vorwärtsberechnung, und die Darstellung als Produkt von Matrizen noch mehr.

In meiner Darstellung reduziere ich die Berechnung in Tabellenform auf die minimal nötigen Variablen s, t und r und füge dann ein paar Felder ein, um aus einer Tabellenzeile eine Gleichung zu machen. Jede Zeile berechnet eine Linearkombination der Parameter a und b.

Die ersten beiden Gleichungen werden trivial aus den Parametern a und b erzeugt. Danach wird die n-te Gleichung berechnet, indem jeweils ein Vielfaches der n-1-ten Gleichung von der n-2-ten Gleichung subtrahiert wird. Der Faktor ist der ganzzahlige Quotient der Werte der beiden vorausgehenen Gleichungen.

Ich hoffe, dass durch Einfärbung und Fettschrift die Felder der interaktiven Berechnung aus sich heraus verständlich sind. Die letzte Zeile ist die gewünschte Darstellung des größten gemeinsamen Teilers als Linearkombination der Parameter.

Interaktive Berechnung

Zeile Berechnung  ± s * a  ∓ t * b  =  r Division

Algorithmus

  • Die ersten beiden Zeilen stellen die Parameter als triviale Linearkombinationen aus sich selbst dar.
  • Für die nächsten Schritte:
    • Der Quotient q der beiden jeweils letzten r-Werte wird bestimmt.
    • Ist der Rest der ganzzahligen Division 0, terminiert die Schleife.
    • Ansonsten wird das q-fache der Werte von s, t und r der letzten Zeile von denen der vorletzten Zeile subtrahiert.
  • Da immer nur die beiden letzten Zeilen für die Berechnung gebraucht werden, reichen uns statt s1, s2, s3, … nur 2 Variablen so und se, mit o für odd und e für even.

Normale Berechnung:

so ≔ 1; to ≔ 0; ro ≔ a
se ≔ 0; te ≔ 1; re ≔ b
loop
  if re = 0 then return (so, to, ro)
  q ≔ ⌊ro / re⌋
  so ≔ so - q * se
  to ≔ to - q * te
  ro ≔ ro - q * re (alternativ: ro ≔ ro mod re)
  if ro = 0 then return (se, te, re) ← wenn |s| + |t| minimal sein soll (Normalfall)
  if ro = 0 then return (se+so, te+to, re) ← wenn s>0 sein muss
  q ≔ ⌊re / ro⌋
  se ≔ se - q * so
  te ≔ te - q * to
  re ≔ re - q * ro (alternativ: re ≔ re mod ro)
end loop

s>0 ist erforderlich, wenn das modulare Inverse s von a modulo b berechnet werden soll:
s = a-1 | mod b
  ⇕
s * a ≡ 1 | mod b
  ⇕
∃t s * a + t * b = 1

Berechnung mit vorzeichenlosen Zahlen:

Da die Vorzeichen der Variablen fix sind (offensichtlich durch die Einfärbung), kann man auch ohne Vorzeichen mit unsigned-Zahlen rechnen (ich nutze für Berechnung mit großen Zahlen eine unsigned-Bibliothek):

so ≔ 1; to ≔ 0; ro ≔ a
se ≔ 0; te ≔ 1; re ≔ b
loop
  if re = 0 then return (+so, −to, ro)
  q ≔ ⌊ro / re⌋
  so ≔ so + q * se
  to ≔ to + q * te
  ro ≔ ro - q * re
  if ro = 0 then return (–se, +te, re) ← wenn |s| + |t| minimal sein soll
  if ro = 0 then return (so-se, –(to-te), re) ← wenn s>0 sein soll
  q ≔ ⌊re / ro⌋
  se ≔ se + q * so
  te ≔ te + q * to
  re ≔ re - r * ro
end loop