Benutzer:Karl Brodowsky/Quadratwurzel modulo n

Dieser Artikel (Quadratwurzel modulo n) ist im Entstehen begriffen und noch nicht Bestandteil der freien Enzyklopädie Wikipedia.

Wenn du dies liest: Der Text kann teilweise in einer Fremdsprache verfasst, unvollständig sein oder noch ungeprüfte Aussagen enthalten. Wenn du Fragen zum Thema hast, nimm am besten Kontakt mit dem Autor Karl Brodowsky auf.

Wenn du diesen Artikel überarbeitest: Bitte denke daran, die Angaben im Artikel durch geeignete Quellen zu belegen und zu prüfen, ob er auch anderweitig den Richtlinien der Wikipedia entspricht (siehe Wikipedia:Artikel). Nach erfolgter Übersetzung kannst du diese Vorlage entfernen und den Artikel in den Artikelnamensraum verschieben. Die entstehende Weiterleitung kannst du schnelllöschen lassen. Importe inaktiver Accounts, die länger als drei Monate völlig unbearbeitet sind, werden gelöscht.

Vorlage:Importartikel/Wartung-2016-06

Anmerkung: Dieser Artikel ist noch nicht fertig geschrieben. Ich werde mich aber in der nächsten Zeit darum kümmern. Karl Brodowsky (Diskussion) 16:51, 10. Feb. 2016 (CET)

Die Quadratwurzel modulo n einer Restklasse ${\bar {a}}\;\mathrm {mod} \;n$ ist eine Restklasse ${\bar {x}}\;\mathrm {mod} \;n$ so daß gilt $x^{2}\equiv a\;\mathrm {mod} \;n$.

So lassen sich auch im Restklassenring $\mathbb {Z} /n\mathbb {Z}$ Quadratwurzeln definieren.

Allerdings muss man sich zur Berechnung von Quadratwurzeln modulo n anderer Methoden bedienen als beim Berechnen reeller oder komplexer Quadratwurzeln. Wenn es überhaupt eine ganzzahlige Lösung gibt, dann ist auch $x+n$ eine solche Lösung, deshalb gibt es unendlich viele Lösungen, die man aber, da man im Restklassenring $\mathbb {Z} /n\mathbb {Z}$ rechnet, als eine einzige Lösung ansieht.

Um die Quadratwurzeln von $x$ modulo $n$ zu bestimmen, geht man folgendermaßen vor:

Zuerst bestimmt man die Primfaktorzerlegung

$n=p_{1}^{m_{1}}\cdot p_{2}^{m_{2}}\cdots p_{k}^{m_{k}}$

und anschließend die Lösungen modulo der jeweiligen Primpotenzen $p^{m}$. Diese Lösungen setzt man schließlich mit dem Chinesischen Restsatz zur gesuchten Lösung zusammen.

Berechnung von Quadratwurzeln modulo einer Primzahl p

Für Primzahlen $p$ ungleich 2 geschieht das Berechnen der Quadratwurzeln zu $x$ so:

Um zu testen, ob $x$ überhaupt eine Quadratwurzel in $\mathbb {Z} /p\mathbb {Z}$ hat, verwendet man das Legendre-Symbol

$\left({\frac {x}{p}}\right)\equiv x^{\frac {p-1}{2}}\,{\bmod {\,}}p$,

denn es gilt

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left({\frac {x}{p}}\right)={\begin{cases}-1,&{\text{wenn }}x{\text{ kein quadratischer Rest modulo }}p{\text{ ist}}\\0,&{\text{wenn }}x{\text{ und }}p{\text{ nicht teilerfremd sind }}\\1,&{\text{wenn }}x{\text{ ein quadratischer Rest modulo }}p{\text{ ist}}\end{cases}}} .

Im ersten Falle besitzt $x$ keine Quadratwurzel in $\mathbb {Z} /p\mathbb {Z}$ und im zweiten Fall nur die Quadratwurzel 0. Der interessante Fall ist also der dritte Fall, und daher nehmen wir im folgenden an, dass ${\bigl (}{\tfrac {x}{p}}{\bigr )}=1$ ist.

Berechnung für den Fall p = 3 mod 4

Ist das Legendre-Symbol ${\bigl (}{\tfrac {x}{p}}{\bigr )}=1$, dann sind

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle q\equiv \pm x^{\frac {p+1}{4}}\,{\bmod {\,}}p}

