Multiplikativ Inverse in Ringen |
02.01.2006, 20:03 | sannies | Auf diesen Beitrag antworten » | ||
Multiplikativ Inverse in Ringen im Rahmen einer Arbeit für die Uni muss ich an mehreren Stellen multiplikativ Inverse berechnen. Da ich den betreffenden Teil in Hardware baue ist es mir nur schwer möglich den euklidschen Algorhitmus umzusetzen. Ich rechne mit drei Ringen: 1: Zn1 (rechnet im Ring Z mod n1) 2: Zn2 (rechnet im Ring Z mod n2) 3: Zn3 (rechnet im Ring Z mod n3). zu Zn1 brauch ich das multiplikativ Inverse (n2 * n3) modulo n1 zu Zn2 brauch ich das multiplikativ Inverse (n1 * n3) modulo n2 zu Zn3 brauch ich das multiplikativ Inverse (n1 * n2) modulo n3 Wenn ich jetzt die Zahlen benachbart wähle d.h. n1 = n2 -1; n3 = n2+1 und n2 = 2^n, kommen für mich recht günstige Zahlen heraus (zumindest bei meinen Tests): für Zn1: n2 / 2 für Zn2: n2 - 1 für Zn3: n2 / 2 + 1 Das funktioniert - soweit ich sehen kann - auch für alle anderen geraden n2 (dadurch werden n1 und n3 teilerfremd), für mich interessant sind allerdings nur die n2 = 2^n (wegen der Einfachkeit in Hardware). Ich scheiter da auch nur einen Ansatz für den Beweis zu finden, ob es hier jemanden mit eine Idee gibt? Beste Grüße, Sebastian |
||||
02.01.2006, 20:11 | JochenX | Auf diesen Beitrag antworten » | ||
kannst du das näher erläutern? n1 ist eine natürliche zahl nehme ich an? geht es dann tatsächlich um den (i.A. Einslosen!) ring n1*Z? oder eher um Z/(n1*Z)? |
||||
02.01.2006, 21:08 | sannies | Auf diesen Beitrag antworten » | ||
Ich hab es gerade versucht die Sache in meinem Posting richtigzustellen. Ich meine einen Ring (zum Teufel - das ist doch ein Ring, Restklassenring!?) von Ganzzahlen mod n. also Z mod n( = 8): 1 + 3 = 4 4 + 2 = 6 6 + 2 = 0 0 + 8 = 0. n + 8 = n Bin mit den Begrifflichkeiten nicht so gut ... |
||||
02.01.2006, 23:39 | Abakus | Auf diesen Beitrag antworten » | ||
Ich bin nicht sicher, ob ich es richtig verstanden habe. Deine erste Behauptung ist beispielsweise: Das ist für richtig. Beweisen läßt sich das durch modulo-Rechnen, du darfst wie folgt rechnen: Das führt hier zum Ziel: . Grüße Abakus EDIT: die anderen beiden müssten ähnlich überprüfbar sein (ich habe es nicht gemacht). |
||||
07.01.2006, 21:36 | sannies | Auf diesen Beitrag antworten » | ||
Danke, ich war schon betriebsblind. Hab schon überlegt wie man das mit volständiger Induktion und erweitertem Euklidschen Algorithmus etc ... |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|