?
Christoph schrieb:
Dazu braucht man schon ein bisschen Zahlentheorie, würd ich sagen. Das Legendre-Symbol, geschrieben (a/p), sagt dir, ob x^2 = a (mod p) eine Lösung hat oder nicht. Das geht in die folgende Richtung:
Für a != 0 (mod p) gilt: Wenn a^((p-1)/2) = 1 (mod p) ist, dann hat x^2 = a (mod p) eine Lösung, sonst nicht.
Die Idee dahinter ist: Angenommen wir können a schreiben als x^2 (modulo p). Dann ist a^((p-1)/2) = x^(p-1) = 1 (mod p) wegen des kleines Satzes von Fermat.
Die andere Richtung bekomm ich auf die Schnelle nicht hin, das ist aber möglicherweise ein einfaches Abzählargument.
Damit kannst du zumindest schonmal sehr schnell entscheiden, ob es eine Lösung gibt oder nicht, denn a^((p-1)/2) (mod p) kann man sehr schnell ausrechnen.
Einen effizienten Algorithmus, um die Lösung auszurechnen, wenn sie existiert, kenn ich aber nicht. Viele Mathematiker geben sich eben damit zufrieden, die Existenz einer Lösung zu beweisen.
Es gibt aber mit Sicherheit Leute, die sich über das Berechnen so einer Lösung schon Gedanken gemacht haben. Vielleicht hast du Glück es gibt sogar einen guten Algorithmus, aber ich würde nicht zu sehr hoffen.
Shanks-Tonelli algo