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

Es seien ${}p$ und ${}q$ ungerade verschiedene Primzahlen, und man möchte ${}\left({\frac {p}{q}}\right)$ berechnen, also herausfinden, ob ${}p$ ein quadratischer Rest modulo ${}q$ ist oder nicht. Ist ${}p>q$, so berechnet man zuerst den Rest ${}p\mod q$, und ersetzt ${}p$ durch den kleineren Rest, der natürlich keine Primzahl sein muss. Ist hingegen ${}p<q$, so berechnet man die Reste von ${}p$ und ${}q$ modulo ${}4$ und kann dann mittels dem quadratischen Reziprozitätsgesetz ${}\left({\frac {p}{q}}\right)$ auf ${}\left({\frac {q}{p}}\right)$ zurückführen. In beiden Fällen kommt man also auf eine Situation, wo ${}\left({\frac {k}{q}}\right)$ zu berechnen ist, wo ${}q$ eine ungerade Primzahl ist und ${}k<q$ beliebig.

Es sei ${}k=2^{\alpha }\cdot p_{1}^{\alpha _{1}}\cdots p_{r}^{\alpha _{r}}$ die Primfaktorzerlegung von ${}k$. Dann ist nach der Multiplikativität des Legendre-Symbols

${}\left({\frac {k}{q}}\right)=\left({\frac {2^{\alpha }}{q}}\right)\cdot \left({\frac {p_{1}^{\alpha _{1}}}{q}}\right)\cdots \left({\frac {p_{r}^{\alpha _{r}}}{q}}\right)=\left({\frac {2}{q}}\right)^{\alpha }\cdot \left({\frac {p_{1}}{q}}\right)^{\alpha _{1}}\cdots \left({\frac {p_{r}}{q}}\right)^{\alpha _{r}}\,.$

Jetzt kann ${}\left({\frac {2}{q}}\right)$ nach dem zweiten Ergänzungsgesetz berechnet und die ${}\left({\frac {p_{i}}{q}}\right)$ können für ${}i=1,\ldots ,r$ nach dem gleichen Verfahren auf die Berechnung von ${}\left({\frac {q}{p_{i}}}\right)$ zurückgeführt werden (von den Exponenten ${}\alpha ,\alpha _{i}$ 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.