Kardinalität quadratischer Reste von N=p*q

13.11.2015, 21:08	crt	Auf diesen Beitrag antworten »
*Kardinalität quadratischer Reste von N=pq Meine Frage:** Hallo, gegeben ist eine Zahl $\begin{eqnarray} N=pq \end{eqnarray}$ , wobei $\begin{eqnarray} p\neq q \end{eqnarray}$ und $\begin{eqnarray} p,q \end{eqnarray}$ ungerade. Die Menge der Zahlen mit Jacobi-Symbol $\begin{eqnarray} +1 \end{eqnarray}$ ist: $\begin{eqnarray} \|J_{N}^{+1}\|=\left\{x\in Z_{n}^{}:\left(\frac{x}{N}\right)=+1\right\} \end{eqnarray}$ Z.z. ist, dass (a) $\begin{eqnarray} \|J_{N}^{+1}\|=\frac{\|Z_{n}^{}\|}{2} \end{eqnarray}$ und (b) $\begin{eqnarray} \|\text{Quadratische Reste}\|=\frac{\|J_{N}^{+1}\|}{2} \end{eqnarray}$ . Meine Ideen:* Zu (a): Ich weiß, dass die Anzahl der quadratischen Reste in p und q, jeweils die Hälfte der Elemente sind. Durch die Multiplikativität im Nenner des Jacobi-Symbols kann dieses nur 1 sein, wenn die Jacobi-Symbole von x über p bzw. q beide 1 oder -1 sind. Vermutlich kann man mit dem chinesischen Restsatz eine Verbindung herstellen, allerdings weiß ich nicht wie. Geschweige denn, wie ich es mathematisch korrekt formuliere. Zu (b): Vermutlich ein ähnlicher Ansatz wie in (a). Über Tipps würde ich mich sehr freuen!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »