www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Gruppe, Ring, Körper" - Modulo r^2 berechnen
Modulo r^2 berechnen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Modulo r^2 berechnen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
Modulo r^2 berechnen: Antwort
Status: (Antwort) fertig Status 
Datum: 19:58 Mo 27.06.2011
Autor: reverend

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


Bezug
                
Bezug
Modulo r^2 berechnen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Modulo r^2 berechnen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:04 Mo 27.06.2011
Autor: Al-Chwarizmi


> 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


Bezug
                
Bezug
Modulo r^2 berechnen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
        
Bezug
Modulo r^2 berechnen: Antwort
Status: (Antwort) fertig Status 
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 []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


Bezug
                
Bezug
Modulo r^2 berechnen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]