Quadratisches Reziprozitätsgesetz/Algorithmische Berechnung/Mit Primfaktorzerlegung/Bemerkung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Seien und ungerade verschiedene Primzahlen, und man möchte berechnen, also herausfinden, ob ein quadratischer Rest modulo ist oder nicht. Ist , so berechnet man zuerst den Rest , und ersetzt durch den kleineren Rest, der natürlich keine Primzahl sein muss. Ist hingegen , so berechnet man die Reste von und modulo und kann dann mittels dem quadratischen Reziprozitätsgesetz auf zurückführen. In beiden Fällen kommt man also auf eine Situation, wo zu berechnen ist, wo eine ungerade Primzahl ist und beliebig.

Sei die Primfaktorzerlegung von . Dann ist nach der Multiplikativität des Legendre-Symbols

Jetzt kann nach dem zweiten Ergänzungsgesetz berechnet und die können für nach dem gleichen Verfahren auf die Berechnung von zurückgeführt werden (von den Exponenten kommt es nur auf die Parität an). Bei diesem Verfahren werden natürlich die Nenner (und damit auch die Zähler) in den Legendre-Symbolen kleiner, so dass man schließlich das Resultat erhält.