matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGruppe, Ring, KörperKongruenz
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Gruppe, Ring, Körper" - Kongruenz
Kongruenz < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Gruppe, Ring, Körper"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Kongruenz: Beweis
Status: (Frage) beantwortet Status 
Datum: 16:12 Mo 02.02.2015
Autor: Ellie123

Aufgabe
Seien s,p [mm] \in \IN= \left\{ 1,2,... \right\} [/mm] und f,m [mm] \im \IZ \left[ X \right], [/mm] dann gilt pf+m [mm] \equiv [/mm] m (mod sp)

Hallo zusammen,

ich möchte gerne die folgende Aussage beweisen, da ich denke, dass dies gehen müsste. Allerdings weiß ich nicht so richtig wie dies gehen könnte. Ich hatte schon an vollständige Induktion über s gedacht. Bin damit aber auch nicht wirklich weitergekommen.
Kann mir jemand helfen?

Viele Grüße, Ellie



        
Bezug
Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 17:16 Mo 02.02.2015
Autor: felixf

Moin!

> Seien s,p [mm]\in \IN= \left\{ 1,2,... \right\}[/mm] und f,m [mm]\im \IZ \left[ X \right],[/mm]
> dann gilt pf+m [mm]\equiv[/mm] m (mod sp)

Setze $f = 1$, $m = 0$. Dann steht da $p [mm] \equiv [/mm] 0 [mm] \pmod{s p}$. [/mm] Das ist genau dann wahr, wenn $s = 1$ ist.

Wenn allerdings $s = 1$ ist, dann ist die Aussage immer wahr.

LG Felix


Bezug
                
Bezug
Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:23 Di 03.02.2015
Autor: Ellie123

Hallo,
leider ist mir nicht klar, was du mir damit

> Setze [mm]f = 1[/mm], [mm]m = 0[/mm]. Dann steht da [mm]p \equiv 0 \pmod{s p}[/mm].
> Das ist genau dann wahr, wenn [mm]s = 1[/mm] ist.
>  
> Wenn allerdings [mm]s = 1[/mm] ist, dann ist die Aussage immer
> wahr.
>  
> LG Felix
>  

sagen willst. Warum betrachtest du diesen Sonderfall f=1 und m=0?

Mittlerweile frage ich mich auch, ob man meine ursprüngliche Aussage überhaupt beweisen kann? Und wenn ja wie? Ist die Idee mit der vollständigen Induktion total falsch?
Kann mir jemand weiterhelfen?
Grüße, Ellie


Bezug
                        
Bezug
Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 08:29 Di 03.02.2015
Autor: hippias

Das fragst Du Dich zu recht, denn die Aussage ist unter den gemachten Vorassetzungen falsch: betrachte etwa $s=1$, $p=3$, $f= 5$ und $m=0$ als Gegenbeispiel.

Vielleicht koenntest Du den Kontext posten, dann laesst sich vielleicht erraten, was tatsaechlich gemeint ist.

Bezug
                                
Bezug
Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 08:57 Di 03.02.2015
Autor: Ellie123

Hallo,
wenn ich aber die von dir gegeben Zahlen
>[mm]s=1[/mm], [mm]p=3[/mm],

> [mm]f= 5[/mm] und [mm]m=0[/mm] als Gegenbeispiel.

einsetze, komme ich doch auf 15 [mm] \equiv [/mm] 0 (mod3). Und das ist doch eine wahre Aussage.

> Vielleicht koenntest Du den Kontext posten, dann laesst
> sich vielleicht erraten, was tatsaechlich gemeint ist.

Genau genommen geht es bei meiner Frage um das NTRU Kryptosystem. Dabei ist die verschlüsselte Nachricht gegeben durch [mm] p\phi [/mm] * h +m. p ist wieder eine natürliche Zahl, [mm] \phi, [/mm] h und m sind Polynome aus [mm] \IZ \left[ X \right]. [/mm] Das Polynom m stellt die Klartextnachricht dar. Mit * ist die Bildung des Konvolutionsproduktes gemeint ist, wie sie in

ftp://ftp.informatik.uni-stuttgart.de/pub/library/medoc.ustuttgart_fi/DIP-3286/DIP-3286.pdf

beschrieben ist. Die Koeffizienten von der verschlüsselten Nachricht [mm] p\phi [/mm] * h +m werden dann aber noch als Elemente aus [mm] \IZ [/mm] /q [mm] \IZ [/mm] aufgefasst.

Es wird dann beim NTRU Verfahren gesagt, dass falls p |q gilt (also q=sp), es leicht möglich ist, eine verschlüsselte Nachricht zu dechiffrieren, also m herauszubekommen.
Das wollte ich eigentlich ursprünglich zeigen und habe das ganze versucht vereinfacht darzustellen.
Ellie

Bezug
                                        
