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 $pmodq$, 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,\dots ,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, sodass man schließlich das Resultat erhält.