 |
 |
 |
 |
 |
 |
Startseite » Forum » Berechnung des multiplikativen Inversen
Berechnung des multiplikativen Inversen
Universität / Fachhochschule
Algebraische Zahlentheorie
Tags: Modulo Arithmetik, Zahlentheorie
 
|
  |
|---|
|
GHallo, da ich zum ersten Mal in diesem Forum bin und nicht genau weiß, wo genau ich lande, schicke ich voraus, daß ich kein Mathematik-(sondern Philosophie)-Student bin, es mir um die Berechnung des multiplikativen Inversen geht und ich zuletzt auf einer Seite dieses Forums war, auf der es genau um dieses multiplikative Inverse ging und Naico und michaL den für mich vielversprechendsten Lösungsansatz diskutierten. Ich habe bisher herausgefunden, daß man offenbar mit dem erweiterten Euklidschen Algorithmus dieses Inverse berechnen kann. Wie dieser Algorithmus angewendet wird, habe ich inzwischen begriffen. Mein konkreter Fall: ggT von und berechnen. · · · · · · · · · · Damit ist formal bewiesen, daß und teilerfremd sind – aber das wußte ich vorher schon, denn (nicht ganz) zufälligerweise ist eine Primzahl. Der einzige Grund, warum ich mir diesen Algorithmus überhaupt genauer angesehen habe, war, daß auf mehreren Internet-Seiten (und in mehreren Google-Büchern) behauptet wird, als "Nebeneffekt" des erweiterten Euklidschen Alsgorihtmus (künftig erhielte man auch das multiplikative Inverse. Und genau das ist es, was mich nach drei Tagen Problemwälzen beinahe zur Verzweiflung treibt. Denn ich habe einerseits das Gefühl, nicht weit entfernt von der Lösung meines Problems zu sein, kann aber andererseits so gar nicht erkennen, inwiefern man aus den Rechenschritten oben das multiplikative Inverse (künftig ableiten kann. Auf mehreren Seiten habe ich sinngemäß ferner gelesen, daß die Formel ggT(a, xa yb bei der Berechnung eine Rolle spielt; es ist mir aber in keiner Weise klar, in welcher Beziehung xa yb zum . steht. Sie scheint eine Rolle bei dem zu spielen, was Naico "Rückwärtseinsetzen" genannt hat, und was der eigentliche Lösungsweg ist (den man wirklich nicht als "Nebeneffekt" des . bezeichnen kann, sondern als eigenständige und auch nicht-triviale Operation ansehen muß). Der auf jener Seite diskutierte Fall war simpler, nämlich · · · Dazu schrieb michaL: "Aus der letzten Zeile folgt: · · 3 · · · · · · · · · · " An dieser (entscheidenden) Stelle habe ich mich festgefahren. Wie kommt man von 1 · · · zu · · ? Mir ist natürlich klar, daß es hier genau um dieses Rückwärtseinsetzen geht und daß besagte Formel xa yb dabei offenbar die entscheidende Rolle spielt. Mir ist aber weder der theoretische Hintergrund für diese Formel noch ihre Anwendung auf meinen anfangs geschilderten Fall, also das . von zum Modul klar, so daß gilt: · Bin für jeden Hinweis dankbar. Walter Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo, wieso kannst du nicht erkennen, warum und gleich sind? Ganz konkret!?! Mfg Michael |
 |
|
Natürlich erkenne ich, daß beide Terme gleich sind, dazu muß man es ja nur in den Taschenrechner eintippen. Worum es mir ging, war, etwas mehr über die Form ax by zu erfahren, in die der Term 1 ⋅ − ⋅ ⋅ − 1 ⋅ überführt werden soll. Ich denke, das ging auch aus meinem Text klar hervor (ausführlich genug war er ja nun wirklich). Was mich - als Nichtmathematiker - bei der Beschäftigung mit der Frage "multiplikatives Inverses" geärgert hat, war, daß überall, wo etwas im Netz zu dieser Frage stand, immer wieder behauptet wurde, als "Abfallprodukt" des erweiterten Euklidschen Algorithmus könne man dieses Inverse berechnen. Und so etwas kann eben nur von "Leuten der Zunft" kommen, die mit uns nichterleuchteten Laien keinerlei Mitleid haben. Ich habe nach genauerem Studium begriffen, daß 1 ⋅ − ⋅ ⋅ − 1 ⋅ einfach ausmultipliziert werden muß, aber eben so, daß am Ende ein Term der Form ax by herauskommt. Wieso und warum, weiß ich noch immer nicht – es ist einfach so. Ich habe das dann für mein Beispiel am Anfang durchgeführt und herauskam: –2 · · – 9 · · – · · – · – 1 · –47 · · –47 · · – 1 · · – · · – · – 3 · –99 · · –99 · · – 1 · · – · · – · – · –448 · · –448 · · – 1 · · – · · – · – · = – · · ist damit . Und das soll nun die effizienteste Vorgehensweise sein, um das . zu berechnen? Gibt es, insbesondere für größere Zahlen wie meine, keinen komfortableren Weg? |
|
|
|
Wenn du es per Hand rechnen willst, wird es wohl keinen bequemeren Weg geben. |
|
|
|
Ich will es gerade nicht per Hand rechnen. Wenn Du also eine Alternative weißt, wäre ich Dir sehr dankbar. Ich habe mich natürlich auch selbst schon ein wenig umgesehen. Folgendes kleine Basic-Programm z.B. berechnet das multiplikative Inverse: For i = 1 To m mix = (m*i+1)/x If mix = Int(mix) Then Exit For Next Print mix Im Falle von 37457x ≡ 1 mod 2147483647 müßte man also m = 2147483647 und x = 37457 setzen; dazu wird dann das multiplikative Inverse mix berechnet. Das Problem: Da i immer nur um 1 hochgezählt wird, kann es bei großen Zahlen recht lange dauern, bis das Ergebnis kommt. Mit den angegebenen Zahlen wird die Schleife über 15000 mal durchlaufen, was auf schnellen Rechnern Bruchteile von Sekunden dauert. Ich hatte aber auch schon Zahlen für m und x, an denen mein Rechner fast eine Minute lang gerechnet hat. Was ich bisher noch nicht erwähnt habe: Ich brauche das multiplikative Inverse zur Erzeugung von Zufallszahlen in einem inversiven Kongruenzgenerator, der möglichst schnell arbeiten soll. Dazu taugt das Programm oben nicht, weil es viel zu langsam ist. |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
880207
879642