Ordnung Polynomring < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:21 Fr 15.02.2013 | | Autor: | Ra7or |
| Aufgabe | Das Polynom p(x) := [mm] x^4 [/mm] + [mm] x^3 [/mm] + 1 ist irreduzibel über GF(2) (sogar primitiv).
Wir rechnen im Korper K := GF(2)[x]/p(x).
(a) Berechnen Sie das multiplikative Inverse des Elements x + 1 von K.
(b) Welche Ordnung hat das Element x + 1 in der multiplikativen Gruppe von K?
(c) Geben Sie fur die (zyklische) Untergruppe U der Ordnung 3, die in der multiplikativen Gruppe von K enthalten ist, samtliche Elemente von U an.
(d) Gesucht sind alle a ∈ K, die die Gleichung [mm] a^2 [/mm] + (x + 1) a = 0 erfullen. |
Hallo,
ich habe für die Teilaufgabe a) mittels des erweiterten euklidischen Algorithmus recht einfach das multiplikative Inverse für $(x + 1) $ bestimmen können:
$ggT(p(x), x+1) = 1$
[mm] $x^4 [/mm] + [mm] x^3 [/mm] + 1 = [mm] x^3 [/mm] ( x+1) + 1$
$x+1 = (x + 1) 1 + 0$
daraus folgt:
[mm] $(x+1)^{-1} [/mm] = [mm] x^3$
[/mm]
Teilaufgabe b) macht mir allerdings etwas Kopfschmerzen. Die Ordnung eines Elementes g der Gruppe ist die kleinste Zahl n für die gilt [mm] $g^n [/mm] = e$, wobei e das neutrale Element der Gruppe ist. Das neutrale Element ist in diesem Fall $1$. Also suche ich [mm] $(x+1)^n \equiv [/mm] 1$ mod $p(x)$ Allerdings weiß ich nicht, wie ich n effektive bestimmen kann.
Teilaufgabe c) würde bedeuten, dass ich alle Elemente der Gruppe aufstellen muss und dann die Elemente mit der Ordnung 3 auswählen. Die Elemente der Gruppe sind die Polynomreste?
Teilaufgabe d) würde ich durch einfaches Umstellen lösen, $x [mm] \equiv [/mm] 15a + 1$ mod $p(x)$ und dann für jedes a aus dem Ring testen. Das ist allerdings auch etwas aufwendig, gibt es einen einfacheren Weg?
Vielen Dank im Vorraus!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:19 Fr 15.02.2013 | | Autor: | felixf |
Moin!
> Das Polynom p(x) := [mm]x^4[/mm] + [mm]x^3[/mm] + 1 ist irreduzibel über
> GF(2) (sogar primitiv).
> Wir rechnen im Korper K := GF(2)[x]/p(x).
> (a) Berechnen Sie das multiplikative Inverse des Elements
> x + 1 von K.
> (b) Welche Ordnung hat das Element x + 1 in der
> multiplikativen Gruppe von K?
> (c) Geben Sie fur die (zyklische) Untergruppe U der
> Ordnung 3, die in der multiplikativen Gruppe von K
> enthalten ist, samtliche Elemente von U an.
> (d) Gesucht sind alle a ∈ K, die die Gleichung [mm]a^2[/mm] + (x
> + 1) a = 0 erfullen.
>
> ich habe für die Teilaufgabe a) mittels des erweiterten
> euklidischen Algorithmus recht einfach das multiplikative
> Inverse für [mm](x + 1)[/mm] bestimmen können:
> [mm]ggT(p(x), x+1) = 1[/mm]
> [mm]x^4 + x^3 + 1 = x^3 ( x+1) + 1[/mm]
> [mm]x+1 = (x + 1) 1 + 0[/mm]
>
> daraus folgt:
> [mm](x+1)^{-1} = x^3[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Teilaufgabe b) macht mir allerdings etwas Kopfschmerzen.
> Die Ordnung eines Elementes g der Gruppe ist die kleinste
> Zahl n für die gilt [mm]g^n = e[/mm], wobei e das neutrale Element
> der Gruppe ist. Das neutrale Element ist in diesem Fall [mm]1[/mm].
> Also suche ich [mm](x+1)^n \equiv 1[/mm] mod [mm]p(x)[/mm] Allerdings weiß
> ich nicht, wie ich n effektive bestimmen kann.
Nunja. Ersteinmal: weisst du, welche potentielle Ordnungen in Frage kommen? Wenn du das weisst, kannst du deine Arbeit wesentlich vereinfachen.
Ansonsten: berechne $(x + [mm] 1)^n$ [/mm] modulo $p(x)$ fuer $n = 1, 2, 3, [mm] \dots$. [/mm] Irgendwann kommt da 1 raus und du hast dein $n$ gefunden.
> Teilaufgabe c) würde bedeuten, dass ich alle Elemente der
> Gruppe aufstellen muss und dann die Elemente mit der
> Ordnung 3 auswählen.
Es geht viel einfacher. Du brauchst einfach nur irgendein Element der Ordnung 3; die Potenzen davon sind gerade die gesuchten Elemente. Aber mach erstmal (b).
> Die Elemente der Gruppe sind die Polynomreste?
Ja, und zwar alle ungleich 0.
> Teilaufgabe d) würde ich durch einfaches Umstellen lösen,
> [mm]x \equiv 15a + 1[/mm] mod [mm]p(x)[/mm]
Was macht die 15 da?!? Und richtig umgestellt hast du das auch nicht.
> und dann für jedes a aus dem
> Ring testen. Das ist allerdings auch etwas aufwendig, gibt
> es einen einfacheren Weg?
Natuerlich. Umloesen und Gleichung aufloesen. Wie du das ueber [mm] $\IR$ [/mm] machen wuerdest. Nur dass du jetzt in dem endlichen Koerper $K$ bist. Ist in zwei Zeilen erledigt, ohne wirklich zu rechnen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:04 Sa 16.02.2013 | | Autor: | Ra7or |
Hallo!
Erst einmal vielen Dank für deine Antwort!
Zu Teilaufgabe b)
Ich habe mich noch einmal zum Thema belesen und laut Satz von Lagrange muss die Ordnung des Elements des Elementes ein Teiler der Ordnung des Körpers sein, da es sich hierbei um einen endlichen Körper handelt.
Die Gruppe hat die Ordnung 16, da $GF(2)$ und $grad(p(x))=4$ also [mm] $2^4=16$. [/mm] Also ist die Ordnung des Elements $a [mm] \varepsilon \{1,2,4,8,16\}$. [/mm]
Ich habe das Ganze für [mm] $(x+1)^n$ [/mm] mit $n [mm] \varepsilon \{1,2,4,8,16\}$ [/mm] durchgespielt und komme zu folgenden Ergebnissen:
$(x + [mm] 1)^1 [/mm] $ mod $ p(x) = x + 1 $
$(x + [mm] 1)^2 [/mm] $ mod $ p(x) = [mm] x^2 [/mm] + 1$
Nebenrechung: $ [mm] x^4 [/mm] $ mod $ p(x) = [mm] x^3 [/mm] + 1$
$(x + [mm] 1)^4 [/mm] $ mod $ p(x) = (x + [mm] 1)^2 [/mm] (x + [mm] 1)^2 [/mm] = [mm] x^4 [/mm] + [mm] x^2 [/mm] + [mm] x^2 [/mm] + 1 = [mm] x^3 [/mm] + 1 + 1 = [mm] x^3$
[/mm]
$(x + [mm] 1)^8 [/mm] $ mod $ p(x) = x ^3 x ^3 = [mm] x^4 x^2 [/mm] = [mm] (x^3 [/mm] + 1) [mm] x^1 [/mm] = x ^4 x + [mm] x^2 [/mm] = [mm] x^4 [/mm] + [mm] x^2 [/mm] + x +1$
$(x + [mm] 1)^{16} [/mm] $ mod $ p(x) = [mm] (x^4 [/mm] + [mm] x^2 [/mm] + x +1) [mm] (x^4 [/mm] + [mm] x^2 [/mm] + x +1) = [mm] x^6 [/mm] + [mm] x^4 [/mm] + [mm] x^2 [/mm] + 1 = [mm] x^3 [/mm] + [mm] x^2 [/mm] + x + 1 + [mm] x^3 [/mm] + 1 + [mm] x^2 [/mm] +1 = x + 1$
Was bedeuten würde die Ordnung des Elements ist unendlich, allerdings wiederspricht das doch dem Satz von Lagrange, dessen Aussagen lautet das man auf jeden Fall in einem endlichen Körper die Ordnung eines Elements eindeutig bestimmen kann.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:33 Sa 16.02.2013 | | Autor: | felixf |
Moin!
> Zu Teilaufgabe b)
> Ich habe mich noch einmal zum Thema belesen und laut Satz
> von Lagrange muss die Ordnung des Elements des Elementes
> ein Teiler der Ordnung des Körpers sein, da es sich
> hierbei um einen endlichen Körper handelt.
Nicht ganz. Du bist hier bei der additiven Gruppe.
Die multiplikative Gruppe hat weniger Elemente als der Koerper.
> Die Gruppe hat die Ordnung 16, da [mm]GF(2)[/mm] und [mm]grad(p(x))=4[/mm]
> also [mm]2^4=16[/mm]. Also ist die Ordnung des Elements [mm]a \varepsilon \{1,2,4,8,16\}[/mm].
Das gilt nur in der additiven Gruppe. Die multiplikative Gruppe hat Ordnung 15.
> Ich habe das Ganze für [mm](x+1)^n[/mm] mit [mm]n \varepsilon \{1,2,4,8,16\}[/mm]
> durchgespielt und komme zu folgenden Ergebnissen:
> [mm](x + 1)^1[/mm] mod [mm]p(x) = x + 1[/mm]
> [mm](x + 1)^2[/mm] mod [mm]p(x) = x^2 + 1[/mm]
>
> Nebenrechung: [mm]x^4[/mm] mod [mm]p(x) = x^3 + 1[/mm]
> [mm](x + 1)^4[/mm] mod [mm]p(x) = (x + 1)^2 (x + 1)^2 = x^4 + x^2 + x^2 + 1 = x^3 + 1 + 1 = x^3[/mm]
>
> [mm](x + 1)^8 [/mm] mod [mm]p(x) = x ^3 x ^3 = x^4 x^2 = (x^3 + 1) x^1 = x ^4 x + x^2 = x^4 + x^2 + x +1[/mm]
>
> [mm](x + 1)^{16} [/mm] mod [mm]p(x) = (x^4 + x^2 + x +1) (x^4 + x^2 + x +1) = x^6 + x^4 + x^2 + 1 = x^3 + x^2 + x + 1 + x^3 + 1 + x^2 +1 = x + 1[/mm]
>
> Was bedeuten würde die Ordnung des Elements ist unendlich,
Nein. Da $(x + [mm] 1)^{15} [/mm] = 1$ ist (modulo $p(x)$, nach Lagrange/Fermat), ist $(x + [mm] 1)^{16} [/mm] = x + 1$. Insofern ist das Ergebnis nicht ueberraschend.
LG Felix
|
|
|
|
