Quadratische Reziprozitätsgesetz/Algorithmus/ohne Primfaktorzerlegung/Bemerkung

Es seien ${}n$ und ${}m$ ungerade verschiedene Zahlen, und man möchte das Jacobi-Symbol ${}\left({\frac {n}{m}}\right)$ berechnen (man berechnet im Allgemeinen nicht, ob ${}n$ ein quadratischer Rest modulo ${}m$ ist, dies ist nur dann der Fall, wenn ${}m$ eine Primzahl ist). Durch die Restberechnung ${}n\mod m$ können wir sofort annehmen, dass ${}n<m$ ist. Wir schreiben

${}n=2^{\alpha }k\,,$

wobei ${}k$ ungerade sei. Dann gilt nach Fakt

${}\left({\frac {n}{m}}\right)=\left({\frac {2^{\alpha }}{m}}\right)\cdot \left({\frac {k}{m}}\right)=\left({\frac {2}{m}}\right)^{\alpha }\cdot \left({\frac {k}{m}}\right)\,.$

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