Das multiplikativ inverse Element a-1 eines Elements a in der Gruppe ℤn* ist das eindeutig bestimmte Element, für das gilt
a-1· a = a · a-1 = 1
wobei 1 das neutrale Element der Gruppe ist.
Beispielsweise ist 5 das inverse Element zu 3 in der Gruppe ℤ14*. Denn in ℤ gilt 5 · 3 ≡ 15 ≡ 1 (mod 14), und in ℤ14* gilt damit 5 · 3 = 1.
Das inverse Element eines Elements a ∈ ℤn* berechnen Sie mit Hilfe des erweiterten euklidischen Algorithmus.
Der erweiterte euklidische Algorithmus berechnet für zwei Zahlen a, b ∈ ℕ den größten gemeinsamen Teiler ggt(a, b) sowie die Darstellung des ggt als ganzzahlige Linearkombination von a und b:
ggt(a, b) = u·a + v·b mit u, v ∈ ℤ.
Die multiplikative Gruppe ℤn* besteht aus den Elementen von ℤn, die teilerfremd zu n sind. Für jedes a ∈ ℤn* gilt dann
ggt(a, n) = 1
und die 1 lässt sich nach dem Lemma von Bézout als ganzzahlige Linearkombination von a und b darstellen:
1 = u·a + v·n.
Modulo n gerechnet ergibt sich
1 ≡ u·a + v·n ≡ u·a (mod n).
Multiplikation mit a-1 ergibt
a-1 ≡ u (mod n).
Damit ist u mod n das inverse Element von a in ℤn*.
Mit der folgenden Python-Funktion modinverse berechnen Sie das multiplikativ inverse Element a-1 eines Elements a in einer Gruppe ℤn*. Achten Sie darauf, dass a auch tatsächlich ein Element von ℤn* ist, d.h. dass ggt(a, n) = 1 gilt. Die Funktion extgcd ist eine Implementierung des erweiterten euklidischen Algorithmus.
Weiter mit: [up]