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

$\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

$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

$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 $p$. Hierbei wählt man r dergestalt, dass das Legendre-Symbol

$\left({\frac {r^{2}-4x}{p}}\right)=-1$

ist. Dazu einfach verschiedene Werte von r durchprobieren. Die Folge $W_{n}$ ist rekursiv definiert:

$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 $x=3$ und $p=37$:

Nach obiger Formel sind die Quadratwurzeln von $x$ gegeben durch

$q\equiv \pm {\frac {x}{2r}}\left(W_{9}+W_{10}\right)\,{\bmod {\,}}37$

Für $r$ findet man durch Probieren den Wert $r=2$, denn es ist

$\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 $W_{9}$ und $W_{10}$ ergeben sich zu

${\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

$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 $a$ ist sie ${\bar {0}}$, da $0^{2}\equiv a\,{\bmod {\,}}2$ und für ungerade Zahlen $a$ ist sie ${\bar {1}}$, da $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 $n>1$ und eine ganze Zahl $a$. Gesucht eine Zahl $x$ mit $x^{2}\,\equiv a\,\mod n$.

n läßt sich in Primzahlpotenzen faktorisieren $n\,=\,\prod _{j=1}^{m}p_{j}^{s_{j}}$. Wenn sich für alle $j=1..m$ Lösungen von $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 $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ß $n=p^{s}$ eine Primzahlpotenz ist.

Wenn $a\equiv 0\mod n$ ist, dann ist $x=0$ bereits die Lösung und wir sind fertig, diesen Fall können wir also ausschließen. Wenn also nur $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 $a\equiv 0\mod p$ gilt, dann läßt sich keine Quadratwurzel modulo n ziehen, denn wenn $x$ eine solche wäre, dann wäre $x^{2}\equiv a\mod n$, also $x^{2}\equiv a\mod n$ nach der Definition einer Primzahl einer der beiden Faktoren des durch $p$ teilbaren Produkts $x\cdot x$ durch $p$ teilbar, also $x\equiv 0\mod p$, also $a\equiv 0modp^{2}$, was ein Widerspruch ist. Für $a$, in dem eine ungerade Potenz von $p$ steckt, gibt es also keine Quadratwurzel modulo n.

Wir können jetzt annehmen, daß $a\not \equiv 0\mod p$ ist. (Das gilt übrigens alles auch für $p=2$.)

Für $p\not =2$ kann mit dem quadratischen-Reste-Symbol geprüft werden, ob es eine Lösung $x_{0}$ mit $x_{0}^{2}\equiv a\mod p$ gibt. Genau dann läßt sich die Quadratwurzel modulo n ermitteln. Nun muß man eine Lösung $x_{0}$ finden, die modulo p stimmt.

Sei $\bigwedge _{m=0}^{\infty }q_{m}=p^{2^{m}}$ (Vereinfachung der Schreibweise im folgenden): Nun wiederholt man $x_{m+1}\equiv {\frac {{\frac {a}{x_{m}}}+x_{m}}{2}}\mod q_{m}$ solange, bis $q_{m}\geq n$. Da $a$ und $x_{m}$ und $2$ teilerfremd zu $p$ sind, kann die Division modulo Dann ist $x=x_{m+1}$ eine Lösung. Dafür muß man (z.B. durch vollständige Induktion) beweisen, daß $\bigwedge _{m=0}^{\infty }x_{m}^{2}\equiv a\mod q_{m}$ gilt. Für $m=0$ gilt das, denn wir haben $x_{0}$ so gewählt.

Wenn es für ein beliebiges $m$ gilt, dann ist also für eine gemäß Hensel-Lemma vorhandene Lösung $x$ mit $x^{2}\equiv amodp^{N}$ für ein $N$ das beliebig groß, also größer als $s$ ist, $x_{m}=x+r_{m}q_{m}$ für ein ganzzahliges $r_{m}$. Nun gilt $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 $q_{m}^{2}\equiv 0\mod q_{m+1}$ und $x^{2}\equiv a\mod q_{m+1}$ und damit $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 $p=2$ hat man die Situation, daß $x^{2}\equiv x\mod 2$ für alle $x$. Damit ist für $n=2$ bereits $x=a$ die Lösung. Für höhere 2er-Potenzen muß man und eine Lösung $x_{0}$ mit $x_{0}^{2}\equiv a\mod 4$ finden. Hier verläuft der Beweis analog, man muß aber die $q_{m}$ anders wählen, weil die Division durch $2$ jeweils die 2er-Potenz, modulo der die Kongruenz gilt, um eins niedriger ausfallen läßt, aber wir mit $q_{0}=4=2^{2^{0}+1}$ beginnen: $\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]]