Bezug
Kongruenz: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:03 Di 03.02.2015
Autor: hippias


> Hallo,
>  wenn ich aber die von dir gegeben Zahlen
>  >[mm]s=1[/mm], [mm]p=3[/mm],
> > [mm]f= 5[/mm] und [mm]m=0[/mm] als Gegenbeispiel.
>  
> einsetze, komme ich doch auf 15 [mm]\equiv[/mm] 0 (mod3). Und das
> ist doch eine wahre Aussage.

Richtig, ich habe mich geirrt. Aber trotzdem findest Du jetzt sicher selbst leicht ein Gegenbeispiel.

Bezug
                                                
Bezug
Kongruenz: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:13 Di 03.02.2015
Autor: Ellie123

Ja, ich könnte z.B. p=4, f=1 , m=7 und s=2 setzen. Dann bekomme ich 11 [mm] \equiv [/mm] 7 (mod8) raus, was ja eine unwahre Aussage ist.

Kann mir jemand denn etwas zu meiner eigentlichen Frage bezüglich des NTRU Verfahrens, etwas sagen? Ich komme da nämlich alleine leider nicht weiter?!

Bezug
                                        
Bezug
Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 10:03 Di 03.02.2015
Autor: Teufel

Hi!

Ok, also wir bekommen die verschlüsselte Nachricht [mm] $e=p\phi h+m\in\IZ_q[X]/(X^N-1)\cong \IZ[X]/(q,X^N-1)$, [/mm] d.h. wir betrachten [mm] $p\phi [/mm] h+m$ nicht nur modulo $q$, sondern auch modulo dem Polynom [mm] $X^N-1$. [/mm]

Wenn nun p|q gilt, dann haben wir für alle ganzen Zahlen a,b: [mm] a\equiv b\mod{q} \Rightarrow a\equiv b\mod{p} [/mm] (warum?).
Im Chiffretext [mm] $e=p\phi [/mm] h+m [mm] \mod{(q,X^N-1)}$ [/mm] sind nun die Koeffizienten von [mm] $p\phi [/mm] h$ durch $p$ teilbar. Wenn man also einfach die Koeffizienten von $e$ modulo $p$ ausrechnet, fliegt [mm] $p\phi [/mm] h$ weg und [mm] m\mod{(p,X^N-1)} [/mm] bleibt über.

Wieso können wir daraus nun wieder leicht [mm] m\mod{(q,X^N-1)} [/mm] bestimmen bzw. die richtige Nachricht $m$ bestimmen?


Bezug
                                                
Bezug
Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:17 Mi 04.02.2015
Autor: Ellie123

Hallo,
vielen Dank für die Antworten. Leider steige ich aber immer noch nicht ganz durch.

> Hi!
>  
> Ok, also wir bekommen die verschlüsselte Nachricht [mm]e=p\phi h+m\in\IZ_q[X]/(X^N-1)\cong \IZ[X]/(q,X^N-1)[/mm],
> d.h. wir betrachten [mm]p\phi h+m[/mm] nicht nur modulo [mm]q[/mm], sondern
> auch modulo dem Polynom [mm]X^N-1[/mm].
>  
> Wenn nun p|q gilt, dann haben wir für alle ganzen Zahlen
> a,b: [mm]a\equiv b\mod{q} \Rightarrow a\equiv b\mod{p}[/mm]
> (warum?).

Es gilt dann a=kq+r und b=mq+r für k,m,r [mm] \in \IN. [/mm]  Und da p|q gibt es ein s [mm] \in \IN, [/mm] so dass ps=q. Wir können deshalb a und b auch schreiben als a=kps+r und b=mps+r. Damit ist der Rest, der bei Division von a und b durch p übrig bleibt,  derselbe, nämlich: r mod p

>  Im Chiffretext [mm]e=p\phi h+m \mod{(q,X^N-1)}[/mm] sind nun die
> Koeffizienten von [mm]p\phi h[/mm] durch [mm]p[/mm] teilbar. Wenn man also
> einfach die Koeffizienten von [mm]e[/mm] modulo [mm]p[/mm] ausrechnet, fliegt
> [mm]p\phi h[/mm] weg und [mm]m\mod{(p,X^N-1)}[/mm] bleibt über.
>  
> Wieso können wir daraus nun wieder leicht [mm]m\mod{(q,X^N-1)}[/mm]
> bestimmen bzw. die richtige Nachricht [mm]m[/mm] bestimmen?

