Chinesicher Restsatz / Kongruenzgleichung |
06.02.2011, 11:58 | Caramel | Auf diesen Beitrag antworten » | ||||
Chinesicher Restsatz / Kongruenzgleichung Hallo zusammen, auf unserer Probeklausur ist eine Aufgabe die wir in der Form noch nicht hatten, wir der Chinesische Restsatz funktioniert weiß ich, nur allerdings weiß ich nichts mit der Gleichung anzufangen, bzw. wie ich die umformen o.ä. könnte. Wir sollen die kleinste positive Lösung der Kongrunenz 1193x=367mod31500 (wobei hier das = kongruent heißt) mittesl des Chinesischen Restsatzes bestimmen. Über eine paart Tipps wäre ich sehr dankbar!!! Liebe Grüße, Caramel Meine Ideen: Meine Überlegung war es das Inverse zu 1193 zu berechnen, aber das ist ja ziemlich aufwendig, das geht bestimmt einfacher ... |
||||||
06.02.2011, 12:30 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: Chinesicher Restsatz / Kongruenzgleichung Fangen wir mal mit der Primfaktorzerlegung von 31500 an... Wie lautet diese und zu welchem System von Kongruenzen ist daher die gegebene Kongruenz äquivalent? |
||||||
14.02.2011, 16:49 | tigerbine | Auf diesen Beitrag antworten » | ||||
RE: Chinesicher Restsatz / Kongruenzgleichung Da es den Fragesteller wohl nicht mehr interessiert, vielleicht geht jemand mit mir die Aufgabe durch.
Wenn ich den chinesischen Restsatz richtig verstanden habe, dann zu War das so gemeint? |
||||||
14.02.2011, 17:07 | Ibn Batuta | Auf diesen Beitrag antworten » | ||||
Das ist korrekt. Ibn Batuta |
||||||
14.02.2011, 17:11 | tigerbine | Auf diesen Beitrag antworten » | ||||
Bleibt natürlich die Frage, warum man das gemacht hat. Also worin besteht die Verbesserung? Zur Lösung werde ich dann Kongruenzgleichung und euklidischer Algorithmus benötigen? |
||||||
14.02.2011, 17:13 | Ibn Batuta | Auf diesen Beitrag antworten » | ||||
Das kann ich dir leider nicht beantworten.
Genau. Ibn Batuta |
||||||
Anzeige | ||||||
|
||||||
14.02.2011, 17:18 | René Gruber | Auf diesen Beitrag antworten » | ||||
Auf das jeweilige Modul reduziert lauten die entstehenden Einzelkongruenzen dann Diese Kongruenzen sind (vielleicht mit Ausnahme der dritten) sehr schnell durch Probieren lösbar. Aus den Einzellösungen kann man dann wiederum mit dem chinesischen Restsatz - diesmal in der "anderen" Rcihtung - die Gesamtlösung modulo 31500 zusammenbasteln. |
||||||
14.02.2011, 17:27 | tigerbine | Auf diesen Beitrag antworten » | ||||
Hier gilt noch 1193<31500, 367<31500 so dass man da nicht/schwer vereinfachen kann. Hier also 1193>4. Man berechnet sich die Restklasse, also und . Mit den Rechenregeln in Restklassen kommt man dann auf das von dir gepostete Habe ich das so richtig verstanden? Dann mache ich mich mal an das Rechnen. |
||||||
14.02.2011, 17:32 | René Gruber | Auf diesen Beitrag antworten » | ||||
So ist es. Bei der Lösung von Kongruenzen des Typs mit (wie etwa diesem ) gibt es übrigens einen rekursiven Zugang, der dieses Problem auf aufeinander aufbauende lineare Einzelkongruenzen modulo reduziert, ganz ohne EEA. Ein Wort noch zum Sinn der ganzen Zerlegung: Man kann so wie beschrieben vorgehen, und gelangt auch zum richtigen Ergebnis. Ob da ganze am Ende aber der effizientere Rechenweg ist, als gleich auf die Ausgangskongruenz den EEA loszulassen, vermag ich nicht zu beurteilen - dazu habe ich zu wenige Beispiele gerechnet und mich auch ansonsten nicht mit Effizienzfragen in diesem Teilgebiet auseinandergesetzt. |
||||||
14.02.2011, 18:53 | Mystic | Auf diesen Beitrag antworten » | ||||
Ich habe oben den Weg über den Chinesischen Restsatz vorgeschlagen, weil das in der Aufgabenstellung so verlangt war... In der Regel wird man wohl von vornherein mit dem EEA arbeiten, insbesondere dann, wenn der Modul nur einmal verwendet wird und die Bestimmung seiner Primfaktoren aufgrund seiner Größe Probleme macht... Ganz anders liegen allerdings die Dinge wenn der Modul sich nicht ändert und zwar groß ist, aber man seine Faktorsierung kennt, eine Situation wie sie etwa bei RSA für den rechtmäßigen Empfänger einer Nachricht vorliegt... Dieser benutzt exakt die gleiche Idee wie hier vorgeführt zum Potenzieren mit seinem privaten Schlüssel, was die Rechenzeit immerhin um fast den Faktor 4 senkt... |
||||||
14.02.2011, 19:01 | tigerbine | Auf diesen Beitrag antworten » | ||||
Also suche in ein x mit folgenden Eigenschaften: |
||||||
14.02.2011, 19:28 | Mystic | Auf diesen Beitrag antworten » | ||||
Derive sagt teilweise was anderes, nämlich Rest stimmt... |
||||||
14.02.2011, 20:09 | tigerbine | Auf diesen Beitrag antworten » | ||||
Dann helft mir mal bitte den Fehler zu finden. Anleitung aus dem anderen Thread:
Nun hatten wir hier also a=68, m=125, b=117. Mit dem EEA kam ich auf u=57 und v =-31. Nun ist So, wo hab ich nun was falsch gemacht? Danke |
||||||
14.02.2011, 20:41 | Mystic | Auf diesen Beitrag antworten » | ||||
Die letzte Zeile ist falsch, nämlich Keine Ahnung wie du da auf deine Zahlen kommst... |
||||||
14.02.2011, 20:46 | Tokolosh | Auf diesen Beitrag antworten » | ||||
Hallo, ich hab die gleiche Aufgabe aufbekommen. Doch irgendwie kann ich die nicht lösen, da eine Bedingung nicht gilt. Darum meine Frage, ist die Aufgabe überhaut lösbar.??????? |
||||||
14.02.2011, 20:56 | tigerbine | Auf diesen Beitrag antworten » | ||||
Ahrgh! 117*86 statt 117*57. Danke, dann kann ich nun weitermachen! |
||||||
14.02.2011, 20:56 | Mystic | Auf diesen Beitrag antworten » | ||||
Welche Bedingung gilt nicht?
Und du glaubst, wir hätten, wenn es wirklich so wäre, dieser Tatsache bisher noch keine Erwähnung getan? |
||||||
14.02.2011, 23:39 | tigerbine | Auf diesen Beitrag antworten » | ||||
Also ich habe das System nach meiner Anleitung gelöst und komme auf Probe stimmt. Habe nun aber nicht immer den EEA gemacht, sondern auch mit "Tabelle" gearbeitet. Manchmal ist die schönste Antwort doch, wenn "lösbar" reicht. |
||||||
15.02.2011, 08:59 | Tokolosh | Auf diesen Beitrag antworten » | ||||
Hallo, ich hab meinen Fehler gefunden. Hatte ne falsche multiplikative Inverse von M3. Wie auch immer, bei mir kommen auch so hohe Zahlen raus. Was für eine Probeklausuraufgabe^^. Wie dann die echte Klausur wird. Und das ohne Hilfsmittel. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |