Chinesicher Restsatz / Kongruenzgleichung

Neue Frage »

Caramel Auf diesen Beitrag antworten »
Chinesicher Restsatz / Kongruenzgleichung
Meine Frage:
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 ...
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?
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. Augenzwinkern



Zitat:
Fangen wir mal mit der Primfaktorzerlegung von 31500 an




Zitat:
zu welchem System von Kongruenzen ist daher die gegebene Kongruenz äquivalent?


Wenn ich den chinesischen Restsatz richtig verstanden habe, dann zu









War das so gemeint?
Ibn Batuta Auf diesen Beitrag antworten »

Das ist korrekt.


Ibn Batuta
tigerbine Auf diesen Beitrag antworten »

Bleibt natürlich die Frage, warum man das gemacht hat. Augenzwinkern Also worin besteht die Verbesserung?

Zur Lösung werde ich dann Kongruenzgleichung und euklidischer Algorithmus benötigen?
Ibn Batuta Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Bleibt natürlich die Frage, warum man das gemacht hat. Augenzwinkern Also worin besteht die Verbesserung?


Das kann ich dir leider nicht beantworten. unglücklich

Zitat:
Original von tigerbine
Zur Lösung werde ich dann Kongruenzgleichung und euklidischer Algorithmus benötigen?


Genau. Freude


Ibn Batuta
 
 
René Gruber Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Bleibt natürlich die Frage, warum man das gemacht hat. Augenzwinkern Also worin besteht die Verbesserung?

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.
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.
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. Augenzwinkern


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. verwirrt
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...
tigerbine Auf diesen Beitrag antworten »

Zitat:



Also suche in ein x mit folgenden Eigenschaften:

Mystic Auf diesen Beitrag antworten »

Derive sagt teilweise was anderes, nämlich



Rest stimmt...
tigerbine Auf diesen Beitrag antworten »

Dann helft mir mal bitte den Fehler zu finden. Anleitung aus dem anderen Thread:

Zitat:
Zur Lösung der Kongruenzgleichung :


1.Fall: teilerfremd

Dann liefert der Erweiterte (!) Euklidische Algorithmus (EEA) zwei ganze Zahlen mit , woraus



folgt, und daraus wiederum

,

somit ist die eine Lösung der Ausgangskongruenz.


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? verwirrt Danke Wink
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von tigerbine
Dann helft mir mal bitte den Fehler zu finden [...]

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? verwirrt Danke Wink


Die letzte Zeile ist falsch, nämlich



Keine Ahnung wie du da auf deine Zahlen kommst... verwirrt
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.???????
tigerbine Auf diesen Beitrag antworten »

Ahrgh! 117*86 statt 117*57. Danke, dann kann ich nun weitermachen!
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Tokolosh
Hallo, ich hab die gleiche Aufgabe aufbekommen. Doch irgendwie kann ich die nicht lösen, da eine Bedingung nicht gilt.

Welche Bedingung gilt nicht?

Zitat:
Original von Tokolosh
Darum meine Frage, ist die Aufgabe überhaut lösbar.???????

Und du glaubst, wir hätten, wenn es wirklich so wäre, dieser Tatsache bisher noch keine Erwähnung getan? geschockt
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. Augenzwinkern
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »