Modulare Quadratwurzel von Kompositzahlen

05.02.2020, 09:19

Hosenschlange

Modulare Quadratwurzel von Kompositzahlen

Guten Morgen,

ich bin auf der Suche nach einem Lösungsweg, um modulare Quadratwurzeln x^2 = 1 (mod m) für Kompositzahlen zu finden. Was Primpotenzen betrifft, kann man den Adleman-Miller-Test verwenden. Bei anderen Zahlen, wie z. B. 8 oder 20, wird das natürlich nichts.
Ist das wiederum eine Sache für den Chinesischen Restsatz, oder gibt es noch andere Möglichkeiten?

05.02.2020, 11:22

Elvis

Auf diesen Beitrag antworten »

Dafür haben wir in der Zahlentheorie das quadratische Reziprozitätsgesetz erfunden. Du stellst die Frage, ob 1 ein quadratischer Rest mod m ist (https://de.wikipedia.org/wiki/Quadratischer_Rest), siehe auch Legendre-Symbol (https://de.wikipedia.org/wiki/Legendre-Symbol) und Jacobi-Symbol (https://de.wikipedia.org/wiki/Jacobi-Symbol).

Entschuldigung, du suchst die Quadratwurzeln, das ist etwas anderes. Ich weiß nur, ob es eine gibt, und das ist für $\begin{eqnarray*} 1=1^2=(-1)^2 \end{eqnarray*}$ ohnehin kein Problem.

05.02.2020, 12:15

Hosenschlange

Auf diesen Beitrag antworten »

Genau. 1 und -1 sind m. E. trivial. Aber für n = 8 existieren ja auch noch x = +-3 bzw +-5, so dass x^2 = 1 (mod 8).

05.02.2020, 19:59

HAL 9000

Auf diesen Beitrag antworten »

Sei Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ in der Potenz $\begin{eqnarray*} p^k \end{eqnarray*}$ in der Primfaktorzerlegung von $\begin{eqnarray*} m \end{eqnarray*}$ enthalten. Dann kannst du doch erstmal diese Kongruenzen

$\begin{eqnarray*} (x+1)(x-1)\equiv 0\bmod p^k \end{eqnarray*}$

getrennt lösen (für ungerade Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ kein Problem; für $\begin{eqnarray*} p=2 \end{eqnarray*}$ sind die Betrachtungen ein wenig anders, aber auch nicht so sehr kompliziert), um dann abschließend die Lösungen dieser Einzelkongruenzen zu Lösungen des Ausgangsproblems zusammenzubasteln, via Chinesischem Restsatz.

Für $\begin{eqnarray*} m=2^e\cdot p_1^{e_1}\cdot \ldots p_r^{e_r} \end{eqnarray*}$ mit paarweise verschiedenen ungeraden Primzahlen $\begin{eqnarray*} p_k \end{eqnarray*}$ sowie $\begin{eqnarray*} e_k>0 \end{eqnarray*}$ für alle $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} e\geq 0 \end{eqnarray*}$ dürfte damit zumindest schon mal die Anzahl der Lösungen dieser Kongruenz $\begin{eqnarray*} x^2\equiv 1\bmod m \end{eqnarray*}$ klar sein:

$\begin{eqnarray*} 2^{\max(\min(e-1,2),0)+r} \end{eqnarray*}$ .

Ein Beispiel:

$\begin{eqnarray*} x^2\equiv 1\bmod 240 \end{eqnarray*}$ hat wegen $\begin{eqnarray*} 240=2^4\cdot 3\cdot 5 \end{eqnarray*}$ dann $\begin{eqnarray*} 2^{2+2}=16 \end{eqnarray*}$ Lösungen, die sich aus der Kombination von

( $\begin{eqnarray*} x\equiv \pm 1\bmod 16 \end{eqnarray*}$ oder $\begin{eqnarray*} x\equiv \pm 7\bmod 16 \end{eqnarray*}$ ) mit $\begin{eqnarray*} x\equiv \pm 1\bmod 3 \end{eqnarray*}$ und $\begin{eqnarray*} x\equiv \pm 1\bmod 5 \end{eqnarray*}$ ergeben, das sind letztlich $\begin{eqnarray*} \pm \{1,31,41,49,71,79,89,119\} \end{eqnarray*}$

EDIT (9.2.): Hmm, Interesse verloren - schade um die Tippmühe. unglücklich

10.02.2020, 14:58

Hosenschlange

Auf diesen Beitrag antworten »

Für Zweierpotenzen scheint zu gelten $\begin{eqnarray*} x\equiv \pm (2^{k-1} + 1) (mod 2^{k}) \end{eqnarray*}$ . Was die übrigen Primpotenzen $\begin{eqnarray*} p^{k}, p > 2, k > 0, \end{eqnarray*}$ angeht, besteht lediglich $\begin{eqnarray*} x\equiv \pm 1 (mod p^{k}) \end{eqnarray*}$ .

10.02.2020, 16:01

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Hosenschlange
Für Zweierpotenzen scheint zu gelten $\begin{eqnarray*} x\equiv \pm (2^{k-1} + 1) (mod 2^{k}) \end{eqnarray*}$

... was exakt $\begin{eqnarray*} x\equiv \mp (2^{k-1} - 1) \bmod 2^{k} \end{eqnarray*}$ entspricht. Aber das ist nur die eine Hälfte der Lösungen modulo $\begin{eqnarray*} 2^k \end{eqnarray*}$ im Fall $\begin{eqnarray*} k\geq 3 \end{eqnarray*}$ , die andere (einfachere) Hälfte $\begin{eqnarray*} x\equiv \pm 1\bmod 2^{k} \end{eqnarray*}$ ist natürlich ebenfalls Lösung.

Man könnte das natürlich auch kurz zusammenfassen zu $\begin{eqnarray*} x\equiv \pm 1\bmod 2^{k-1} \end{eqnarray*}$ , und damit etwa als Lösungen von meinem Beispiel $\begin{eqnarray*} x^2\equiv 1\bmod 240 \end{eqnarray*}$ dann die Werte $\begin{eqnarray*} x = \pm \{1,31,41,49\}\bmod 120 \end{eqnarray*}$ . Diese 8 Lösungen modulo 120 entsprechen dann 16 Lösungen modulo 240.

12.02.2020, 20:31

Hosenschlange

Auf diesen Beitrag antworten »

Danke soweit erstmal Freude

Neue Frage »

Antworten »

Modulare Quadratwurzel von Kompositzahlen

Verwandte Themen