Upload
others
View
4
Download
0
Embed Size (px)
Citation preview
2: Restklassen2.1: Modulare Arithmetik
I Uhr: Stunden mod 24,Minuten mod 60,Sekunden mod 60, . . .
I Rechnerarithmetik: mod 2w ,w ∈ {8,16,32,64}
I Prüfziffern mod 10 odermod 11
I . . .
–71– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Division mit Rest
Satz 18Seien a ∈ N0 und n ∈ N. Dann gibt es eindeutig bestimmte q ∈ N0,r ∈ {0, . . . ,n − 1} mit
a = n ∗ q + r .
Entsprechend definieren wir die Operationen “ div ” und “mod” durch
a div n = q und a mod n = r
(das ganzzahlige Teilen und die Berechnung des Restes).
–72– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Die Kongruenz-Relation
Definition 19Ist
a mod n = b mod n,
dann sind a und b kongruent modulo n, wir schreiben
a ≡ b (mod n).
In welcher logischen Beziehung stehen die Aussagen “a = b mod n”und “a ≡ b (mod n)”?(Nein, das ist nicht ganz das Gleiche!)
–73– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Eigenschaften der Kongruenz-Relation
Satz 20Für alle a,b,n ∈ N gelten die folgenden EigenschaftenReflexivität: a ≡ a (mod n)Symmetrie: a ≡ b (mod n) ⇔ b ≡ a (mod n)Transitivität: (a ≡ b (mod n)) ∧ (b ≡ c (mod n))
⇒ (a ≡ c (mod n))
(Allgemein bezeichnet man Relationen, die reflexiv und symmetrischund transitiv sind, als “Äquivalenzrelationen”.)
Satz 21 (Regel vom Vielfachen in N0)Für alle a,b ∈ N0 mit a ≥ b gilt: (a ≡ b (mod n))⇔ n|(a− b).
(Hinweis: Alle natürlichen Zahlen n ∈ N0 sind Teiler von 0.)
–74– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Rechenregeln mod n
Satz 221. (a + b) mod n = ((a mod n) + (b mod n)) mod n2. (a− b) mod n = ((a mod n)− (b mod n)) mod n3. (a ∗ b) mod n = ((a mod n) ∗ (b mod n)) mod n4. ad mod n = (ad−x ∗ ax ) mod n = ((ad−x mod n) ∗ (ax mod n)) mod n
(für x ≤ d)
FolgerungBei Berechnungen modulo n kann man Zwischenergebnisse (alleSummen, alle Differenzen und alle Produkte) auf Werte in{0, . . . ,n − 1} reduzieren.
–75– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Square-And-MultiplyDie Potenzierung von Binärzahlen
Eingabe: x , y , z ∈ {0,2n − 1} (∗ drei n-bit Binärzahlen ∗)Ausgabe: p = yx mod zAlgorithmus:
p := 1for i from 0 to n − 1 do
if xi 6= 0 thenp := (p ∗ y) mod z (∗ multiply conditionally ∗)
end ify := y ∗ y mod z (∗ square always ∗)
end for
Multiplizieren und den Modulus berechnen können wir in quadratischerZeit. Dann gilt:Wir können p in kubischer Laufzeit berechnen. (Warum?)
–76– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Das 444-Problem: 4(44) (mod 13)
1. Lösungsversuch:
1. Berechne 4(44).
2. Reduziere das Ergebnis mod 13.
>>> x = 4∗∗ (4∗∗4)>>> pr in t ( x )13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096>>> pr in t ( x % 13)9
Ergebnis: 9.Das funktioniert, ist aber wegen des großen Zwischenwertes rechtineffizient.
–77– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Mit Python ging die Berechnung aber schnell . . .
Dann berechnen Sie doch bitte mit Python
14(1414) (mod 13).
Nach einigen Minuten des Wartens fällt Ihnen vielleicht auf, dass14 mod 13 = 1 ist . . .
–78– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
Das 444-Problem (2)2. Lösungsversuch:
1. Berechne x := 44 = 256.2. Berechne 4x mit Square-and-Multiply:
(4 ∗ (4 ∗ (. . . (4 ∗ 4) mod 13 . . . 4) mod 13) ∗ 4) mod 13 = 9.
Das funktioniert auch, und ist, wegen der kleineren Zwischenwerte,viel effizienter.
3. Lösungsversuch:
1. Berechne y = (44) mod 13 = 256 mod 13 = 9.2. Berechne 4y mit Square-and-Multiply: 49 mod 13 = 12.
Das ist noch effizienter . . . und falsch!
Im Allgemeinen gilt ad mod n = ad mod n mod n nicht!
–79– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.1: Modulare Arithmetik
2.2: Anwendung: EAN- bzw. GTIN Prüfziffer
EAN: 13-stellige “European Article Number”;2009 umbenannt in “Global Trade Item Number”(GTIN), bestehend aus
I Länderpräfix (z.B. 40–44 für Deutschland),I Unternehmensnummer,I Artikelnummer des Herstellers undI Prüfziffer x13I Präfix, Unternehmensnummer und
Artikelnummer zusammen 12 Ziffernx1, . . . , x12 ∈ {0, . . . ,9}.
–80– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.2: Anwendung: EAN/GTIN
EAN- bzw. GTIN Prüfziffer (2)
Die GTIN (x1, . . . , x12, x13) ist gültig, falls(x1 + 3x2 + x3 + 3x4 + x5 + 3x6 + · · ·+ x11 + 3x12 + x13) mod 10 = 0.
I Sei (x1, . . . , x12) gegeben. Wie muss man die Prüfziffer x13berechnen, um eine gültige GTIN zu erhalten?
I Erkennungsleistung: Besonders häufige Fehler (beimenschlicher Eingabe) werden meistens erkannt:
1. Veränderung einer gültigen GTIN in nur einer Ziffererkennt man immer. (Nachrechnen!)
2. Das Vertauschen zweier benachbarter Ziffernwird meistens, aber nicht immer erkannt.(Für welche Ziffern x 6= y gilt x + 3y ≡ 3x + y mod 10?)
3. Das Vertauschen zweier beliebiger Ziffernwird in mehr als 50 % aller Fälle nicht erkannt.
–81– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.2: Anwendung: EAN/GTIN
Warum ist die Erkennungsleistung so?Könnte man sie verbessern?
Satz von BézoutSeien a,b,n ∈ N gegeben. Ist a teilerfremd zu n, dann ist dieGleichung
ax ≡ b (mod n)
lösbar. Es gibt genau eine Lösung x ∈ {0, . . . ,n − 1}.
(Werden wir noch beweisen!)
I Verändern einer Ziffer: 1 und 3 sind teilerfremd zu 10.I Vertauschen zweier Ziffern: 2x ≡ b ist nicht eindeutig lösbar.
Man beachte, dass 2 und 10 nicht teilerfremd sind!I Alternative: Berechnung der Prüfziffer mod 11 (Primzahl!).I Problem: zusätzliche Ziffer “10” oder “verbotene” Eingaben.
–82– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.2: Anwendung: EAN/GTIN
International Standard Book Number (ISBN – veraltet)
Eine ISBN (x1, . . . , x9, x10) ist gültig, fallsx1 + 2x2 + 3x3 + 4x4 + 5x5 + 6x6 + 7x7 + 8x8 + 9x9 ≡ x10 (mod 11).
I Die 11 möglichen Prüfziffern sind ∈ {0,1, . . . ,9, ’X’}.I Veränderung einer gültigen ISBN in nur einer Ziffer erkennt man
immer.I Das Vertauschen zweier benachbarter Ziffern erkennt man
immer – und sogar das Vertauschen zweier beliebiger Ziffern!I Statt der alten 10-stelligen ISBN verwendet man inzwischen
13-stellige, bestehend aus einem Pseudo-Ländercode 978, der9-stelligen ISBN (ohne Prüfziffer) und der GTIN Prüfziffer.
–83– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.2: Anwendung: EAN/GTIN
2.3: Der Satz von Bézout
Den folgenden Satz haben wir bereits ohne Beweis behauptet. Er wirdauch als “Fundamentalsatz der Arithmetik” bezeichnet:
Satz 23 (Eindeutigkeit der Primzahlzerlegung)Jede Zahl n ∈ N, n ≥ 2, lässt sich eindeutig in der Form
n = pe11 ∗ pe22 ∗ · · · ∗ p
ekk
darstellen, wobei p1 < p2 < . . . < pk und e1,e2, . . . ,ek ∈ N gilt.
( Beweis der Existenz induktiv;Eindeutigkeit als Widerspruchsbeweis! )
–84– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.3: Der Satz von Bézout
Teilerfremde Zahlen
Definition 24Der größte gemeinsame Teiler ggT(a,b) von a,b ∈ N ist die größtenatürliche Zahl, die sowohl a als auch b teilt.
Zwei Zahlen a und b sind teilerfremd (wir sagen auch relativ prim),wenn ggT(a,b) = 1 ist.
Die Existenz und Eindeutigkeit des ggT ergeben sich aus derEindeutigkeit der Primzahlzerlegung.
Genau dann, wenn p prim ist, gilt ggT(p,a) = 1 für allea ∈ {1, . . . ,p − 1}.
–85– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.3: Der Satz von Bézout
Linearkombinationen
Definition 25Linearkombinationen von zwei Zahlen a,b ∈ Z sind alle ZahlenL = ax + by, für x,y ∈ Z. Die x,y heißen Koeffizienten von L.
Eine Linearkombination L = ax + by ist positiv, wenn L ∈ N.
Satz 26 (Lemma von Bézout)Die kleinste positive Linearkombination von a und b ist ggT(a,b).
Beispiel 27Die Linearkombinationen von 4 und 6 sind {. . . ,−4,−2,0,2,4, . . .},also alle geraden Zahlen in Z.
Die kleinste pos. Linearkombination von 4 u. 6 ist 2 = 6 ∗ 1 + 4 ∗ (−1).
–86– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.3: Der Satz von Bézout
Der Hilfssatz von Euklid
Satz 28Aus n|ab und ggT(a,n) = 1 folgt n|b.
Folgerung 29Ist p eine Primzahl und p|ab, dann ist p|a oder p|b.
–87– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.3: Der Satz von Bézout
Kürzen mod n
Im Allgemeinen gilt nicht ax ≡ ay (mod n) ⇒ x ≡ y (mod n). Z.B.
10 ≡ 30 (mod 20) aber 5 6≡ 15 (mod 20).
Nur wenn wir die Wahl von a einschränken, dürfen wir durch a kürzen:
Satz 30 (Kürzungsregel)Ist a teilerfremd zu n und
ax ≡ ay (mod n),
dann giltx ≡ y (mod n).
–88– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.3: Der Satz von Bézout
Lösbare lineare Gleichungen
Satz 31 (Satz von Bézout)Seien a,b,n ∈ N gegeben. Ist a relativ prim zu n, dann ist dieGleichung
ax ≡ b (mod n)
lösbar. Es gibt genau eine Lösung x ∈ {0, . . . ,n − 1}.
Beispiel: 3x ≡ 7 mod 8.
Folgerung 32Ist a relativ prim zu n, dann ist die Funktion
πa : {0, . . . ,n − 1} → {0, . . . ,n − 1}, πa(x) = ax mod n
eine Permutation.
–89– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.3: Der Satz von Bézout
2.4: Der Restklassenring mod nModulo n sind alle Werte a± kn äquivalent.
Wir interessieren uns für die Menge der echt verschiedenen Werte,d.h., für a1,a2, . . . mit ai 6≡ aj (mod n) :
Definition 33Seien n ∈ N und a ∈ Z. Die Restklasse von a modulo n ist
{kn + a|k ∈ Z}
Ein Element einer Restklasse bezeichnet man auch als Repräsentantder Restklasse. Die natürlichen Repräsentanten sind die Zahlen 0, . . . ,n − 1.
Die Menge aller Restklassen modulo n, geschrieben Zn, bildet,zusammen mit der Addition und der Multiplikation, denRestklassenring mod n.
–90– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.4: Restklassenring mod n
Bemerkungen
I Jede Restklasse hat genau einen natürlichen Repräsentantena ∈ {0, . . . ,n − 1}, aber unendlich viele beliebige Repräsentantena + kn ∈ Z.
I Nie vergessen: Mathematisch bedeutet eine Berechung in Zn,dass egal ist, wie eine Restklasse repräsentiert wird!
I Zn besteht aus genau n Restklassen.I In Zn können wir rechnen wie in Z (→ Rechenregeln mod n), bis
auf die etwas andere→ Kürzungsregel.I Wenn klar ist, das eine Berechnung in Zn stattfindet, können wir
statt “a ≡ b (mod n)” auch “a = b” schreiben.
–91– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.4: Restklassenring mod n
Der Begriff “Ring”
Was genau ein “Ring” ist, werden wir im Kapitel über “Körper”definieren. Für uns ist wichtig: In Zn gelten, wie in Z, die folgendenarithmetischen Gesetze:
I Assoziativgesetze:I Addition: a + (b + c) = (a + b) + c undI Multiplikation: a(bc) = (ab)c.
I Kommutativgesetze:I Addition: a + b = b + a undI Multiplikation: ab = ba.
I Neutrale Elemente:I Addition: 0 + a = a + 0 = a undI Multiplikation: a1 = 1a = a.
I Inverses Element der Addition: a + (−a) = 0.I Distributivgesetz: a(b + c) = ab + ac
–92– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.4: Restklassenring mod n
Division in Zn
I In Z ist die ganzzahlige Division als Umkehrung der Multiplikationnur partiell definiert:
a/b = c, falls es ein c ∈ Z gibt mit bc = a.I Z.B. gilt 3 ∗ 4 = 12 und 3 ∗ 5 = 15; ensprechend sind 12/4 und
15/5 in Z definiert, aber 13/3 und 14/5 nicht.I Auch in Zn wollen wir die Division zumindest partiell definieren.I Beispiel Z10:
I 4 ∗ 3 = 2 und 3 ∗ 5 = 5.Analog zu Z müsste 2/3 = 4 und 5/5 = 3 gelten.
I 5/5 = 3? Kann doch nicht sein!I Tatsächlich ist 1 ∗ 5 = 3 ∗ 5 = 5 ∗ 5 = 7 ∗ 5 = 9 ∗ 5 = 5,
also könnte 5/5 eine beliebige ungerade Zahl sein . . .I Und 2/5? D.h. k ∈ N mit 2k ≡ 5 (mod 10)? Gibt’s nicht!
–93– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.4: Restklassenring mod n
Multiplikative Inverse modulo nDefinition 34Sei a ∈ Zn. Das multiplikative Inverse von a mod n ist ein Wert a−1 mita ∗ a−1 ≡ 1 (mod n).
Satz 35In Zn existiert das multiplikative Inverse einer ganzen Zahl a modulo ngenau dann, wenn a teilerfremd zu n ist.
(Satz von Bézout, Widerspruchsbeweis)
Beispiel: Vollständige Liste der multiplikativen Inversen in Z10i i−1 Begründung1 1 1 ∗ 1 = 13 7 3 ∗ 7 = 217 3 7 ∗ 3 = 219 9 9 ∗ 9 = 81
–94– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.4: Restklassenring mod n
Division in Zn – jetzt richtig
I Wenn ein multiplikatives Inverses von b in Zn existiert,dann ist a/b = a ∗ b−1.
I Wenn ein solches Inverses nicht existiert,dann ist a/b nicht definiert.
I Wenn man in Zn rechnet, darf man niemals (!!!) a/b ∈ Qverwenden . . .denn a und b sind Restklassen, die jeweils unendlich vieleverschiedene Zahlen als Repräsentanten haben können.
(Anders als in Z, wo a und b eindeutig bestimmte Zahlen sind,und a/b ∈ Q für b 6= 0 eindeutig bestimmt ist.)
–95– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.4: Restklassenring mod n
2.5: Die Berechnung des Inversen in Zn
Frage 1: Wie können wir effizient feststellen,ob b−1 mod n existiert?
D.h.: Wie kann man den ggT von b und n berechnen?
Frage 2: Wie können wir b−1 mod neffizient berechnen?
Denn: “Teste für alle x ∈ Zn, ob ax mod n = 1 gilt” funktioniertzwar, ist aber nur für kleine n effizient.
–96– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Die brutale Berechnung des ggT:Eine Nicht-Antwort auf Frage 1
Eingabe: a,b ∈ NAusgabe: ggT(a,b)
Algorithmus:for i from min{a,b} downto 1 do
if i |a and i |b thenreturn i
end ifend for
–97– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Warum keine Antwort auf Frage 1?Der Algorithmus funktioniert doch . . .Beispiel:
I Für alle z ∈ N gilt ggT(2z − 1,2z − 2) = 1. (Warum?)I Der Brutal-Algorithmus probiert 2z − 2 verschiedene Teiler i , bis er
endlich mit i = 1 den ggT findet.I Ersetzt man z durch z + 1,
I dann werden die Zahlen nur um 1 Bit länger,I aber die Laufzeit des Algorithmus verdoppelt sich!
Allgemein:
I Die Laufzeit zur Berechnung des ggTs zweier z-bit Zahlen(d.h., für a,b < 2z die Berechnung von ggT(a,b))kann sich etwa proportional zu 2z verhalten.
I Eine solche Laufzeit nennt man exponentiell.=⇒ Exponentielle Laufzeiten sind schlecht!
–98– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Zwei hilfreiche Eigenschaften des ggT
Satz 361. Ist b|a, dann ist ggT(a,b) = b.2. Ist r = a mod b, dann ist ggT(a,b) = ggT(b, r).
(Zweite Beh.:r = a mod b entspricht r = a− bx für ein x ∈ N0.(a) Jeder gemeinsame Teiler von a und b teilt auch r .(b) Jeder gemeinsame Teiler von b und r teilt auch a = bx + r .)
–99– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Die Antwort auf Frage 1:Der Euklidische Algorithmus
Eingabe: a,b ∈ NAusgabe: ggT(a,b)
Algorithmus:loop
r := a mod bexit when r = 0a := bb := r
end loopreturn b
–100– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Die Laufzeit des Euklidischen Algorithmus
Satz 37Seien a und b Z-bit Nummern, d.h., a,b < 2Z .Dann terminiert der Euklidische Algorithmus spätestens nach 2ZSchleifendurchläufen.
(Für a ≥ b gilt: a ≥ b + r > 2r .)
Es gibt Algorithmen zur Berechnung von “a mod b” mit höchstensquadratischer Laufzeit.
Folgerung 38Der Euklidische Algorithmus kann so implementiert werden, dass dieLaufzeit höchstens kubisch ist.
–101– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Zwei Varianten des Euklidischen Algorithmus
Eingabe: a,b ∈ NAusgabe: ggT(a,b)
Algorithmus (iterativ):loop
r := a mod bexit when r = 0a := bb := r
end loopreturn b
Eingabe: a,b ∈ NAusgabe: ggT(a,b)
Algorithmus (rekursiv):r := a mod bif r = 0 then
return belse
return ggT(b, r)end if
–102– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Worin unterscheiden sich die beiden Varianten?
I der gleiche Algorithmus (die gleichen Werte a, b, und r )I Laufzeit: # Schleifendurchläufe = # rekursiver AufrufeI Laufzeitanalyse (scheinbar) einfacher bei iterativer VarianteI Korrektheit klarer bei rekursiver VarianteI beim Rechnen von Hand finde ich die rekursive Variante
einfacher, z.B.,
ggT(50,23) = ggT(23,4) = ggT(4,3) = ggT(3,1) = 1.
–103– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Beispiele
Berechne ggT(33,27), ggT(343,77) und ggT(3343,77).ggT(a,b) Gleichung rggT(33,27) 33 = 1 ∗ 27 + 6 6ggT(27,6) 27 = 4 ∗ 6 + 3 3ggT(6,3) 6 = 2 ∗ 3 + 0 0 Ergebnis=3ggT(343,77) 343 = 4 ∗ 77 + 35 35ggT(77,35) 77 = 2 ∗ 35 + 7 7ggT(35,7) 35 = 5 ∗ 7 + 0 0 Ergebnis=7ggT(3343,77) 3343 = 43 ∗ 77 + 32 32ggT(77,32) 77 = 2 ∗ 32 + 13 13ggT(32,13) 32 = 2 ∗ 13 + 6 6ggT(13,6) 13 = 2 ∗ 6 + 1 1ggT(6,1) 6 = 1 ∗ 6 + 0 0 Ergebnis=1
–104– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Gesucht: Die Koeffizienten der Linearkombination ggT
BeobachtungSei ggT(a,b) = 1. Dann ist 1 die kleinste positive Linearkombinationvon a und b. D.h., es gibt Koeffizienten x und y mit
ax + by = 1.
Wenn wir diese Koeffizienten kennen,dann können wir multiplikative Inverse berechnen:
ax ≡ 1 (mod b), also a−1 ≡ x (mod b).
Genauso:b−1 ≡ y (mod a).
–105– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Zwei hilfreiche Beobachtungen, neu aufgemischt
Satz (bereits bekannt)1. Ist b|a, dann ist ggT(a,b) = b.2. Ist r = a mod b, dann ist ggT(a,b) = ggT(b, r).
Satz 391. Ist b|a, dann ist b = ggT(a,b) = 0a + 1b.2. Ist z = a div b, r = a (mod b) und ggT(a,b) = xb + yr , dann
ggT(a,b) = ggT(b, r) = ya + (x− zy)b.
–106– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Der Erweiterte Euklidische Algorithmus (→ Frage 2)
Eingabe: a,b ∈ N,a > bAusgabe: (d , x , y),
d = ggT(a,b) ∈ N x , y ∈ Z : ax + by = d
Algorithmus XggT(a,b):r := a mod bif r = 0 then
return (b,0,1) (∗ b = ggT(a,b) = 0a + 1b ∗)else
(d , x , y) := XggT(b,a mod b) (∗ d = ggT(a,b) = xb + yr ∗)z := a div breturn (d , y , x − zy ) (∗ d = ggT(a,b) = ya + (x − zy)b ∗)
end if
–107– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Eigenschaften des EEA
1. Laufzeit: Genau so viele rekursive Aufrufe, wie beim EuklidischenAlgorithmus
2. Korrektheit:2.1 d = ggT(a,b): Gleiche Operationen wie beim Euklidischen
Algorithmus2.2 ax + by = d : Induktiv (Anfang: r = 0)
r := a mod bif r = 0 then
return (b,0,1) (∗ b = ggT(a,b) = 0a + 1b ∗)else
(d , x , y) := XggT(b,a mod b) (∗ d = ggT(a,b) = xb + yr ∗)z := a div breturn (d , y , x − zy ) (∗ d = ggT(a,b) = ya + (x − zy)b ∗)
end if
–108– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Beispiel (1)
Berechne den erweiterten ggT von 33 und 27 und – wenn vorhanden –das multiplikative Inverse von 27 mod 33.
ggT(a,b) Gleichung r , z ErgebnisggT(33,27) 33 = 1 ∗ 27 + 6 r = 6, z = 1 (3,-4,5)ggT(27,6) 27 = 4 ∗ 6 + 3 r = 3, z = 4 (3,1,-4)ggT(6,3) 6 = 2 ∗ 3 + 0 r = 0 (3,0,1)
Probe: 33 ∗ (−4) + 27 ∗ 5 = −132 + 135 = 3
Man beachte die Reihenfolge in der Berechnung: zuerst links von obennach unten, dann rechts von unten nach oben!
–109– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn
Beispiel (2): 77−1 mod 3343
ggT(a,b) Gleichung r z ErgebnisggT(3343,77) 3343 = 43 ∗ 77 + 32 32 43 (1,−12,521)ggT(77,32) 77 = 2 ∗ 32 + 13 13 2 (1,5,−12)ggT(32,13) 32 = 2 ∗ 13 + 6 6 2 (1,−2,5)ggT(13,6) 13 = 2 ∗ 6 + 1 1 2 (1,1,−2)ggT(6,1) 6 = 1 ∗ 6 + 0 0 — (1,0,1)
Probe: (0) 1 = 0 ∗ 6 + 1 ∗ 1(1) 1 = 1 ∗ 13 + (−2) ∗ 6 = 13− 12(2) 1 = (−2) ∗ 32 + 5 ∗ 13 = −64 + 65(3) 1 = 5 ∗ 77 + (−12) ∗ 32 = 385− 384(4) 1 = (−12) ∗ 3343 + 521 ∗ 77 = −40116 + 40117
“Heureka! Alles stimmt!”Ergebnis: 521 ∗ 77− k ∗ 3343 = 1⇒ 77−1 ≡ 521 (mod 3343).
–110– S. Lucks Diskr Strukt. (WS 18/19) 2: Restklassen 2.5: Inverse in Zn