multiplikative inverse?
was ist die multiplikative inverse ? und was ist in dem bezug modulo ? was macht man mit den ''rechnungen'' und wie macht man es?
3 Antworten
Etwas (kurzgefasste) Theorie muss ich wohl ablassen, um das zu erklären. Die Antwort auf deine eigentliche Frage steht in D.
A. Ein Ring ist eine Menge, in der so gerechnet werden kann wie mit ganzen Zahlen. Welche Recheneigenschaften da genau gefordert sind, steht z.B. in >http://de.wikipedia.org/wiki/Ring_%28Mathematik%29#Definitionen .
B. Bei der Rechnung "modulo n", z.B. Z/n, werden alle ganzen Zahlen, die sich paarweise genau um ein ganzzahliges Vielfaches von n unterscheiden, als eine Klasse zusammengefasst. Meistens wird die Klasse mit der kleinsten nichtnegativen Zahl bezeichnet, die ihr angehört. Beispielsweise hat Z/3 die Klassen
{0 + 3k}, {1 +3k}, {2 +3k},
die als 0, 1, 2 bezeichnet werden. Wenn eine beliebige positive ganze Zahl mit Rest durch n geteilt wird, kommt dieses kleinste nichtnegative Zahl als Rest heraus.
C. Diese Klassen sind nun Elemente eines Rings (genauer. einen Restklassenring), d.h. die Rechengesetze, die für (einzelne) ganze Zahlen gelten, gelten auch für sie. Nur rechnest du mit der ganzen Klasse, als wäre es eine Zahl. Beispielsweise gelten Kommuntativ-, Assoziativ und Distributivgesetz, es gibt eine Null bzw. eine Eins, die ohne Veränderung addiert bzw. multipliziert werden kann, und es gibt zu jeder Klassen eine anderer Klasse so, dass die Summe beider die Nullklasse ist.
Das führt zu allerdings zu gewöhnungsbedürftigen Rechnungen, wie (in Z/3) etwa
1 + 2 = 0, denn für die entsprechenden ganzen Zahlen je einer Klasse gilt:
(1 + 3k) + (2 + 3k') = 3 + 3k + 3k' = 0 + 3(1 + k + k') = 0 + 3k'';
2 * 2 = 1, denn für die entsprechenden ganzen Zahlen je einer Klasse gilt:
(2 + 3k) * (2 + 3k') = 4 + 6k + 6k' + 9kk' =
1 + 3(1 + 2k + 2k' + 3kk') = 1 + 3k''.
Hierbei wird normalerweise ein Gleichheitszeichen mit drei Strichen geschrieben, um diese als Kongruenz bezeichnete "Gleichheit" von der tatsächlichen Gleichheit zu unterscheiden
D. Zu deinem eigentlichen Punkt: Sei a ein Element in einem Ring (z.B. einem Restklassenring. Dann heißt a^(-1) (geschrieben a hoch -1, gelesen "a invers") ein multplikativ inverses Element genau dann, wenn gilt:
a^(-1) * a = 1
Ein multiplikativ inverses Element kann existieren, muss aber nicht. Beispielsweise hat 0 in keinem Ring ein multiplikativ Inverses, denn in jedem Ring gilt:
x * 0 = 0
für alle Elemente x (wie du das von den ganzen Zahlen schon kennst, die auch ein Ring sind, s.o.), also ist x * 0 = 1 unlösbar.
Beispiele: In Z/3 ist 2 selbstinvers (2 * 2 = 1, s.o.).
In Z/14 hat 3 ein inverses (3 * 5 = 1), 2 aber nicht (alle Vielfachen von 2 sind "gerade", also ist 1 nicht darunter)
D. Einfache Rechenregeln und Eigenschaften:
Das Element 1 ist in allen Ringen selbstinvers (für die ganzen Zahlen ist 1 sogar das einzige Element, zu dem es ein multiplikativ Inverses gibt).
In Z/n ist n-1 immer selbstinvers.
In einem Ring mit endlich vielen Elementen (also z.B. einem Restklassenring) heißt ein von 0 verschiedenes Element a, das kein multiplikativ Inverses hat, Nullteiler. Denn es gibt für eine solches Element immer ein weiteres von Null verschiedenes Element b so, dass a * b = 0 ist.
Beispiel : 2 ist Nullteiler in Z/14, denn 2 * 7 = 0
a ist genau dann eine Nullteiler in Z/n, wenn a und einen Primfaktor gemeinsam hat. (1)
Umgekehrt hat also ein endlicher Ring ohne Nullteiler hat zu jedem Element bis auf 0 eine multiplikativ Inverses. Ein Restklassenring Z/n ist wegen (1) genau dann nullteilerfrei (und hat zu jedem Element bis auf 0 eine multiplikativ Inverses), wenn n eine Primzahl ist.
Wenn a^(-1) für ein gegebenes a aus Z/n existiert, ist a^(-1) = a^(n-2) (also das Produkt von a mit n-2 Faktoren)
multipl. Inverse sind die Kehrwerte; und zu modulo musst du mal präziser werden.
also: mein ''problem'' ist die rsa verschlüsselung. vielleicht wissen sie jetzt was ich meine.
multipl. inverse sind die kehrwerte ? können sie das vielleicht etwas genauer erklären ? danke
http://www.scoberlin.de/content/media/http/informatik/rsa/rsajan.pdf
da von hab ich leider keine Ahnung
ok, danke trotzdem für den link
das problem bei sowas ist immer, dass es auf slchen seiten immer sehr schwer erklärt wird und nicht für mich :D