hi,
hab auch mal wieder eine frage an euch:
wie berechnet man das inverse (bzgl. *) einer zahl
in einem restklassenkörper (oder -ring mit 1)?
z.B: in (Z257,+,*)
gesucht: das inverse von 7 (also 7-1)
danke im voraus!
Tom
Hallo Tom,
hab auch mal wieder eine frage an euch:
wie berechnet man das inverse (bzgl. *) einer zahl
in einem restklassenkörper (oder -ring mit 1)?z.B: in (Z257,+,*)
gesucht: das inverse von 7 (also 7-1)
Das Problem ist, dass die Einheitengruppe in Restklassenringen
nicht vollständig ist. D.h. vielen Elementen fehlt das Inverse.
Daher muss man vorher ermitteln, ob das Inverse existiert.
Die Berechnung in einem Restklassenring kann mit
den „normalen“ Rechenoperationen in Z geschehen. Beispiel (Z11,+,*)
Wenn man die Werte 5 und 8 aus Z11 multiplizieren will, tut man dies
innerhalb Z und bildet später den Modulo im Ring.
Also
5 * 8 = 40 in Z
40 MOD 11 = 7
Das heisst
5 * 8 = 7 in Z11
Um nun auf das Inverse einer Zahl zu kommen, hat man einen
Multiplikator so zu suchen, dass das Ergebnis das neutrale Element
darstellt, also 1.
Z.b. das Inverse von 6 in Z11 wäre dann 2, denn
6 * 2 = 12 in Z, und
12 MOD 11 = 1 in Z11
Daher hat z.B. die 7 kein Inverses in (257,+,*), denn
7 * 36 = 252 in Z
7 * 37 = 259 in Z, aber
259 MOD 257 = 2 1
Zu Körpern; Ein Restklassenring Zn kann nur dann ein Körper sein,
wenn n eine Primzahl ist.
Hoffe, ein wenig geholfen zu haben, sorry, wenn sich Fehler
eingeschlichen haben sollten.
Grüße
Wolfgang Wagner
Hallo,
der Ansatz ist 7n mod 257=1 mit 1=0), also 257m mod 7=6.
256\*1 mod 7=5
256\*2 mod 7=3
256\*3 mod 7=1
256\*4 mod 7=6
ergo m=4 ist eine Lsg. Setzen wir das oben ein erhalten wir 7n=257*4+1=1029 und n=147.
Gruss
Enno
Hallo,
sollte natürlich
257\*1 mod 7=5
257\*2 mod 7=3
257\*3 mod 7=1
257\*4 mod 7=6
heißen.
Gruss
Enno
wie berechnet man das inverse (bzgl. *) einer zahl
in einem restklassenkörper (oder -ring mit 1)?
Der Algorithmus, mit dem das geht, heisst erweiterter Euklid-Algorithmus. Literatur-Tipp: D. E. Knuth, Art of Computer Programming.
In Python sieht das Teil so aus:
def multinv(u3, v3):
"""first parameter u3 is the base modulus
2nd parameter v3 is the number, for which the multiplicative inverse is desired
result is a tuple:
1st element is the greatest common divisor gcd
2nd the multiplicative inverse (valid only if gcd==1)"""
large = u3 # make a copy, if result would be negative
u2 = 0
v2 = 1
while v3 0:
q, u4 = divmod(u3, v3)
u3, v3 = v3, u4
u4 = u2 - q \* v2
u2, v2 = v2, u4
if u2
hab Dank!
Tom