Darstellung Körper

Neue Frage »

Joachim1 Auf diesen Beitrag antworten »
Darstellung Körper
Guten Morgen liebes Forum,

ich möchte einen (endlichen) Körper für Computerrechnungen handhaben. Dazu würde ich die Konstruktion ( prim)



mit einem



von Grad , irreduzibel und normiert verwenden.

Aus der Klassifikation endlicher Körper weiß man, dass es zu jeder Primzahlpotenz einen Körper mit dieser Anzahl an Elementen gibt. Der Beweis konstruiert aber diesen Körper mit einer Menge aller Fixpunkte der -fachen Ausführung des Frobeniusautomorphismus. Das ist hierfür leider wenig nützlich (oder?).

Allenfalls muss es ein solches Polynom geben. Meine Frage ist nun, wie man dieses oder ein solches Polynom finden kann.



Kurze Zwischenfrage: Was ist der Zusammenhang zwischen einem algebraischen Element eines endlichen Körpers und dem endlichen Körper? Sind alle Elemente eines endlichen Körpers algebraisch, dh gibt es zu allen ein Minimalpolynom vom Grad höchstens ?



Mir ist (fast, dazu brauche ich noch die Antwort obiger Frage) klar, dass dieses Polynom die Eigenschaft hat, dass



mit einer Menge und . Leider brauche ich, um ein aufzustellen Rechenregeln über . Also drehe ich mich im Kreis ... :-) Außerdem weiß ich dann noch nicht, ob genau dieses für obige Konstruktion dienen kann, also ob es irreduzibel ist.

Vielen Dank für eure Ideen.
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

Zitat:

da ist was entscheidendes verloren gegangen.

Zitat:
Der Beweis konstruiert aber diesen Körper mit einer Menge aller Fixpunkte der -fachen Ausführung des Frobeniusautomorphismus.

Keine Ahnung von welchem beweis du sprichst. Für den Frob.homomorphismus braucht man auch einen Oberkörper für die Fixpunkte, also sehe ich nicht wirklich wie das gehen soll.

Der betrachtete Ring ist ein Körper mit Elementen da er als vektorraum Dimension deg(f)=n über GF(p) hat und da f irred. und GF(p)[X] ein Hauptidealring ist damit sogar (f) ein max. Ideal ist.

Zitat:
Was ist der Zusammenhang zwischen einem algebraischen Element eines endlichen Körpers und dem endlichen Körper?

Was soll denn ein "algebraisches Element eines endlichen Körpers" überhaupt sein?
Ich kenne den Begriff 2algebraisch" nur im kontext von Körpererweiterungen.

Zitat:
ein Minimalpolynom vom Grad höchstens ?

Min.pol worüber?


Zitat:
Mir ist (fast, dazu brauche ich noch die Antwort obiger Frage) klar, dass dieses Polynom die Eigenschaft hat, dassmit einer Menge und .

Mit anderen Worten: Keine Nullstellen in Gf(p), keine doppelten Nullstellen (separabel) und vom Grad n. Das ist hinreichend, aber wie du richtig festgestellt hast nicht notwendig.


Allerdings ist das Finden irreduzibler Polynome über endlichen Körpern ein Problem aus der Kategorie "nicht wirklich trivial". D.h. es kommt masiv auf die konkrete Frage wie man genau vorgeht, für den Anfang ist brute-forcing gar nicht so schlecht , reicht einfach und hilfreich ist nicht die folgende Formel:
Joachim1 Auf diesen Beitrag antworten »

Hi und danke für die schnelle Antwort,

Zitat:
Zitat:da ist was entscheidendes verloren gegangen.


Ich stehe gerade auf dem Schlauch, was soll fehlen? Ich dachte, die folgenden Bedingungen reichen für den Körper:

Zitat:
mit einemvon Grad , irreduzibel und normiert


Zitat:
Keine Ahnung von welchem beweis du sprichst. Für den Frob.homomorphismus braucht man auch einen Oberkörper für die Fixpunkte, also sehe ich nicht wirklich wie das gehen soll.


Ich habe den Beweis auf dem matheplanet gelesen. Eine URL kann ich nicht posten, da sich das System weigert. Einfach nach endlicher Körper matheplanet googlen. Man nimmt da einen Oberkörper, über dem in Linearfaktoren zerfällt.

Zitat:
Was ist der Zusammenhang zwischen einem algebraischen Element eines endlichen Körpers und dem endlichen Körper?


