Modulo Quadratische Gleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:48 Mi 03.10.2012 | | Autor: | Erbse |
| Aufgabe | Gleichung:
[mm] x^{2} [/mm] = m mod n
Wobei n = p*q und p,q zwei unterschiedliche Primzahlen |
Die Lösung berechnet x durch Anwendung des Chinesischen Restsatzes:
Es wird r = m mod p, s = m mod q
Nun ist r = [mm] a^{2} [/mm] mod p und s = [mm] b^{2} [/mm] mod q
Die Idempotente mod n sind e bzg p und f bzg q
Die Beziehung [mm] x^{2} [/mm] = r * e + s * f mod n leuchtet mir ein,
doch die Lösung folgert x = a * e + b * f
Welcher Satz, oder welche Beziehung wird hierbei ausgenutzt?
Vielen Dank für die Mühle
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:52 Do 04.10.2012 | | Autor: | hippias |
> Gleichung:
> [mm]x^{2}[/mm] = m mod n
> Wobei n = p*q und p,q zwei unterschiedliche Primzahlen
> Die Lösung berechnet x durch Anwendung des Chinesischen
> Restsatzes:
>
> Es wird r = m mod p, s = m mod q
> Nun ist r = [mm]a^{2}[/mm] mod p und s = [mm]b^{2}[/mm] mod q
>
> Die Idempotente mod n sind e bzg p und f bzg q
> Die Beziehung [mm]x^{2}[/mm] = r * e + s * f mod n leuchtet mir
> ein,
> doch die Lösung folgert x = a * e + b * f
>
> Welcher Satz, oder welche Beziehung wird hierbei
> ausgenutzt?
Ich verstehe Deine Frage nicht so ganz: Das $x$ ist zu konstruieren, dazu wird $x:= a * e + b * f$ gesetzt und die gewuenschte Eigenschaft nachgerechnet; insbesondere werden die besonderen Eigenschaften von $e$ und $f$ dabei benutzt.
> Vielen Dank für die Mühle
Gerne geschehen: aber pass auf den Raeuber Hotzenplotz auf!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:44 Sa 06.10.2012 | | Autor: | Erbse |
Und wieso darf ich das x so berechnen?
Warum "fallen" die Quadrate dann auf einmal weg?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:16 So 07.10.2012 | | Autor: | leduart |
Hallo
du kannst doch x erstmal einfach so ansetzen, überlegen was für e,f gelten muss, dann [mm] x^2 [/mm] bilden!
Gruss leduart
|
|
|
|