Hier komme ich nicht so richtig weiter. Es kann auch sein, dass ich etwas grundlegend nicht verstanden habe. Wenn ich die Koeffizienten von [mm] e=p\phi [/mm] h+m modulo p ausrechne, fällt [mm] p\phi [/mm] h weg. Das kann ich wohl nachvollziehen. Aber die Koeffizienten von m (also der Klartextnachricht), verändern sich doch auch, zumindest, wenn sie [mm] \ge [/mm] p sind. D.h. doch dass verschiedenartige Koeffizienten aus der Klartextnachricht zu gleichen Koeffizienten werden können, wenn ich modulo p reduziere. Also, ich weiß nicht, wie ich daraus wieder die Klartextnachricht gewinnen kann?

Ich hoffe ich habe mich verständlich ausgedrückt und es kann mir nochmal wer weiterhelfen.
Viele Grüße, Ellie


Bezug
                                                        
Bezug
Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 14:12 Mi 04.02.2015
Autor: Teufel

Hi!

Genau, so kann man das machen. Der Knackpunkt ist jetzt, dass $m$ nur 0 und 1 als Koeffizienten hat, also z.B. für $N=5$ eben [mm] $m=X^4+X^3+1$, [/mm] was der Nachricht 11001 entsprechen könnte.

Und diese Koeffizienten bleiben gleich, wenn man modulo einer kleineren Zahl rechnet. Wenn $m$ beliebige Koeffizienten hätte, wäre das nicht so einfach Möglich, wie du schon richtig erkannt hast. Aber für Zahlen $<p$ ist das ok.

Bezug
                                                
Bezug
Kongruenz: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 09:42 Do 05.02.2015
Autor: Ellie123

Hallo nochmal,
Ich habe nochmal eine Frage, zu dem was du geschrieben hast.

> Hi!
>  
> Ok, also wir bekommen die verschlüsselte Nachricht [mm]e=p\phi h+m\in\IZ_q[X]/(X^N-1)\cong \IZ[X]/(q,X^N-1)[/mm],
> d.h. wir betrachten [mm]p\phi h+m[/mm] nicht nur modulo [mm]q[/mm], sondern
> auch modulo dem Polynom [mm]X^N-1[/mm].
>  
> Wenn nun p|q gilt, dann haben wir für alle ganzen Zahlen
> a,b: [mm]a\equiv b\mod{q} \Rightarrow a\equiv b\mod{p}[/mm]
> (warum?).
>  Im Chiffretext [mm]e=p\phi h+m \mod{(q,X^N-1)}[/mm] sind nun die
> Koeffizienten von [mm]p\phi h[/mm] durch [mm]p[/mm] teilbar. Wenn man also
> einfach die Koeffizienten von [mm]e[/mm] modulo [mm]p[/mm] ausrechnet, fliegt
> [mm]p\phi h[/mm] weg und [mm]m\mod{(p,X^N-1)}[/mm] bleibt über.
>  
> Wieso können wir daraus nun wieder leicht [mm]m\mod{(q,X^N-1)}[/mm]
> bestimmen bzw. die richtige Nachricht [mm]m[/mm] bestimmen?
>  

Was meinst du damit, dass man aus [mm] m\mod{(p,X^N-1)} [/mm] wieder [mm] m\mod{(q,X^N-1)} [/mm] bzw. die Klartextnachricht bestimmen kann? Ich würde jetzt denken, dass wenn p|q und man die verschlüsselte Nachricht [mm] e=p\phi [/mm] h+m [mm] \mod{(q,X^N-1)} [/mm] modulo p reduziert, man dann bereits die ursprüngliche Nachricht wiederbekommt.
Also, was genau meinst du mit aus [mm] m\mod{(p,X^N-1)} [/mm] wieder [mm] m\mod{(q,X^N-1)} [/mm] bestimmen?
Ich kann mir auch nach wie vor nicht vorstellen, wie ein Beweis der Aussage konkret aussehen kann? Kann mir jemand weiterhelfen? Ich wäre sehr, sehr dankbar.

Viele Grüße,
Ellie

Bezug
                                                        
Bezug
Kongruenz: Antwort
Status: (Antwort) fertig Status 
Datum: 10:33 Do 05.02.2015
Autor: Teufel

Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)

Na, wenn du deinen Chiffretext modulo p bestimmst, dann fällt ja das $p\phi h$ weg und du bekommst $m \mod{(p,X^N-1)$. Aber davor hast du ja immer \mod{q} und nicht \mod{p} gerechnet. Aber ja, du bekommst in dem Fall das m trotzdem wieder, eben weil die Koeffizienten von $m$ nur 0 und 1 sind.

Ein beispiel wo das nicht klappen würde, wäre z.B. für q=12, p=6, \phi=h=1, m=7\mod{q}.

Dann hast du c=p*\phi*h+m=13=1\mod{q} und das Rechnen \mod{p} würde m=1\mod{p} liefern, was auch stimmt, aber keiner könnte genau sagen, dass eigentlich m=7\mod{q} gilt. Aber wenn die Koeffizienten von $m$ eh alle kleiner als $p$ sind, ist das egal.


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


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]