Quadratwurzeln modulo p^t < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:17 So 13.05.2007 | | Autor: | DaSaver |
| Aufgabe | Uberlege Dir ein Verfahren um effzient Quadratwurzeln modulo [mm] p^t [/mm] für ein [mm]t\ge1[/mm] zu bestimmen. Finde also ein Verfahren um für gegebenes a einen Wert x so zu bestimmen, dass
[mm]x^2\equiv a \mod p^t[/mm]
gilt.
Hinweis: Schreibe x in der p-adischen Entwicklung, d.h. [mm]x = x_{0} + x_{1}p+\ldots+x_{t-1}p^{t-1}[/mm], und bestimme x in mehreren Schritten. |
Hallo!
Die Aufgabe steht oben. Wir haben schon ein Verfahren gemacht wie man Quadratwurzeln modulo p bestimmt (p prim). Und nun sollen wir dieses auch hier irgendwie anwenden. Das Problem ist, das Verfahren habe ich nicht so richtig verstanden und so habe ich auch bei dieser Aufgabe Schwierigkeiten... Vielleicht kann mir ja jemand helfen! Wäre auf jeden Fall sehr dankbar!
Gruß,
Michael
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:27 So 13.05.2007 | | Autor: | felixf |
Hallo Michael!
> Uberlege Dir ein Verfahren um effzient Quadratwurzeln
> modulo [mm]p^t[/mm] für ein [mm]t\ge1[/mm] zu bestimmen. Finde also ein
$p$ soll sicher eine ungerade Primzahl sein, oder?
> Verfahren um für gegebenes a einen Wert x so zu bestimmen,
> dass
> [mm]x^2\equiv a \mod p^t[/mm]
> gilt.
>
> Hinweis: Schreibe x in der p-adischen Entwicklung, d.h. [mm]x = x_{0} + x_{1}p+\ldots+x_{t-1}p^{t-1}[/mm],
> und bestimme x in mehreren Schritten.
Die Koeffizienten [mm] $x_0, \dots, x_{n-1}$ [/mm] zu bestimmen heisst ja gerade, eine Quadratwurzel von $a$ modulo [mm] $p^n$ [/mm] zu bestimmen.
> Die Aufgabe steht oben. Wir haben schon ein Verfahren
> gemacht wie man Quadratwurzeln modulo p bestimmt (p prim).
> Und nun sollen wir dieses auch hier irgendwie anwenden. Das
> Problem ist, das Verfahren habe ich nicht so richtig
> verstanden und so habe ich auch bei dieser Aufgabe
> Schwierigkeiten... Vielleicht kann mir ja jemand helfen!
> Wäre auf jeden Fall sehr dankbar!
Das Verfahren brauchst du hierfuer nicht zu verstehen. Du musst nur wissen, dass man damit [mm] $x_0$ [/mm] berechnen kann (da nach der obigen Bemerkung das gerade heisst, dass du die Quadratwurzel modulo $p$ bestimmst).
Jetzt musst du dir ueberlegen, wie du, wenn du [mm] $x_0, \dots, x_{n-1}$ [/mm] bestimmt hast, auch [mm] $x_n$ [/mm] bestimmen kannst. Dann bist du per Induktion fertig: du bestimmst schrittweise [mm] $x_1$, $x_2$, $x_3$, $\dots$ [/mm] bis du schliesslich [mm] $x_{t-1}$ [/mm] hast und damit ganz $x$.
Wie du da jetzt konkret vorgehst: Wenn du [mm] $x_0, \dots, x_{n-1}$ [/mm] bestimmt hast, dann weisst du, dass [mm] $(x_0 [/mm] + [mm] x_1 [/mm] p + [mm] \dots [/mm] + [mm] x_{n-1} p^{n-1})^2 \equiv [/mm] a [mm] \pmod{p^n}$ [/mm] ist. Um etwas Schreibarbeit zu sparen definier ich mal $A := [mm] x_0 [/mm] + [mm] x_1 [/mm] p + [mm] \dots [/mm] + [mm] x_{n-1} p^{n-1}$; [/mm] dann ist [mm] $A^2 [/mm] - a = k p$ fuer ein $k [mm] \in \IZ$, [/mm] also [mm] $A^2 [/mm] = a + k p$.
So. Fuer [mm] $x_n$ [/mm] soll jetzt gelten $(A + [mm] x_n p^n)^2 [/mm] = [mm] (x_0 [/mm] + [mm] \dots [/mm] + [mm] x_{n-1} p^{n-1} [/mm] + [mm] x_n p^n)^2 \equiv [/mm] a [mm] \pmod{p^{n+1}}$. [/mm] Nun ist $(A + [mm] x_n p^n)^2 [/mm] = [mm] A^2 [/mm] + 2 A [mm] x_n p^n [/mm] + [mm] x_n^2 p^{2 n} \equiv A^2 [/mm] + 2 A [mm] x_n p^n \pmod{p^{n+1}}$. [/mm] Also muss [mm] $A^2 [/mm] + 2 A [mm] x_n p^n [/mm] + [mm] x_n^2 p^{2 n} \equiv [/mm] a [mm] \pmod{p^{n+1}}$ [/mm] sein.
Jetzt kannst du ganz einfach [mm] $x_n$ [/mm] berechnen.
LG Felix
|
|
|
|