die 2 Quadratwurzeln von $x$ modulo $p$.

Berechnung für den Fall p = 1 mod 4

Ist das Legendre-Symbol ${\bigl (}{\tfrac {x}{p}}{\bigr )}=1$, dann sind

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle q\equiv \pm {\frac {x}{2r}}\left(W_{\frac {p-1}{4}}+W_{\frac {p+3}{4}}\right)\,{\bmod {\,}}p}

die 2 Quadratwurzeln von $x$ modulo Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} . Hierbei wählt man r dergestalt, dass das Legendre-Symbol

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(\frac{r^2-4x}{p}\right) = -1}

ist. Dazu einfach verschiedene Werte von r durchprobieren. Die Folge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_n} ist rekursiv definiert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_n = \begin{cases} r^2/x-2, & \text{ wenn }n = 1\\ W_{n/2}^2-2, & \text{ wenn }n \text{ gerade}\\ W_{(n+1)/2}W_{(n-1)/2}-W_1, & \text{ wenn }n > 1 \text{ ungerade} \end{cases} } .

Rechenbeispiel für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=3} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p=37} :

Nach obiger Formel sind die Quadratwurzeln von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} gegeben durch

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle q\equiv \pm {\frac {x}{2r}}\left(W_{9}+W_{10}\right)\,{\bmod {\,}}37}

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} findet man durch Probieren den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = 2} , denn es ist

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(\frac{r^2-4x}{p}\right) \equiv (r^2-4x)^\frac{p-1}2 \equiv (-8)^{18} \equiv 36 \equiv -1\,\bmod\,37. }

Die Werte für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_9} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_{10}} ergeben sich zu

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{matrix} W_1 &\equiv& r^2/x - 2 &\equiv& 4/3 -2 &\equiv& 24 & \bmod\,37 \\ W_2 &\equiv& W_1^2-2 &\equiv& 24^2-2 &\equiv& 19 & \bmod\,37 \\ W_3 &\equiv& W_1 W_2 - W_1 &\equiv& 24\cdot 19 - 24 &\equiv& 25 & \bmod\,37 \\ W_4 &\equiv& W_2^2-2 &\equiv& 19^2-2 &\equiv& 26 & \bmod\,37 \\ W_5 &\equiv& W_2 W_3 - W_1 &\equiv& 19\cdot 25 - 24 &\equiv& 7 & \bmod\,37 \\ W_9 &\equiv& W_4 W_5 - W_1 &\equiv& 26\cdot 7 - 24 &\equiv& 10 & \bmod\,37 \\ W_{10}&\equiv& W_5^2-2 &\equiv& 7^2-2 &\equiv& 10 & \bmod\,37 \\ \end{matrix}}

Einsetzen dieser Werte ergibt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q \equiv \pm \frac{x}{2r}\left(W_9 + W_{10} \right) \equiv \pm \frac{3}{4}(10 + 10) \equiv \pm 15 \mbox{ mod } 37}

das heißt 15 und 22 sind die beiden Quadratwurzeln von 3 modulo 37.

Berechnung für den Fall p=2

Die Berechnung der Quadratwurzel modulo 2 ist trivial, für gerade Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist sie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar 0} , da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0^2 \equiv a\,\bmod\,2} und für ungerade Zahlen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} ist sie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar 1} , da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1^2 \equiv a \,\bmod\,2} .

Berechnung von Quadratwurzeln modulo einer Primzahlzahlpotenz q=p^n

Anhebung...

Berechnung modulo Zweierpotenzen

modulo 4 haben nur 0 und 1 sich selbst als Quadratwurzeln, 2 und 3 haben keine Quadratwurzeln.

modulo 8 ist 2 eine Quadratwurzel von 4, während 1, 3, 5 und 7 Quadratwurzeln von 1 sind.

Berechnung der Quadratwurzel modulo beliebigem n

Gegeben ist eine natürliche Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n>1} und eine ganze Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} . Gesucht eine Zahl Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \,\equiv a \,\mod n} .

n läßt sich in Primzahlpotenzen faktorisieren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n\,=\,\prod_{j=1}^m p_j^{s_j}} . Wenn sich für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j=1..m} Lösungen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \,\equiv a \,\mod p_j^{s_j}} finden lassen, dann läßt sich aus jeder Kombination dieser Lösungen mit dem chinesischen Restesatz eine Lösung für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \,\equiv a \,\mod n} ermitteln.