Das ist mir mittlerweile klar. Da die Körpererweiterung endlich ist, ist sie auch algebraisch. Das heißt, dass alle Elemente der Erweiterung auch algebraisch sind. Und das heißt wiederum, dass es zu allen Elementen in der Körpererweiterung ein Minimalpolynom mit Grad <= Grad der Körpererweiterung gibt.

Zitat:
Min.pol worüber?


Ich meinte über .

Zitat:
Allerdings ist das Finden irreduzibler Polynome über endlichen Körpern ein Problem aus der Kategorie "nicht wirklich trivial".


Genau das ist mein Problem. Was kann man da machen?
Captain Kirk Auf diesen Beitrag antworten »


ist nicht definiert, da (f) kein Ideal von ist.

Zitat:
Man nimmt da einen Oberkörper

Und genau das ist das Problem. Wo nimmst man den denn her?

Zitat:
Genau das ist mein Problem. Was kann man da machen?

Wie ich bereits schrieb:

Was ist denn die konkrete Fragestellung?

Hast du ein p und ein n und willst solche einen Körper konstruieren?
So ist die Frage sehr vage formuliert und dementsprechend ist die Antwort vage.
Und ein bisschen was hab ich dazu ja schon geschrieben. kannst du damit nichts anfangen?
tmo Auf diesen Beitrag antworten »

Zitat:
Original von Joachim1
Man nimmt da einen Oberkörper, über dem in Linearfaktoren zerfällt.


@Captain Kirk: Da ist er doch, der Oberkörper. Es wurde offensichtlich bereits gezeigt, dass es zu jedem Polynom einen Zerfällungskörper gibt und danach wird dann a posteriori gezeigt, dass der Zerfällungskörper Elemente hat. Das ist die übliche Vorgehensweise, deshalb bin ich ob deiner Verwirrung etwas verwundert.

Was die Ursprungsfrage angeht: Eine Faktorisierung von mit Berlekamp ist wahrscheinlich das Schnellste.
Captain Kirk Auf diesen Beitrag antworten »

@tmo:
Den Oberkörper muss man ja auch irgendwie konstruieren, oder nicht?
Und dann kann man den gesuchten Körper auch gleich direkt konstruieren, darum geht es mir hier.

Vielleicht bin ich aber auch nur verwirrt, mir ist ja auch immer noch nicht klar was jetzt wirklich die konkrete Frage ist.
 
 
Captain Kirk Auf diesen Beitrag antworten »

@tmo: Und was willst du mit Berlekamp faktorisieren?
Sollen wir nicht ein irred. Polynom suchen?
Jetzt bin ich wirklich verwirrt.
tmo Auf diesen Beitrag antworten »

Wenn wir über faktorisieren, ist das Ergebnis unter anderem doch auch ein irreduzibles Polynom vom Grad n.
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Original von tmo
Wenn wir über faktorisieren, ist das Ergebnis unter anderem doch auch ein irreduzibles Polynom vom Grad n.


Was je nach n ein Aufwand für das gesuchte Ergebnis wäre, mal abgesehen davon, dass man sich erstmal durch den Berlekamp-Alg. durchwühlen darf.


Und muss man seit neustem hier javascript aktiviert haben damit man die Einträge richtig sieht?
tmo Auf diesen Beitrag antworten »

Es geht doch um Computerberechnungen. Optimalerweise ist Berlekamp schon implementiert.
Captain Kirk Auf diesen Beitrag antworten »

Aus dem Eingangspost:
Zitat:
ch möchte einen (endlichen) Körper für Computerrechnungen handhaben.

Das klingt für mich mehr nach: selber implementieren, nicht bereits implementiertes benutzen.

Wir scheinen die Frage also sehr unterschiedlich zu lesen.
tmo Auf diesen Beitrag antworten »

Ich weiß ja nicht, welches CAS benutzt wird, aber ich glaube mich zu erinnern, dass MuPad Berlekamp und die endlichen Körper mit p Elementen implementiert hat, aber eben keine endlichen Körper mit p^n Elementen...Kann mich aber auch irren. MuPad ist eh grässlich Big Laugh

Naja es wurde letztendlich nach einer Möglichkeit gefragt, an ein irreduzibles Polynom vom Grad n zu kommen. Und da ist Berlekamp auf jeden Fall schneller als Bruteforcen. Für die Implementierung interessiere ich mich hier nicht. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »