Normalbasen (Endliche Körper) < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:05 Mi 07.11.2012 | | Autor: | Tim87 |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen,
ich bin mir nicht ganz sicher, ob die gewählte Frageform passend ist -
Ich beschäftige mich mit Normalbasen (im Hauptstudium), nachdem ich den Wikipedia Artikel und ein Paper gelesen habe, bin ich nur unwesentlich schlauer und mir fehlen neben dem exakten Verständnis der Normalbasen auch ein bisschen der Gesamtzusammenhang etc.
Die Fragen:
- Was sind denn Normalbasen (NB) genau? Soweit ich das verstanden habe, ist es (mind.?) ein Elemente ß eines Erweiterungskörpers [mm] GF(p^{m}) [/mm] (jeder Erweiterungskörper hat eine NB) aus welchem alle anderen Elemente des gleichen Erweiterungskörper durch die Anwendung der Potenz p. Wobei die Anzahl der Elemente des Erweiterungskörpers = [mm] p^{m}. [/mm] Dieses Element ß und die m Elemente ergeben scheinbar einen Vektor { ß, ß^{p}, [mm] ß^{p^{2}}, [/mm] ... [mm] ß^{p^{m-1}} [/mm] } (vgl. Wikipedia - die Potenz einer Potzen bekomme ich irgendwie nicht hin oder es geht nicht ;)). Dieser Vektor ist linear unabhängig (oder die einzelnen Elemente sind linear unabhängig?).
- Mir fehlt neben dem exakten Verständnis die Tiefe der Materie - gibt es gute (oder verständlich für den Einstieg) Lehrbücher/Paper die empfehlenswert sind? Wie findet man dieses ß (möglichst gut), wie rechnet man damit, welche Anwendungsgebiete gibt es (innerhalb der Kryptographie/Codierungstheorie/o.ä.), gibt es eine verständlichen Beweis, etc.
Grüße
|
|
| |
|
moin,
Du meinst das hier:
http://en.wikipedia.org/wiki/Normal_basis ?
Um das zu verstehen und damit arbeiten zu können musst du am besten ein paar Semester Algebra gehört haben (nicht lineare Algebra).
Insbesondere musst du ein bisschen was über Gruppen und eine ganze Menge über Körpererweiterungen und speziell Galoiserweiterungen wissen.
Schau dir mal hier zumindest das Inhaltsverzeichnis an
![[]](/images/popup.gif) Wiki
und erzähl mal was du über die dort aufgeführten Themen weißt; in wie weit du sie kennst.
lg
Schadow
PS:
Ich schieb die Frage mal ins Algebraforum, zur Linearen Algebra passt das nicht so ganz.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:40 Fr 09.11.2012 | | Autor: | Tim87 |
Hallo,
ja genau http://en.wikipedia.org/wiki/Normal_basis
also ich habe eine Vorlesung zu Körpern und Primkörpern gehört. Über die Körperweiterung weiß ich noch nicht soo viel, habe mir aber ein Skript dazu durchgelesen - wobei ich mich im Vergleich zu Primkörpern noch nicht so sicher fühle - eher kenne ich den groben Rahmen für die Körpererweiterung.
Der Rest sagt mir nichts :>
lg
Tim
(ok@Verschiebung ;))
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:31 Fr 09.11.2012 | | Autor: | felixf |
Moin!
> ich bin mir nicht ganz sicher, ob die gewählte Frageform
> passend ist -
>
>
> Ich beschäftige mich mit Normalbasen (im Hauptstudium),
> nachdem ich den Wikipedia Artikel und ein Paper gelesen
> habe, bin ich nur unwesentlich schlauer und mir fehlen
> neben dem exakten Verständnis der Normalbasen auch ein
> bisschen der Gesamtzusammenhang etc.
>
> Die Fragen:
>
> - Was sind denn Normalbasen (NB) genau?
Spezielle Basen einer Koerpererweiterung. Sie erlauben, den Frobeniushomomorphismus sehr schnell auszurechnen: er entspricht einfach einem zyklischen Shift.
Dies kann man etwa Ausnutzen, um auf elliptischen Kurven ueber endlichen Koerpern schneller zu multiplizieren. (In dem Fall ist $q$ meist eine Zweierpotenz, also wenn man das ganze wirklich in der Praxis verwenden will.)
> Soweit ich das
> verstanden habe, ist es (mind.?) ein Elemente ß eines
> Erweiterungskörpers [mm]GF(p^{m})[/mm] (jeder Erweiterungskörper
> hat eine NB) aus welchem alle anderen Elemente des gleichen
> Erweiterungskörper durch die Anwendung der Potenz p.
Nein, du bekommst damit nur eine Basis. Du kannst jedes Element aus dem grossen Koerper als Linearkombination dieser Potenzen von [mm] $\beta$ [/mm] schreiben.
> Wobei die Anzahl der Elemente des Erweiterungskörpers = [mm]p^{m}.[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Dieses Element ß und die m Elemente ergeben scheinbar
> einen Vektor [mm] $\{ \beta, \beta^{p}, \beta^{p^{2}}, ... \beta^{p^{m-1}} \}$
[/mm]
Genau. Das ist dann die Basis
> (vgl. Wikipedia - die Potenz einer Potzen bekomme ich
> irgendwie nicht hin oder es geht nicht ;)). Dieser Vektor
> ist linear unabhängig (oder die einzelnen Elemente sind
> linear unabhängig?).
Die Elemente sind alle linear unabhaengig (zueinander).
> wie rechnet man damit,
Das solltest du dir vielleicht erstmal allgemein fuer Basen von Koerpererweiterungen anschauen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:16 Mo 12.11.2012 | | Autor: | Tim87 |
Hallo Felix, danke für deine Antwort.
Ich lese mir jetzt erst einmal die Grundlagen dazu durch.
Was sind Frobeniushomomorphismus?
Wie würde man sonst ohne normalbasen rechnen müssen?
lg tim
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:19 Mi 14.11.2012 | | Autor: | Tim87 |
Ich habe jetzt einige Artikel und Paper gelesen -
und mir stellt sich die Frage auf was genau bezieht sich die NB?
Nach wikipedia auf Galois Erweiterungen, andere schreiben dass es sich generell auf Erweiterungskörper bezieht und andere schreiben nur endliche Körper aber dazu die Form der Körpererweiterung [mm] GF(p^{m}).
[/mm]
Ist damit eigentlich immer das gleiche gemeint und die Worte werden als Synonym verwendet?
So wie ich das verstanden habe, hat man einen endlichen Körper (bzw. einen Primkörper). Ein Erweiterungskörper des Grads d mit p (Primzahl) und f(x) (einem unzerlegbaren Polynom mit Grad deg(f)=d )
definiert über die Vektoraddition, Vektormultiplikation -jeweils mod f(x)
und [mm] \IZ_{p}[x]_{f} [/mm] := {g(x) [mm] \in \IZ_{p}[x] [/mm] | deg(g) < d }.
Ist das automatisch ein Galois Erweiterungskörper oder muss ein Erweiterungskörper L/K zusätzlich algebraisch, normal und separabel sein?
grüße
|
|
|
| |
|
> Nach wikipedia auf Galois Erweiterungen, andere schreiben
> dass es sich generell auf Erweiterungskörper bezieht und
> andere schreiben nur endliche Körper aber dazu die Form
> der Körpererweiterung [mm]GF(p^{m}).[/mm]
Es ist nicht verboten, Begriffe zu definieren wie man sie gerne möchte.
Also ist es durchaus möglich, dass verschiedene Autoren mit Normalbasis verschiedene Dinge meinen, auch wenn man als (guter) Autor darauf achten sollte, dass man den anderen nicht widerspricht.
Ohne deine Texte zu lesen kann man das natürlich nicht sicher sagen, aber ich nehme einfach mal an die beziehen sich schon auf den selben Begriff, nur in unterschiedlichem Kontext.
> So wie ich das verstanden habe, hat man einen endlichen
> Körper (bzw. einen Primkörper). Ein Erweiterungskörper
> des Grads d mit p (Primzahl) und f(x) (einem unzerlegbaren
> Polynom mit Grad deg(f)=d )
> definiert über die Vektoraddition, Vektormultiplikation
> -jeweils mod f(x)
> und [mm]\IZ_{p}[x]_{f}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
:= {g(x) [mm]\in \IZ_{p}[x][/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| deg(g) < d
> }.
Und das ist für ein irreduzibles Polynom $f$ und eine Primzahl $p$ tatsächlich ein Körper, ja.
> Ist das automatisch ein Galois Erweiterungskörper oder
> muss ein Erweiterungskörper L/K zusätzlich algebraisch,
> normal und separabel sein?
Ja, ist es. Da für deine Erweiterung $L/K$ hier sowohl $L$ als auch $K$ endliche Körper sind, ist diese Erweiterung sofort algebraisch, normal und separabel - und damit Galois'sch.
Das müsste man natürlich noch zeigen, das ist nicht ganz ohne ein wenig Mühe klar.
lg
Schadow
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 11:53 Do 15.11.2012 | | Autor: | Tim87 |
Hallo,
ich bis jetzt zwar relativ viel gelesen, hänge aber noch an dem Problem, genau zu verstehen, auf was sich die Normalbasen genau beziehen.
Beziehen die NB sich immer nur auf Galois Erweiterungen?
Und was genau ist das? bzw. wo kann ich das "gut" nachlesen - ich bin bezüglich der verschiedenen Erweiterungen etc. begrifflich etwas verwirrt -
lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:20 Sa 17.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:35 Do 15.11.2012 | | Autor: | felixf |
Moin!
> Ich habe jetzt einige Artikel und Paper gelesen -
> und mir stellt sich die Frage auf was genau bezieht sich
> die NB?
>
> Nach wikipedia auf Galois Erweiterungen, andere schreiben
> dass es sich generell auf Erweiterungskörper bezieht und
> andere schreiben nur endliche Körper aber dazu die Form
> der Körpererweiterung [mm]GF(p^{m}).[/mm]
Der Begriff ist allgemein fuer Galois-Erweiterungen definiert. Erweiterungen von endlichen Koerpern sind immer Galois-Erweiterungen mit sehr einfach zu beschreibender Galois-Gruppe, womit du dort insbesondere auch Normalbasen hast und die dort besonders einfach aussehen.
Bei nicht-Galois-Erweiterungen hast du keine Normalbasen, da diese zwingend eine Galoisgruppe voraussetzen und diese nur bei Galois-Erweiterungen Sinn macht.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:08 Do 15.11.2012 | | Autor: | Tim87 |
Hallo Felix,
super - danke :)
also ich habe dann einen endlichen Körper [mm] \IZ(p), [/mm] wobei p eine Primzahl ist und der endl. Körper dadurch ein Primkörper und erweitere ihn zu [mm] GF(p^d) [/mm] (oder [mm] \IZ_{p}[x]_{f}(?)) [/mm] //ist ein Beispiel aus einem Skript, ich nehme an diese beiden Begriffe kann man als synonym verwenden?// mit Hilfe von unzerlegbaren (irreduzibeln) Polynomen z.B. f(x).
Dann ist für diesen Erweiterungskörper die Polynomaddition,Polynommultiplkation (jeweils mod f(x)) und Abgeschlossenheit definiert und
das unzerlegbare Polynom f(x) [mm] \in \IZ_{p}[x]_{f} [/mm] vom Grad d gibt an, dass der Körper [mm] \IZ_{p}[x]_{f} [/mm] genau [mm] p^{d} [/mm] Elemente hat.
Ist das soweit richtig?
Und wenn ja, aus welchen Elementen besteht der Erweiterungskörper? Aus den Elementen des Unterkörpers/Primkörpers sowie dem unzerlegbaren Polynom? oder noch mehr?
Für f(x) [mm] =x^{2}+x+1 \in \IZ_{2}[x]
[/mm]
werden die Elemente als [mm] \IZ_{2}[x]_{f} [/mm] = {0,1,x,x+1} angegeben. Das Beispiel verstehe ich nicht ganz.
Danke,
lg,
tim
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:54 Fr 16.11.2012 | | Autor: | felixf |
Moin tim!
> also ich habe dann einen endlichen Körper [mm]\IZ(p),[/mm] wobei p
> eine Primzahl ist und der endl. Körper dadurch ein
> Primkörper und erweitere ihn zu [mm]GF(p^d)[/mm] (oder
> [mm]\IZ_{p}[x]_{f}(?))[/mm] //ist ein Beispiel aus einem Skript, ich
> nehme an diese beiden Begriffe kann man als synonym
> verwenden?// mit Hilfe von unzerlegbaren (irreduzibeln)
> Polynomen z.B. f(x).
Nun, [mm] $GF(p^d)$ [/mm] wird so konstruiert, ja. Aber im Endeffekt haengt das Resultat nicht direkt vom Polynom ab, weshalb man einfach [mm] $GF(p^d)$ [/mm] schreibt.
> Dann ist für diesen Erweiterungskörper die
> Polynomaddition,Polynommultiplkation (jeweils mod f(x)) und
> Abgeschlossenheit definiert und
>
> das unzerlegbare Polynom f(x) [mm]\in \IZ_{p}[x]_{f}[/mm] vom Grad
> d gibt an, dass der Körper [mm]\IZ_{p}[x]_{f}[/mm] genau [mm]p^{d}[/mm]
> Elemente hat.
Genau.
> Und wenn ja, aus welchen Elementen besteht der
> Erweiterungskörper? Aus den Elementen des
> Unterkörpers/Primkörpers sowie dem unzerlegbaren Polynom?
> oder noch mehr?
Er besteht eigentlich aus Restklassen. Da das etwas schwerer zu erklaeren ist, wenn man keine gute lineare Algebra / Algebra gehoert hat, kann man das auch etwas einfacher machen:
Der endliche Koerper [mm] $GF(p^d) [/mm] = [mm] \IZ_p[x]/(f)$ [/mm] (oder wie auch immer du ihn schreiben willst) besteht aus allen Polynomen in $x$ mit Grad $< [mm] \deg [/mm] f = d$, welche als Koeffizienten Elemente aus [mm] $\IZ_p$ [/mm] haben, also im Endeffekt (das ist wieder eine Vereinfachung) die Zahlen 0 bis $p - 1$.
Bezueglich dieser Zahlen wird modulo $p$ gerechnet, und wenn (bei Multiplikation) Polynome mit hoeherem Grad auftreten, macht man Division mit Rest durch $f$ (bei den Koeffizienten rechnet man wieder modulo $p$) und nimmt den Rest -- dessen Grad ist immer $< [mm] \deg [/mm] f = d$.
> Für f(x) [mm]=x^{2}+x+1 \in \IZ_{2}[x][/mm]
> werden die Elemente
> als [mm]\IZ_{2}[x]_{f}[/mm] = {0,1,x,x+1} angegeben. Das Beispiel
> verstehe ich nicht ganz.
Nun, das sind alle Polynome von Grad $< 2 = [mm] \deg(x^2 [/mm] + x + 1)$, die Koeffizienten in [mm] $\IZ_2 [/mm] = [mm] \{ 0, 1 \}$ [/mm] haben.
Macht es jetzt mehr Sinn?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:38 Mi 21.11.2012 | | Autor: | Tim87 |
Hi Felix,
ja super, danke ;)
habe mir die letzten Tage sehr viel zu Primkörpern, Erweiterungskörpern und deren erzeugung durchglesen.
Soweit ist erst mal alles klar ;)
Jetzt schaue ich mir die Erzeugung von NBs an. Kennst du zufälligerweise eine gute Seite diesbezüglich?
lg,
tim
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 15:13 Do 22.11.2012 | | Autor: | Tim87 |
Hallo Felix,
ich habe weiter gelesen (z.B. "Normal Bases over Finite Fields" von Shuhong Gao [google erster Link]).
ich habe mich ein paar Sachverhalte gefragt - 2 allgemeine Fragen und ein paar spezielle, die aus den Texten für mich nicht ganz ersichtlich waren
1) [mm] ß^{p^{m-1}} [/mm] dieses m-1 bezieht sich auf den Grad des unzerlegbaren Polynoms oder? für z.B. [mm] F_{2} [/mm] mit dem unzerlegbaren Polynom f(x) [mm] =x^{2}+x+1. [/mm] Wäre m=2.
2) In der oben angegebenen Dissertation bezieht sich der Autor immer nur auf Normalbasen bezgl. eines Erweiterungskörpers über einem anderen Erweiterungskörper. (Ich weiß dass man Erweiterungskörper ja auch wieder erweitern kann - aber die Erweiterung kann sich doch auch auf Primkörper beziehen, oder?) (also NB für Erweiterungskörper über Primkörper)
3) Wie stelle ich denn ein Element aus dem Erweiterungskörper dar?
Bei dem oben genannten Bsp [mm] F_{2} [/mm] mit f(x) würde ich ja für die Polynom-Darstellung die Anzahl an Koeffizienten aus dem Grad deg(f(x)) = 2 ableiten und dann alle Kombinationen als Polynome darstellen, sodass ich
0 [mm] x^{0} [/mm] + 0 [mm] x^{1} [/mm]
0 [mm] x^{0} [/mm] + 1 [mm] x^{1} [/mm]
1 [mm] x^{0} [/mm] + 0 [mm] x^{1} [/mm]
1 [mm] x^{0} [/mm] + 1 [mm] x^{1} [/mm]
habe. Wie funktioniert soetwas mit NB?
4)
In der Dissertation wird sehr stark zwischen NB mit einer geringen Komplexität und optimalen Normalbasen (ONB) unterschieden. Ist eine ONB nicht einer NB mit der "besten/geringsten" Komplexität, oder habe ich da etwas falsch verstanden
lg,
tim
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:20 Sa 24.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:53 Sa 24.11.2012 | | Autor: | Tim87 |
Hallo Felix,
(noch einmal, da ich die Zeit nicht richtig eingestellt habe)
ich habe weiter gelesen (z.B. "Normal Bases over Finite Fields" von Shuhong Gao [google erster Link]).
ich habe mich ein paar Sachverhalte gefragt - 2 allgemeine Fragen und ein paar spezielle, die aus den Texten für mich nicht ganz ersichtlich waren
1) [mm] ß^{p^{m-1}} [/mm] dieses m-1 bezieht sich auf den Grad des unzerlegbaren Polynoms oder? für z.B. [mm] F_{2} [/mm] mit dem unzerlegbaren Polynom f(x) [mm] =x^{2}+x+1. [/mm] Wäre m=2.
2) In der oben angegebenen Dissertation bezieht sich der Autor immer nur auf Normalbasen bezgl. eines Erweiterungskörpers über einem anderen Erweiterungskörper. (Ich weiß dass man Erweiterungskörper ja auch wieder erweitern kann - aber die Erweiterung kann sich doch auch auf Primkörper beziehen, oder?) (also NB für Erweiterungskörper über Primkörper)
3) Wie stelle ich denn ein Element aus dem Erweiterungskörper dar?
Bei dem oben genannten Bsp [mm] F_{2} [/mm] mit f(x) würde ich ja für die Polynom-Darstellung die Anzahl an Koeffizienten aus dem Grad deg(f(x)) = 2 ableiten und dann alle Kombinationen als Polynome darstellen, sodass ich
0 [mm] x^{0} [/mm] + 0 [mm] x^{1} [/mm]
0 [mm] x^{0} [/mm] + 1 [mm] x^{1} [/mm]
1 [mm] x^{0} [/mm] + 0 [mm] x^{1} [/mm]
1 [mm] x^{0} [/mm] + 1 [mm] x^{1} [/mm]
habe. Wie funktioniert soetwas mit NB?
4)
In der Dissertation wird sehr stark zwischen NB mit einer geringen Komplexität und optimalen Normalbasen (ONB) unterschieden. Ist eine ONB nicht einer NB mit der "besten/geringsten" Komplexität, oder habe ich da etwas falsch verstanden
lg,
tim
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Di 27.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