Wegen des chinesischen Restesatzes kann man n in Primzahlpotenzen faktorisieren und für jede Primzahlpotenz separat die Betrachtung machen. O.B.d.A. kann man also annehmen, daß Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=p^s} eine Primzahlpotenz ist.

Wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \equiv 0 \mod n} ist, dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=0} bereits die Lösung und wir sind fertig, diesen Fall können wir also ausschließen. Wenn also nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \equiv 0 \mod p} , dann kann man eine gerade Potenz von p aus a herausziehen, deren Quadratwurzel zu ziehen trivial ist. Wenn danach immer noch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \equiv 0 \mod p} gilt, dann läßt sich keine Quadratwurzel modulo n ziehen, denn wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} eine solche wäre, dann wäre Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \equiv a \mod n} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \equiv a \mod n} nach der Definition einer Primzahl einer der beiden Faktoren des durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} teilbaren Produkts Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\cdot x} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} teilbar, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \equiv 0 \mod p} , also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \equiv 0 mod p^2} , was ein Widerspruch ist. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , in dem eine ungerade Potenz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} steckt, gibt es also keine Quadratwurzel modulo n.

Wir können jetzt annehmen, daß Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \not\equiv 0 \mod p} ist. (Das gilt übrigens alles auch für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p=2} .)

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p\not=2} kann mit dem quadratischen-Reste-Symbol geprüft werden, ob es eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0^2 \equiv a \mod p} gibt. Genau dann läßt sich die Quadratwurzel modulo n ermitteln. Nun muß man eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0} finden, die modulo p stimmt.

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bigwedge_{m=0}^\infty q_m = p^{2^m}} (Vereinfachung der Schreibweise im folgenden): Nun wiederholt man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{m+1} \equiv \frac{\frac{a}{x_m} + x_m}{2} \mod q_m} solange, bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_m \ge n} . Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_m} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} teilerfremd zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} sind, kann die Division modulo Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = x_{m+1}} eine Lösung. Dafür muß man (z.B. durch vollständige Induktion) beweisen, daß Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bigwedge_{m=0}^\infty x_m^2 \equiv a \mod q_m} gilt. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=0} gilt das, denn wir haben Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0} so gewählt.

Wenn es für ein beliebiges Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} gilt, dann ist also für eine gemäß Hensel-Lemma vorhandene Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \equiv a mod p^N} für ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} das beliebig groß, also größer als Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} ist, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_m = x + r_m q_m} für ein ganzzahliges Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_m} . Nun gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{m+1} \equiv \frac{\frac{a}{x_m} + x_m}{2} \equiv \frac{\frac{a}{x + r_m q_m} + x + r_m q_m}{2} \equiv \frac{\frac{a(x - r_m q_m}{x^2 - r_m^2 q_m^2} + x + r_m q_m}{2} \mod q_{m+1}} , wobei gemäß der dritten binomischen Formel erweitert wurde. Nun gilt aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_m^2 \equiv 0 \mod q_{m+1}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \equiv a \mod q_{m+1}} und damit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{m+1} \equiv \frac{\frac{a(x - r_m q_m)}{x^2 - r_m^2 q_m^2} + x + r_m q_m}{2} \equiv \frac{\frac{a(x - r_m q_m)}{a} + x + r_m q_m}{2} \equiv \frac{(x - r_m q_m) + (x + r_m q_m)}{2} \equiv x \mod q_{m+1}}

q.e.d.

Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p=2} hat man die Situation, daß Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 \equiv x \mod 2} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x} . Damit ist für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n=2} bereits Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=a} die Lösung. Für höhere 2er-Potenzen muß man und eine Lösung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_0^2 \equiv a \mod 4} finden. Hier verläuft der Beweis analog, man muß aber die Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_m} anders wählen, weil die Division durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2} jeweils die 2er-Potenz, modulo der die Kongruenz gilt, um eins niedriger ausfallen läßt, aber wir mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_0=4=2^{2^0+1}} beginnen: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bigwedge_{m=0}^\infty q_m = 2^{2^m+1}}

Siehe auch

• Wurzel (Mathematik)
• Modulo, Restklassenring

Weblinks

Commons: Square root – Sammlung von Bildern, Videos und Audiodateien

[[Kategorie:Arithmetik]] [[Kategorie:Zahlentheorie]]