Quadratische Reziprozitätsgesetz/Algorithmus/ohne Primfaktorzerlegung/Bemerkung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Seien und ungerade verschiedene Zahlen, und man möchte das Jacobi-Symbol berechnen (man berechnet im Allgemeinen nicht, ob ein quadratischer Rest modulo ist, dies ist nur dann der Fall, wenn eine Primzahl ist). Durch die Restberechnung können wir sofort annehmen, dass ist. Wir schreiben

wobei ungerade sei. Dann gilt nach Fakt

Hier kann, nach dem quadratischen Reziprozitätsgesetz für das Jacobi-Symbol (und der Ergänzungssätze), berechnet werden und kann auf zurückgeführt werden. Bei diesem Verfahren werden natürlich die Nenner (und damit auch die Zähler) in den Jacobi-Symbolen kleiner, so dass man schließlich das Resultat erhält.