PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Frage zur Klausur FS07 (Prüfung 3.9.08) Aufg. 1 f)



ormium
04.08.2008, 07:52
Sali

In Aufg. 1f) wird gefragt:

Das Polynom x2+1 \in GF(2)[x] ist nicht irreduzibel, aber das Polynom x2+1 \in GF(3)[z] ist irreduzibel. Wahr oder falsch?

Antwort aus der Musterlösung von Beat:

wahr, für deg= 2,3 gilt: Polynom hat mind. 1 Nullstelle -> nicht irreduzibel


Nun meine Frage:
Was bedeutet das "z" in GF(3)[z] und was hat das mit der irreduziblität zu tun? Und ich habe auch keine Nullstelle gefunden. Für welches x ist denn x2+1=0?

Lieber Gruss
Romeo

lutz
04.08.2008, 11:35
Folgendes sind wohl die wichtigen Fragen:
(sollte alles im Skript stehen...)

Was ist denn die Definition von GF(q)[x] ?
Was ist denn überhaupt die Definition von irreduzibel? / Was heisst es?
Bemerkung: für Grad kleiner/gleich 3 gibt es einen Zusammenhang mit Nullstellen (welchen?)

ormium
05.08.2008, 10:21
Sali


Was ist denn die Definition von GF(q)[x] ?
Also GF(q) sind ja die endlichen Körper die wir fürs Verstehen der Kryptographie kennengelernt haben. Da kenne ich die Eigentschaften von GF(2), GF(3), GF(4) und weiss auch dass Z^*_p, wobei p eine Primzahl ist, auch endliche Körper sind.

Was aber das [x] bedeutet habe ich nicht gefunden.



Was ist denn überhaupt die Definition von irreduzibel? / Was heisst es??

Das heisst, dass das Polynom sich so verhält wie eine Primzahl. Also dass es kein anderes Polynom gibt, durch das das irreduzieble Polynom mittels Polynomdivision teilbar ist.


Bemerkung: für Grad kleiner/gleich 3 gibt es einen Zusammenhang mit Nullstellen (welchen?)

Ich glaube es ist so dass die Nullstellen dann in IR bestimmt werden können. Für Grad=4 gibt es glaube ich eine Formel mit der man die NS in den komplexen Zahlen finden kann (Quartische Gleichung). Und bei Grad>4 gibt es keine allgemeine Formel.

Sitmmt das so einigermassen?

Lg.
Romeo

smf68
05.08.2008, 10:27
Sali


Was ist denn die Definition von GF(q)[x] ?
Also GF(q) sind ja die endlichen Körper die wir fürs Verstehen der Kryptographie kennengelernt haben. Da kenne ich die Eigentschaften von GF(2), GF(3), GF(4) und weiss auch dass Z^*_p, wobei p eine Primzahl ist, auch endliche Körper sind.

Was aber das [x] bedeutet habe ich nicht gefunden.
Wie du richtig sagst sind GF(p^d) Körper. GF(p^d)[x] oder auch GF(p^d)[z] bedeutet nun nichts weiter, als dass man Polynome mit der Variablen x oder z über diesem Körper bildet. Die möglichen Koeffizienten sind dann eben Körperelemente.


Und ich habe auch keine Nullstelle gefunden. Für welches x ist denn x2+1=0?
In GF(2) gibt es ja nur zwei Möglichkeiten, nämlich 0 und 1. Einsetzen gibt:
0^2 + 1 = 0 + 1 = 1 keine Nullstelle
1^2 + 1 = 1 + 1 = 2 = 0 (mod 2) Nullstelle!

Fanagon
05.08.2008, 11:19
Und zudem gilt in GF(2): (x+1)^2 = x^2 + 2x + 1 = x^2 + 1 (analog mit (x-1)^2) , was bedeuted, dass du x^2 + 1 faktorisieren kannst, sprich, nicht irreduzibel.

Ueber GF(3) faellt das Zwischenglied aber nicht raus, deshalb dort irreduzibel.

Duh
05.08.2008, 11:41
ausserdem ist Z^*_p kein endlicher körper (bzw gar kein körper, endlich schon :D) weil die menge nur bezüglich multiplikation eine gruppe bildet.
bezüglich addition fehlt das neutrale element, also kann das ganze kein körper sein

ormium
06.08.2008, 07:54
Ok, erstmal vielen Dank!

Habe noch einen kleinen Fehler in der Musterlösung entdeckt. Es heisst in Wirklichkeit GF(3)[x] nicht GF(3)[z], das hat mich verwirrt.

Fanagon, Du schreibst dass (x+1)2 = x2 + 2x + 1 = x2 + 1 . Das 2x fällt in GF(2) weg weil 2*0 mod 2 = 0 und 2*1 mod 2 = 0.
In GF(3) ist aber 2*0 mod 3 = 0, 2*1 mod 3 = 2 und 2*2 mod 3 = 1 und somit in 2 Fällen ungleich 0 und somit ist (x+1)2 \neq x2 + 1 (in GF(3)).
Muss ich dann "raten" dass es in GF(3) kein anderes Polynom gibt, mit dem ich x2 + 1 faktorisieren kann? Oder gibt es da einen anderen Weg?

Duh, ein Gegenbeispiel was Deine Aussage veranschaulicht wäre: Z^*_3.

