primzahl kongruenz



  • hallo,

    hab mal wieder eine frage zur kongruenz:

    x2 ≡ a mod p

    p... ist eine primzahl ab 3 (also nicht 2) und so weiter, also 3, 5, 7, ...
    a... ist eine element aus 1, 2, ... , p-1

    wie löst man denn dieses problem am besten, um zu entscheiden, ob die kongruenz lösbar ist?



  • beispiele:

    p=3:

    1 mod 3 = 1
    2 mod 3 = 2

    p=5:

    1 mod 5 = 1
    2 mod 5 = 2
    3 mod 5 = 3
    4 mod 5 = 4

    was ich nicht verstehe ist das x2



  • ist p prim, dann ist die Kongruenz immer lösbar. Unter Umständen kann es sogar mehr als eine Lösung geben. Ist p nicht prim, dann wird das alles eh viel komplizierter.

    Beispiel zu p=prim:
    angenommen a ist 4 und p=5.

    dann ist x=3 die Lösung. weil: x*x mod 5=3*3 mod 5=9 mod 5 =4 mod 5 =a
    aber auch x=2 : 2*2 mod 5=4 mod 5=a

    wie genau man das berechnet...keine Ahnung, zu lange her.



  • otze schrieb:

    ist p prim, dann ist die Kongruenz immer lösbar.

    Bist du dir sicher? Als Gegenbeispiel würde ich auf die Schnelle p = 3 und a = 2 anführen.

    Oder um ein wenig formeller zu argumentieren:

    $x^2 \equiv a \quad (p)\\ \Leftrightarrow p \mid (x^2 - a)\\ \Leftrightarrow p \mid (x + \sqrt{a}) \vee p \mid (x - \sqrt{a})$

    Die letzte Äquivalenz gilt gerade weil p prim ist. Dann muss $$\sqrt{a} \in Z$$ sein.


  • Mod

    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.



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

    schneller gehts mit reziprozitätsgesetz



  • Michael E. schrieb:

    Bist du dir sicher? Als Gegenbeispiel würde ich auf die Schnelle p = 3 und a = 2 anführen.

    Hast mich überzeugt 🙂

    Keine Ahnung, mit irgendwas hatte ich das verwechselt. Ignoriert meinen post 😉



  • 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


Log in to reply