Modulo r^2 berechnen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:36 Mo 27.06.2011 | | Autor: | Ph0eNiX |
| Aufgabe | | Finde r in 31 = [mm] r^2 [/mm] mod 33 |
Hallo Zusammen!
Wie berechne ich r in: 31 = [mm] r^2 [/mm] mod 33 ?!? Bemerkung: dies ist ein nomales Gleichheitszeichen und nicht kongruent odr so! Eigentlich müsste es ja wurzel(31) sein oder nicht?! Oder mit dem erweiterten euklidischen Algorithmus berechnen?! Denn eine mögliche Lösung für r ist 8 das weiss ich und stimmt auch...nur wie komm ich darauf?
Ursprung ist das Fiat-Shamir Protokoll bei dem x mod n = [mm] r^2 [/mm] mod n. Da ich in der Aufgabe aber x habe, was 31 ist und n= 35 ist 31 mod 35 natürlich 31 und somit 31 = [mm] r^2 [/mm] mod 33...
Vielen Dank!
Freundliche Grüsse Ph0eNiX
|
|
| |
|
Hallo Ph0eNiX,
> Finde r in 31 = [mm]r^2[/mm] mod 33
>
> Hallo Zusammen!
> Wie berechne ich r in: 31 = [mm]r^2[/mm] mod 33 ?!? Bemerkung: dies
> ist ein nomales Gleichheitszeichen und nicht kongruent odr
> so!
Das schreibt man gern aus Faulheit so hin, so auch der Aufgabensteller. Eigentlich muss da natürlich das [mm] \equiv [/mm] -Zeichen stehen.
> Eigentlich müsste es ja wurzel(31) sein oder nicht?!
Nein, das klappt in der Modulrechnung leider nicht.
> Oder mit dem erweiterten euklidischen Algorithmus
> berechnen?! Denn eine mögliche Lösung für r ist 8 das
> weiss ich und stimmt auch...nur wie komm ich darauf?
Der erweiterte euklidische Algorithmus funktioniert auch noch nicht so recht. Die Frage ist, wie weit Du in der Zahlentheorie schon vorgedrungen bist bzw. was Du über quadratische Reste weißt.
> Ursprung ist das Fiat-Shamir Protokoll bei dem x mod n =
> [mm]r^2[/mm] mod n. Da ich in der Aufgabe aber x habe, was 31 ist
> und n= 35 ist 31 mod 35 natürlich 31 und somit 31 = [mm]r^2[/mm]
> mod 33...
Was denn nun, n=35 oder n=33?
In jedem Fall kannst Du bei so kleinen Zahlen natürlich einfach eine Tabellenkalkulation anschmeißen und ausprobieren.
Bei etwas größeren Zahlen würde man den chinesischen Restsatz bemühen und den Modul erst einmal faktorisieren (hier für [mm] n=\blue{33} [/mm] ):
33=3*11, daher: [mm] r^2\equiv 31\mod{33}\quad\gdw\quad r^2\equiv 1\mod{3} \wedge \r^2\equiv 9\mod{11}
[/mm]
Für beide Kongruenzen bekommst Du zwei Lösungen. Das heißt, dass es [mm] \mod{33} [/mm] vier Lösungen geben muss. Zur Kontrolle: diese sind 8,14,19, und 25. (Nebenbei: [mm] \mod{35} [/mm] ist die Aufgabe nicht lösbar.)
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:50 Mo 27.06.2011 | | Autor: | Ph0eNiX |
Hallo reverend
Vielen Dank für die schnelle Antwort!
Mhh mit quadratischem Rest sind wir noch nicht soo weit, hauptsächlich mit der Tabellenkalkulation die du erwähnt hast! Das war auch das ausschlaggebende, habe nicht verstanden wie man [mm] r^2 \equiv [/mm] 31 mod 33 berechnen soll, so ist ja einfach! Danke! Aber muss wohl mal den chinesische Restsatz anschauen :)
Uups, entschuldigung ist natürlich überall mod 33 wie du richtig erkannt hast!
Vielen Dank fürs Helfen!
Liebe Grüsse
Ph0eNiX
|
|
|
| |
|
> Finde r in 31 = [mm]r^2[/mm] mod 33
> Hallo Zusammen!
> Wie berechne ich r in: 31 = [mm]r^2[/mm] mod 33 ?!? Bemerkung: dies
> ist ein nomales Gleichheitszeichen und nicht kongruent odr
> so! Eigentlich müsste es ja wurzel(31) sein oder nicht?!
> Oder mit dem erweiterten euklidischen Algorithmus
> berechnen?! Denn eine mögliche Lösung für r ist 8 das
> weiss ich und stimmt auch...nur wie komm ich darauf?
>
> Ursprung ist das Fiat-Shamir Protokoll bei dem x mod n =
> [mm]r^2[/mm] mod n. Da ich in der Aufgabe aber x habe, was 31 ist
> und n= 35 ist 31 mod 35 natürlich 31 und somit 31 = [mm]r^2[/mm]
> mod 33...
>
> Vielen Dank!
> Freundliche Grüsse Ph0eNiX
Hallo Föhnix,
ich verstehe überhaupt nicht, wie du da zwischen Aussagen
bezüglich der Basen (Moduli) 33 und 35 (oder sogar auch
noch 31 ?) herumjonglierst.
Falls das kein FellHerr ist und nicht nur deiner Panthasei entspringt:
wo könnte ich mich darüber schlau machen ?
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:54 Mo 27.06.2011 | | Autor: | Ph0eNiX |
Hallo Al-Chwarizmi
Entschuldigung, das ist mein Fehler, ist natürlich alles mod 33. Grundsätzlich ist es einfach [mm] r^2 \equiv [/mm] 31 mod 33 ;)
Ist Das Fiat-Shamir Protokoll http://de.wikipedia.org/wiki/Fiat-Shamir-Protokoll ;)
Liebe Grüsse
Ph0eNiX
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:40 Mo 27.06.2011 | | Autor: | felixf |
Moin!
> berechnen?! Denn eine mögliche Lösung für r ist 8 das
> weiss ich und stimmt auch...nur wie komm ich darauf?
Im Allgemeinen berechnet man das so:
* faktorisiere den Modulus $n = [mm] \prod_{i=1}^k p_i^{e_i}$
[/mm]
* finde [mm] $x_i$ [/mm] mit [mm] $x_i^2 \equiv [/mm] x [mm] \pmod{p_i^{e_i}}$
[/mm]
* rekonstruiere mit dem Chinesischen Restsatz das $x$ aus den [mm] $x_i$
[/mm]
Um [mm] $x_i$ [/mm] zu finden, findest du es erst modulo [mm] $p_i$, [/mm] dann modulo [mm] $p_i^2$, [/mm] dann modulo [mm] $p_i^3$, [/mm] ..., bis du es schliesslich modulo [mm] $p_i^{e_i}$ [/mm] hast. Das Liften von [mm] $p_i^j$ [/mm] nach [mm] $p_i^{j+1}$ [/mm] geht mit dem Henselschen Lemma, man bekommt hier einen einfachen Ausdruck. (Das funktioniert nur fuer [mm] $p_i \neq [/mm] 2$. Fuer [mm] $p_i [/mm] = 2$ musst du etwas anders vorgehen.)
Um schliesslich [mm] $x_i$ [/mm] modulo [mm] $p_i$ ($\neq [/mm] 2$) zu bestimmen, verwendest du z.B. den ![[]](/images/popup.gif) Algorithmus von Tonelli und Shanks.
Bei solch kleinen Zahlen wie hier im Beispiel fuehrt ein Taschenrechner oder eine Tabellenkalkulation wohl schneller zum Ziel...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:26 Mi 29.06.2011 | | Autor: | Ph0eNiX |
Hallo felixf
Vielen Dank für deine sehr ausführliche Antwort :)) Erscheint mir doch relativ schwierig, besonders da wir einige Dinge die du erwähnt hast noch gar nicht behandelten im Unterricht, aber interessant allemal :))
Liebe Grüsse
Phoenix
|
|
|
|