Ich habe nun mal die Verknüpfungstabelle bezüglich der Addition erstellt:
+ 1 2 3
1 2 0 1
2 0 1 2
3 1 2 0

Hierraus sehe ich dass für 1 und 2 die 3 das neutrale Element sein könnte (1+3 mod 3 = 1, 2 + 3 mod 3 = 2), jedoch für 3 funktioniert es nicht (3+3 mod 3 = 0).
Weiss man so etwas einfach (bzw. findet es durch Ausprobieren raus) oder gibt es eine andere Möglichkeit festzustellen ob ein neutrales Element existiert?

Ich dachte dass wir immer mit Z^*_p rechnen weil das ein Körper ist und wir den in der RSA-Kryptographie einsetzen. Was habe ich das falsch verstanden?

Lg.

Romeo

lutz
06.08.2008, 08:06
Ein Körper braucht immer 2 Gruppen (eine für jede Operation) und gewisse "Kompatibilitätsregeln", die beide Verknüpfen (welche?)
Es gibt eine einfache Charakterisierung aller endlichen Körtper; wie sehen die aus?

ormium
07.08.2008, 07:35
Ein Körper braucht immer 2 Gruppen (eine für jede Operation) und gewisse "Kompatibilitätsregeln", die beide Verknüpfen (welche?)

Soweit ich weis muss die Gruppe der additiven Verknüpfung abelsch sein (Kommutativ) und ein neutrales Element besitzen und die Gruppe der multiplikativen Verknüpfung muss ebenfalls abelsch sein und ein neutrales Element besitzen. Das neutrale Element natürlich immer für die jew. Operation.

Ausserdem muss für alle Gruppenelemente aus K das Distributivgesetz gelten.

Stimmt das?


Es gibt eine einfache Charakterisierung aller endlichen Körtper; wie sehen die aus?

GF(p)=(Z_p, +, *) wobei p eine Primzahl ist.

lutz
07.08.2008, 07:54
mhhh, sind das alle endlichen Körper? (Schau im Skript nach!)
Da sollte es sowas a la "Hauptsatz für endliche Körper" oder "Charakterisierung endlicher Körper" geben oder so.

Hint: Gibt es nur GF(q) für Primzahlen q?

ormium
15.08.2008, 16:23
Also ich habe nun mal ausgiebig nachgelesen (auch im Buch von Angelika Steger, Diskrete Stukturen, sehr gut!)

Es wird auf Seite 227 genau erklärt wie ein endlicher Körper mittels Polynomen aufgebaut wird.

Als Beispiel wird Z_2[x] über dem Polynom x^2+x+1 verwendet. Da der Grad vom Polynom 2 ist enthält Z_2[x]_{x^2+x+1} die Elemente 0,1,x,x+1

Deshalb gibt es auch folgende Verknüpfungstabellen:

+_{x^2+x+1}--------0--------1--------x--------x+1
0---------------------0--------1--------x--------x+1
1---------------------1--------0--------x+1------x
x---------------------x------x+1--------0--------1
x+1-----------------x+1--------x--------1--------0

Was mir klar ist:
0+0 mod x^2+x+1=0
0+1 mod x^2+x+1=1 (da der Grad von x^2+x+1 >1
...
1+1=0 (weil wir uns in Z_2 befinden. und der Grad von x^2+x+1 > 0
1 + (x+1) = x+2 weil 2 ist in Z_2 = 0
x+x=2x=0 weil 2 ist in Z_2 = 0

Somit habe ich die Verknüpfungstabelle von der +_{x^2+x+1} operation verstanden.

Hier noch die Verknüpfungstabelle für die *_{x^2+x+1} operation:

*_{x^2+x+1}--------0--------1--------x--------x+1
0---------------------0--------0--------0--------0
1---------------------0--------1--------x------x+1
x---------------------0------x----------x+1------1
x+1-----------------0------x+1--------1--------x

Die ersten beiden Zeilen und Spalten sind klar, da der Grad des Ergebnisses immer kleiner als der von x^2+x+1 ist und man somit einfach "hinschreiben" kann was rauskommt da die mod-Operation keinen Einfluss hat.

Was noch unklar ist, ist das 2x2-Quadrat unten rechts.

x*x=x^2, x^2 mod x^2+x+1 ist x+1
x*(x+1)=x^2+x, x^2+x mod x^2+x+1 ist 1
(x+1)*(x+1)=x^2+2x+1, 2x \rightarrow 0, \rightarrow x^2+1 (mod x^2+x+1), also x

Habe ich das nun endlich richtig verstanden? ?(

-KraBaT^
15.08.2008, 16:36
1 + (x+1) = x+2 weil 2 ist in Z_2 = 0



Da noch ein kleiner Flüchtigkeitsfehler ;-)

Aber ansonsten sieht deine Rechnung gut aus. Du darfst einfach immer alles 2en Null setzen und / oder das irreduzible Polynom abziehen von deinem Ergebnis. Sond, soweit ich mich erinnere, beides erlaubte Operationen

ormium
15.08.2008, 18:59
1 + (x+1) = x+2 weil 2 ist in Z_2 = 0



Da noch ein kleiner Flüchtigkeitsfehler ;-)


Also 1 + (x+1) = x+2 und weil 2 in Z_2 = 0 ist 1 + (x+1) = x

Jetzt stimmts, oder?

Etan
15.08.2008, 22:37
confirmed. denke, dass es so stimmt.