Modulare quadratische Gleichung

Neue Frage »

Simon95 Auf diesen Beitrag antworten »
Modulare quadratische Gleichung
Die Aufgabe lautet: Entscheide, ob eine Lösung besitzt.

Dazu berechne ich das Legendre-Symbol:



Als Ergebnis sollte aber -1 herauskommen, denn wenn ich auf andere Weise nachrechne
(Programm testet alle quadratischen Reste), dann sehe ich, dass 2044 nicht quadratischer
Rest vom Modul 2047 ist. Was mache ich falsch?

lg
Simon
HAL 9000 Auf diesen Beitrag antworten »

Deine Rechnung sieht so aus, als würdest du annehmen, dass 2047 eine Primzahl ist...
Simon95 Auf diesen Beitrag antworten »

Hallo,

danke für den Hinweis. Jetzt sehe ich den Fehler auch. Dann stellt sich für mich allerdings die Frage:
Mit welcher Methode kann ich herausfinden, ob 2044 quadratischer Rest von 2047 ist?

Ich bin übrigens weder Schüler noch Student. Mir geht es hauptsächlich darum, eine allgemein gültige
Methode zu finden, mit der sich schnell und effizient bestimmen lässt, ob eine Zahl a quadratischer Rest
bezüglich eines Moduls m ist.

lg
Simon
HAL 9000 Auf diesen Beitrag antworten »

Wenn eine Zahl quadratischer Rest modulo sein soll, dann muss sie es auch für alle Primzahlpotenzteiler von sein - dass letzteres notwendig ist, sollte sofort klar sein. Dass es auch hinreichend ist, bestätigt der Chinesische Restsatz.

Somit erfordert auch notwendig , was sich als unmöglich erweist.
Simon95 Auf diesen Beitrag antworten »

Hallo,

nochmals vielen Dank, und sehr schön auf den Punkt gebracht. Das Problem ist nur:

Was ist, wenn die Primfaktor-Zerlegung nicht bekannt ist?

lg
Simon
HAL 9000 Auf diesen Beitrag antworten »

Dann führt man sie eben durch - hast du ja oben bei 2044 auch gemacht.
 
 
Simon95 Auf diesen Beitrag antworten »

Das geht leider nicht. Die Zahlen die ich testen muss sind zu groß.

lg
Simon
HAL 9000 Auf diesen Beitrag antworten »

Fängt an mit einer harmlosen Aufgabe, macht einen dicken Anfängerfehler und rückt dann erst mit der Info raus, dass er extrem große Module betrachtet. Verheimlichst du sonst noch was? Augenzwinkern
Simon95 Auf diesen Beitrag antworten »

Nö, ich wusste selbst nicht, dass sich das zu einem solchen Problem entwickelt.

Ich dachte es genügt, das Legendre-Symbol zu berechnen. Da ich darin aber keine
Erfahrung habe, dachte ich, ich mache etwas falsch. Erst durch Dein Posting wurde
mir klar, dass man hier genau darauf achten muss, dass der Nenner eine Primzahl
sein muss.

lg
Simon
HAL 9000 Auf diesen Beitrag antworten »

Es gibt zumindest Methoden, für extrem große Zahlen mit vergleichsweise wenig Aufwand festzustellen, dass sie keine Primzahlen sind - ohne ihre Faktorisierung vornehmen zu können, z.B.

http://de.wikipedia.org/wiki/Miller-Rabin-Test
Simon95 Auf diesen Beitrag antworten »

Hallo,

nochmals danke für den Hinweis. Aber was ich suche ist eine Methode, mit der sich bestimmen lässt, ob eine Zahl quadratischer Rest bezüglich eines Moduls ist, wobei und beliebige Zahlen sind und keine Primzahl sein muss.

Bisher dachte ich, es genügt das Legendre-Symbol zu berechnen. Das war ein Fehlschluß. Im Internet habe ich jetzt das gefunden:

w w w .primath.homepage.t-online.de/Homepagedateien/QuaRe.pdf

In Überschrift 2.c Prüfung ob Qadr. Rest eines mit unbekannter Primfaktorzerlegung ist findet sich die Aussage:

Zur Entscheidung dieser Frage kann zunächst das Jacobi-Symbol befragt werden: Ist das Ergbnis -1 steht fest, dass kein QR ist. Hat dagegen das Jacobi-Symbol den Wert 1, lässt sich daraus nur folgern,dass mit einer Wahrscheinlichkeit von 50% ein QR ist ...

Und weiters:

Da keine weiteren Kriterien bekannt sind, kann für eine beliebige vorgelegte Zahl nicht entschieden werden, dass sie ein QR modulo ist.

Wenn das stimmt, dann gibt es für dieses Problem offenbar keine andere Lösung als probieren.

lg
Simon
Neue Frage »
Antworten »



Verwandte Themen

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