Wie löse ich quadratische Kongruenzen?

Neue Frage »

20.12.2009, 15:46	Chris12345	Auf diesen Beitrag antworten »
Wie löse ich quadratische Kongruenzen? Hallo, ich kann in der Vorlesung meinem Prof nicht folgen... Er hat folgende quadratische Kongruenz: 1 'kongruent' y1^2 mod 19 24 'kongruent' y2^2 mod 29 Gelöst wird diese wie folgt: y1=1 oder y1=19-1=18 y2=13 oder y2=29-13=16 Mir fehlt jetzt das Verständnis, wie der Professor bei y2 auf 13 gekommen ist. Ich komm da einfach nicht drauf. Ein Zwischenschritt wär also echt klasse, wenn ihn jemand weiss. Vllt versteh ich es dann auch endlich mal :-) Danke schonmal und freundliche Grüße, Chris
20.12.2009, 18:06	wisili	Auf diesen Beitrag antworten »
RE: Wie löse ich quadratische Kongruenzen? 1 ist Quadratzahl: 1 = (±1)^2 Somit y = ± 1 (statt -1 schreibt man aber 18) Die zweite Gleichung ist aufwändiger: Man sucht eine Quadratzahl der Form 24 + 29 k. Man probiert k = 0, 1, 2, ... und wird bei k=5 fündig: 24 + 145 = 169 = 13^2. Wie oben ist aber nicht nur 13, sondern auch -13, schreibe 16 eine Lösung.
20.12.2009, 19:56	Mystic	Auf diesen Beitrag antworten »
Ja, das Wurzelziehen mod p, p Primzahl, ist ein in Hinblick auf viele Anwendungen - vor allem in der Kryptographie - hochaktuelles Thema und zum Glück gibt es zu diesem Zweck gute Polynomialzeitalgorithmen mit Aufwand höchstens $\begin{eqnarray} O((\ln p)^3) \end{eqnarray}$ ... Im Detail hängt der Aufwand aber noch von der Restklasse mod 8 ab, in der die Primzahl p liegt... In dem Beispiel mit p=29 ist $\begin{eqnarray} p \equiv 5 \mod 8 \end{eqnarray}$ und da wäre im Falle, dass a überhaupt quadratischer Rest ist und außerdem $\begin{eqnarray} a^{\frac{p-1}4} \equiv 1 \mod p \end{eqnarray}$ gilt, dann $\begin{eqnarray} a^{\frac{p+3}8} \mod p \end{eqnarray}$ eine Wurzel... Da im Fall a=24 diese Voraussetzungen zutreffen, ist damit 16 wegen $\begin{eqnarray} 24^4 \equiv 16\mod 29 \end{eqnarray}$ eine Wurzel und 13 (= 29 - 16) die zweite... Eigentlich ist das in Hinblick auf die winzige Größe von p hier schon ein gewaltiger "overkill" und die von von wisili vorgeschlagene Probiermethode oder noch einfacher das Durchprobieren der Quadrate $\begin{eqnarray} (\pm 1)^2 , (\pm 2)^2, (\pm 3)^2, \ldots \mod 29 \end{eqnarray}$ bis man auf 24 stößt, natürlicher, in den kryptographischen Anwendungen, wo die Primzahlen schon mal mehrere hundert Stellen haben können, hat man diese Wahl dann nicht mehr...
21.12.2009, 10:30	Chris12345	Auf diesen Beitrag antworten »
Erstmal vielen Dank euch beiden, aber ganz raff ich das immer noch nicht... @ wisli: Das Durchprobieren ist mir noch nicht ganz klar. Wenn man das gleiche nämlich für y1 macht mit 1+19k, kommt auf jeden Fall nicht die 1 und 18 für y1 raus. Deswegen ist mir nicht ganz klar, wie du darauf gekommen bist. @ mystic: Ich verstehe nicht wie du von p=29 auf $\begin{eqnarray} p \equiv 5 \mod 8 \end{eqnarray}$ kommst. Des Weiteren weiss ich auch nicht, wie du auf $\begin{eqnarray} a^{\frac{p-1}4} \equiv 1 \mod p \end{eqnarray}$ kommst und dann $\begin{eqnarray} a^{\frac{p+3}8} \mod p \end{eqnarray}$ ableitest... @ beide: Gibt es verschiedene Wege, eine quadratische Kongruenz zu lösen, oder habt ihr den gleichen Ansatz und ich sehe ihn nicht?? Grüße Chris
21.12.2009, 11:35	wisili	Auf diesen Beitrag antworten »
@Chris k fängt mit 0 an. (Bei meinem Vorgehen steckt nichts Tiefsinniges dahinter! Ich suche einfach ein Quadrat.)
21.12.2009, 11:46	Chris12345	Auf diesen Beitrag antworten »
@wisli SUUUUUPER!! VIELEN DANK Mit k=0 stimmt's natürlich!! Echt vielen Dank!! Grüße Chris
Anzeige

21.12.2009, 13:44	Mystic	Auf diesen Beitrag antworten »
Mein Vorgehen ist nur ein winziger Teilausschnitt aus einem Algorithmus für das Wurzelziehen mod p, was wie gesagt, in Hinblick auf viele Anwendungen eine sehr wichtige Sache ist, aber ich habe an keiner Stelle begründet, warum man das so macht... Wenn du nichts damit anfangen kannst, so vergiss es am besten gleich wieder... Ich wollte damit nur dem Eindruck entgegenwirken, dass man in der Praxis bei solchen Fragestellungen prinzipiell auf bloßes "Probieren" angewiesen ist, was wie gesagt bei mehrhundertstelligen Primzahlen völlig sinnlos wäre... Edit: Doch noch als Bemerkung, dass der Fall $\begin{eqnarray} p \equiv 5 \mod 8 \end{eqnarray}$ (und dir ist hoffentlich klar, dass $\begin{eqnarray} 29 \equiv 5 \mod 8 \end{eqnarray}$ ist!) zwar noch ein "leichter" Fall ist, aber die leichtesten Fälle sind die, wo $\begin{eqnarray} p \equiv 3 \mod 4 \end{eqnarray}$ ist, denn dann sind die Wurzeln aus a mod p einfach $\begin{eqnarray} \pm a^{\frac {p+1}4} \mod p \end{eqnarray}$ wenn sie überhaupt existieren...Der noch verbleibende Fall $\begin{eqnarray} p \equiv 1 \mod 8 \end{eqnarray}$ ist dann der (vergleichsweise) schwieriegste, wo man z.B. mit Lucasfolgen (einer Verallgemenerung von Fibonaccifolgen) oder dem Algorithmus von Shanks-Tonelli arbeiten muss...
21.12.2009, 17:21	Chris12345	Auf diesen Beitrag antworten »
@Mystic: Ich fange an langsam kryptografisch zu verstehen, was eine Art Fremdsprache für mich ist Vielen Dank für die ausführliche Info, ich glaube wirklich es verstanden zu haben Jetzt probier ich es gleich mal in ner Übung anzuwenden. Mal kucken, ob ich's hinkrieg Merci beaucoup nochmal und ein fröhliches Weihnachtsfest, Chris
13.01.2010, 10:54	Chris12345	Auf diesen Beitrag antworten »
Rabin-Kryptosystem Hallo nochmal, der Thread is zwar schon ne Weile her und ich weiss auch, wie die quadratische Kongruenz gelöst werden kann, jedoch will mein Professor, dass ich das Rabin-Kryptosystem anwende und so auf das k komme. Als Tipp hat er mir folgendes aufgeschrieben: (p,q, kongruent 3 mod 4 und dann hoch (p+1)/4 ...) Kann mir da jemand weiterhelfen?? Des Weiteren verstehe ich den nachfolgenden Teil des Münzwurfs nicht so ganz... Er lautet: Die modulo m eindeutig bestimmte simultane Lösung der Kongruenzen b ž y1 mod p b ž y2 mod q ist gegeben durch b=y1µ1+ y2µ2 , mit µ1 ž 0 mod 29 und µ1 ž 1 mod 19 µ2 ž 0 mod 19 und µ2 ž 1 mod 29. Dies ist erfüllt für µ1=58, µ2=-57. Wie komme ich da jetzt auf die 58 bzw. -57?? VIELMALS DANKE SCHON IM VORRAUS, Chris
13.01.2010, 10:58	Chris12345	Auf diesen Beitrag antworten »
Ein paar Zeichen konnten leider nicht korrekt abgebildet werden, deshalb hier noch kurz ne kleine Beschreibung: ž = kongruent µ = griechischer Buchstabe Xi (frei gewählt)
18.01.2010, 09:55	Chris12345	Auf diesen Beitrag antworten »
@ Mystic Servus nochmal, du, ich hab nochmal ne Frage zu deinem Vorgehen. Ich verstehe jetzt wie du gerechnet hast, jedoch weiss ich nicht, wie du auf mod 8 gekommen bist. Dieser Tipp wäre die letzte Sache, die ich gern wissen würde. Vielen Dank schon mal im Voraus ;-) Grüße Chris

Neue Frage »

Antworten »

Wie löse ich quadratische Kongruenzen?

Verwandte Themen