Bestimmung quadratischer Tower Fields

Neue Frage »

Shalec Auf diesen Beitrag antworten »
Bestimmung quadratischer Tower Fields
Hallo allerseits,

ich habe ein paar Probleme den Tower aufzubauen.

Zunächst gilt ja , wobei a kein Quadrat ist. (D.h. das Polynom ist irreduzibel und wir haben hier tatsächlich eine Isomorphie.)

Die nächste Etage bereitet mir aber Probleme. Welches Polynom kann ich hier wählen?
Hier muss das Polynom irreduzibel über sein. Angenommen , wie könnte meine Wahl da aussehen? Oder von was ist das abhängig? Wie kann ich ein solches Polynom finden? Mein Ansatz war bisher , aber das ist ja nicht irreduzibel, da man auch bekommt und hier gilt.

Ich hatte gedacht, dass ich für den Tower Elemente nehmen muss, die keine 16. (oder Teiler von 16) Wurzel sind.

Hat hier jemand für mich Ansätze oder vielleicht sogar eine direkte Idee?
Elvis Auf diesen Beitrag antworten »

Ich würde nicht versuchen, endliche Körper von unten her aufzubauen, sondern von oben her. Dein Anfang ist schon falsch, denn bekommst du nicht über ein rein quadratisches Polynom, und sind reduzibel, enthält nur Quadrate. Zu kommt man z.B. nur durch , weil dieses keine Nullstelle hat.

Allgemein für : suche ein irreduzibles Polynom vom Grad n in
(ich habe mal irgendwo gelesen, dass es dafür Algorithmen gibt, sorry Quelle vergessen, hier ist eine : http://compilers.cs.uni-saarland.de/publ.../leissa_sem.pdf),
dann ist eine Nullstelle im algebraischen Abschluss ein primitives Element von , die Elemente sind wegen des Vektorraumisomorphismus gerade die Linearkombinationen . Die Teilkörper findet man dann als Fixkörper der Untergruppen der Galoisgruppe (zyklisch, erzeugt vom Frobeniusautomorphismus).

Hier macht es jemand exemplarisch vor, wie ich es auch für machen würde: http://www.mia.uni-saarland.de/hoeltgen/FiniteFields.pdf
(Wir haben früher statt t geschrieben. Da wir immer nur auf Tafeln oder Papier mit der Hand geschrieben haben, war das egal. Ich gebe zu dass t heute auf dem Computer besser ist.)
Shalec Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Ich würde nicht versuchen, endliche Körper von unten her aufzubauen, sondern von oben her. Dein Anfang ist schon falsch, denn bekommst du nicht über ein rein quadratisches Polynom, und sind reduzibel, enthält nur Quadrate. Zu kommt man z.B. nur durch , weil dieses keine Nullstelle hat.

Allgemein für : suche ein irreduzibles Polynom vom Grad n in (ich habe mal irgendwo gelesen, dass es dafür Algorithmen gibt, sorry Quelle vergessen), dann ist eine Nullstelle im algebraischen Abschluss ein primitives Element von , die Elemente sind wegen des Vektorraumisomorphismus gerade die Linearkombinationen . Die Teilkörper findet man dann als Fixkörper der Untergruppen der Galoisgruppe (zyklisch, erzeugt vom Frobeniusautomorphismus).

Hier macht es jemand exemplarisch vor, wie ich es auch für machen würde: http://www.mia.uni-saarland.de/hoeltgen/FiniteFields.pdf
(Wir haben früher statt t geschrieben. Da wir immer nur auf Tafeln oder Papier mit der Hand geschrieben haben, war das egal. Ich gebe zu dass t heute auf dem Computer besser ist.)


Vielen Dank für den Link. Ich habe in ein paar weiteren Papern nachgelesen und ein passendes Polynom gefunden, dass in meinem Fall funktioniert: wird genutzt um von zu gehen.

Ich habe die Angewohnheit die 26-52 Buchstaben unseres Alphabets irgendwie zu nutzen. So lange es irgendwann auch getippt werden soll vermeide ich Buchstaben, die ein Rechtschreibfehlerpotential bürgen. smile Gerade Lambda war eines mit hoher Fehlerrate.. Es spart auch Zeit. smile

Wenn ich das Polynom nun reduziere, erhalte ich

Was ich als Bauplan interpretiert hätte. Jedoch habe ich ein Problem damit zu akzeptieren, dass es einen endlichen Körper gibt, der keine Lösung von enthält.


Edit: Hast du zu dem Link eine Seitenreferenz?
Elvis Auf diesen Beitrag antworten »

kannst du in vergessen. ist reduzibel. 2 ist weder in noch in ein Quadrat, da kannst du keine Wurzel aus 2 finden. Nach dem 2. Ergänzungssatz zum quadratischen Reziprozitätsgesetz ist 2 ein Quadrat mod p für p kongruent +/- 1 mod 8, kein Quadrat für p kongruent +/-3 mod 8 ( http://www.mathematik.uni-muenchen.de/~f...prim/prim08.pdf ) Das bedeutet, dass du allgemein nicht schreiben darfst.

Seitenreferenz für den 2. Link ? siehe Ende des Papers
Shalec Auf diesen Beitrag antworten »

Ehm.. irgendwie hatte ich da grad was durcheinander gebracht. Ich dachte eben die Wurzel aus 2 sei 2, das ist aber das Inverse.. Nun gut. Ich erkenne meine Fehler Augenzwinkern
Elvis Auf diesen Beitrag antworten »

Die Wurzel aus 2 ist ein Element x, für das gilt. In Körpern ist gleichbedeutend mit , deshalb kommt hier das quadratische Reziprozitätsgesetz ins Spiel. In endlichen Körpern kann man nicht allgemein Quadratwurzeln ziehen, höhere Wurzel schon gar nicht (gibt es dafür überhaupt schon eine Theorie ?).
Wenn man aber auch nicht Nullstellen von Polynomen im Körper finden kann, so doch immer in einer algebraischen Erweiterung des Körpers. Nach Kronecker adjungiert man einfach eine Nullstelle eines ireduziblen Polynoms : , und wie durch Zauberei entsteht eine Körpererweiterung, die die Nullstelle enthält. (Für mich ist das immer noch und jedesmal wieder, wenn ich diesen Vorgang studiere, eines der größten Wunder der Algebra.)
 
 
Shalec Auf diesen Beitrag antworten »

Wenn ich nun meinen Tower gemäß aufbaue, faktorisiere ich erstmal entsprechend indem ich
Also usw. (ohne deinen Kommentar unberücksichtigt zu lassen, da ich ja streng genommen keine Wurzel nutzen darf..) Also würde ich das Tower Field so aufbauen





Jetzt prüfe ich mal, ob irreduzibel über ist. Im Grunde läuft es darauf hinaus, ob ein Quadrat ist. D.h. ob ich ein Element finde, dessen Quadrat gerade -U ist. (Intuitiv würde ich jetzt nein pauschal sagen. Aber die Intuition ist immer so eine Sache..) Ein Element kann ich so darstellen:

Ausrechnen liefert gemäß der binomischen Formel, und dass wir eine Primzahl betrachten, z.B. p=5. Also

An dieser Stelle würde mir nur einfallen, beide Seiten zu quadrieren, um zu gucken was dann passiert. Insgesamt liefert das
ab hier würde ich abbrechen, da diese Rechnerei nicht zielführend erscheint. Also muss ich andere Eigenschaften heranziehen.


Ich denke, dass das Interessante an dieser Stelle zu finden ist:
Sehe ich irgendwas einfaches einfach nicht? Big Laugh Hammer Das sieht für mich nämlich nicht nach einem Wiederspruch aus..


Das Wunder, das du da ansprichst, fand ich in der kommutativen Algebra schon fastzinierend. Wenn man in einem Hauptidealring ein Ideal aus einem irreduziblen Polynom erzeugt, ist das Resultat ein maximales Ideal, womit dann folgt, dass der Ring adjungiert diesen Ideals (sagt man hier adjungiert? Ich meine R/I, R modulo I) isomorph zu einem Körper ist. Womit man dann auch Aussagen über Varietäten ableiten kann und damit am Ende sogar über Kurven.


Edit: Nach [2] hat genau dann eine Lösung, wenn Meine Primzahl ist kongruent 13 mod 32 und somit kongruent 5 mod 8. p=13 erfüllt beides und dient daher als gutes Beispiel. Also besitzt die Gleichung keine Lösung und wir können sie als Ausgangsposition nutzen.

Edit: scheint eine gute Wahl zu sein. In sage ist jedoch GF8 und entsprechend GF16 als Tower nicht mehr implementiert. Aber zu den endlichen Körpern habe ich noch eine Frage -> neuer Thread.


[1] https://de.wikipedia.org/wiki/Quadratisc...sgesetz#Aussage

[2] https://en.wikipedia.org/wiki/Quadratic_...cond_supplement
Elvis Auf diesen Beitrag antworten »

Ich weiß nicht, ob das ein guter Ansatz ist. Ganz sicher dann nicht, wenn über reduzibel ist, weil man dann gar nicht den bekommt. Das ist der Fall für und für .
Konstruktive Aufbauten von endlichen Körpern sind möglich, aber mir fehlt eine sinnvolle Theorie dazu. Das heißt, ich müsste erst einmal Einzelfälle probieren und daraus eine Theorie gewinnen (die Lebensdauer des Universums kann dafür zu kurz sein oder auch nicht, jedenfalls ist entweder meine Geduld oder meine Fähigkeit nicht ausreichend). Meine unmaßgebliche Intuition sagt mir, dass dann Fallunterscheidungen notwendig werden, je nachdem welche Eigenschaften die Primzahl p hat, welchen Grad die Körpererweiterung hat und davon abhängig welche Eigenschaften bestimmte Elemente in den Zwischenkörpern haben. Ich weiß nicht, ob und in welchen Fällen deine Konstruktion mit fortgesetzten Quadratwurzeln aus 2 Erfolg hat. (Ich erinnere mich nur dunkel an relativ quadratische Körpererweiterungen, aber da ging es glaube ich um die Theorie algebraischer Zahlkörper.)
Hilbert und ich ( Big Laugh ) haben uns immer bemüht, die Galoistheorie für algebraische und zahlentheoretische Strukturen zu nutzen, und gerade die endlichen Körper sind ein Musterbeispiel für den Erfolg der Galoistheorie, deshalb heißen sie auf englisch Galoisfield .
Wenn man ein einziges irreduzibles Polynom vom Grad n über gefunden hat, ergibt sich alles von selbst. Man kann dann die Teilkörper bestimmen und darin primitive Elemente finden, deren Minimalpolynome konstituieren die Zwischenkörper und du hast den gewünschten Turm konstruiert. Das Problem beim Aufbau von unten nach oben sehe ich darin, dass man jeden Zwischenkörper und seine Elemente verstanden haben muss bevor es auch nur einen Schritt weitergeht. Um zu wissen, welche Zwischenkörper auftreten benutzt man ja ohnehin die Galoistheorie, warum also nicht die ganze Lösung mit einem Rutsch.
Shalec Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Meine unmaßgebliche Intuition sagt mir, dass dann Fallunterscheidungen notwendig werden, je nachdem welche Eigenschaften die Primzahl p hat, welchen Grad die Körpererweiterung hat und davon abhängig welche Eigenschaften bestimmte Elemente in den Zwischenkörpern haben. Ich weiß nicht, ob und in welchen Fällen deine Konstruktion mit fortgesetzten Quadratwurzeln aus 2 Erfolg hat. (Ich erinnere mich nur dunkel an relativ quadratische Körpererweiterungen, aber da ging es glaube ich um die Theorie algebraischer Zahlkörper.)

Bei den Fallunterscheidungen bin ich insgesamt bis Modulo 32 vorgedrungen und habe festgestellt, dass in meinem Fall die ungeraden Restklassen zu betrachten sind. Ein Test bzgl. Modulo 64 zeigte eine exakte Kopie der ersten Sequenz. Die Primzahl, die ich betrachte hat die Eigenschaft kongruent 13 modulo 32 und damit kongruent 5 modulo 8 zu sein. Also liegt vor. Ein schneller Test mit einem Computer-Algebra-System (Sage) hatte mir bestätigt, dass dann in jedem Fall p -> p^2 -> p^4 Körper sind. Mit Singular hätte ich vermutlich mehr Erfolg bei den Tests, da das Programm extra für algebraische Zwecke konstruiert wurde. Insgesamt hatte der Autor des Papers, der die 35-Bit große Primzahl vorgeschlagen hat, auch direkt das Polynom genutzt. Wenn ich mich nur mehr an die kommutative Algebra erinnern würde, könnte ich vermutlich über die Betrachtung der (Annahme: ) Körper darauf kommen, dass das evtl. keine Körper sind.

Am Ende geht es aber auch nur um die Darstellung des Frobenius, die man sicherlich auch über das gegebene Polynom erhalten könnte. D.h., wenn ich z.B. ein Element nehme, wie sieht dann aus? Ich würde mein Ergebnis gerne verifizieren lassen, oder noch etwas mehr Zeit da rein investieren, die ich aber leider nicht habe unglücklich

Zitat:
Original von Elvis
Hilbert und ich ( Big Laugh )

Big Laugh

Zitat:
Original von Elvis haben uns immer bemüht, die Galoistheorie für algebraische und zahlentheoretische Strukturen zu nutzen, und gerade die endlichen Körper sind ein Musterbeispiel für den Erfolg der Galoistheorie, deshalb heißen sie auf englisch Galoisfield .
Wenn man ein einziges irreduzibles Polynom vom Grad n über gefunden hat, ergibt sich alles von selbst. Man kann dann die Teilkörper bestimmen und darin primitive Elemente finden, deren Minimalpolynome konstituieren die Zwischenkörper und du hast den gewünschten Turm konstruiert. Das Problem beim Aufbau von unten nach oben sehe ich darin, dass man jeden Zwischenkörper und seine Elemente verstanden haben muss bevor es auch nur einen Schritt weitergeht. Um zu wissen, welche Zwischenkörper auftreten benutzt man ja ohnehin die Galoistheorie, warum also nicht die ganze Lösung mit einem Rutsch.

Das irreduzible Polynom wäre in dem Fall tatsächlich .

Ich dachte, wenn ich das Polynom weitestgehend faktorisiere, würde mich das zu diesen Tower Fields bringen. Setze ich in diesem Fall für mein U die Gleichheit ein, erhalte ich als ersten Faktor bereits und die anderen Faktoren wären natürliche Teiler davon. Natürlich ist (beispielsweise) in , was sich ja dann auf unseren Fall Übertragen würde. Insgesamt bin ich aber der Meinung, dass die Polynome jeweils irreduzibel in ihren Körpern sind. Vielleicht wäre das nochmal nett zu beweisen?
Elvis Auf diesen Beitrag antworten »

Ich komme nicht gut voran, das läuft alles sehr schnell aus dem Ruder, und ich blicke nicht durch. Bei der Konstruktion von unten verstehe ich auch und insbesondere nicht, wie ich für einen die quadratischen und kubischen Polynome über dem Primkörper wählen muss, so dass die Komposition des und des tatsächlich einen ergibt, und wie rechnet man in diesem ? Dasselbe Kompositionsproblem habe ich dann auch bei der Wahl des quadratischen und kubischen Polynoms über und , verträgt sich das immer mit jeder Wahl eines quadratischen Polynoms über , so dass ein entsteht ? Würdest du hier nur einen Zweig nach oben verfolgen und die anderen Teilkörper nachträglich betrachten ? Mit Zweigen meine ich in diesem Beispiel oder oder .

Was machst du, wenn die Wurzel aus 2 schon im Grundkörper enthalten ist ? Was machst du im Fall der Charakteristik 2 ?
Shalec Auf diesen Beitrag antworten »

William Stein hatte hierzu eine Vorgehensweise empfohlen. Er nahm als Ausgangselement ebenfalls die 2, also definierte dann und nahm das Polynom vom Grad 3 und baute darauf dann auf. Ich suche grade vergeblich diesen Thread aus dem Google-Board bzgl. einer Konstruktionshilfe bei Sage. ..Gefunden! [1] Ich vertraue da auf seine Kenntnisse in dem Gebiet. smile Leider brauche ich aber Arithmetik zum Einbettungsgrad 16, anstelle, wie hier, 12.

Auch betrachte ich bereits eine feste Primzahl, sodass meine Herleitungen schon etwas direkter sind. Leider ist die Primzahl so groß, dass man sie sich noch nicht mal merken kann (und sogar noch größer..). Insgesamt ist sie eben kongruent zu 13 mod 32. Also rechne ich mit dem kleinsten Vertreter, der die meiste Ähnlichkeit zu der Primzahl hat, was hier tatsächlich die Zahl 13 ist. Leider lassen sich aber davon nicht alle Erkenntnisse direkt übertragen, müssen vorher noch für diese Primzahl validiert werden und da muss ich mich leider auf Computerprogramme verlassen smile


[1] https://groups.google.com/forum/#!msg/sage-support/0CEExpCEZmQ/qLicLWV2alIJ
Elvis Auf diesen Beitrag antworten »

So langsam verstehe ich dein Problem ... nicht ganz so viel Theorie ... sehr viel Arbeit ... wenn ich noch etwas für dich tun kann, melde dich wieder ... Programme habe ich nicht, ich muss mit dem bißchen auskommen, was ich im Kopf habe (und in Büchern).
Elvis Auf diesen Beitrag antworten »

Du hattest gefragt, was der gute alte Frobenius mit einem Körperelement macht. Das ist ganz einfach (nachdem ich viel zu lange herumgerechnet und danach erst nachgedacht habe).
Man nehme ein erzeugendes Element , also eine Nullstelle des (normierten) irreduziblen Polynoms .
Dann gilt für jeden Körperautomorphismus und jedes . Man muss also nur auf einem erzeugenden Element kennen und kennt ihn überall.
Speziell für den Frobenius-Automorphismus ist daher .
D.h.: nur einmal anwenden, alles andere ist berechnen von Potenzen, Produkten und Summen im Körper .
Shalec Auf diesen Beitrag antworten »

Zunächst, vielen Dank für das Angebot. Darauf komme ich gewiss zurück. smile

Elegante Anwendung der Homomorphieeigenschaft und Ausnutzung der besonderen Struktur der Elemente. An sowas hatte ich ganz am Anfang auch gedacht. Mir fiel es nur recht schwer das alles in "Code" zu packen. Bzw. in eine Form zu überführen, mit der ich dann auch einem Computer "mal eben" sagen kann, was er zu tun hat.

Wenn ich mich korrekt erinnere ist mit einer Basis , also in diesem Fall ist sigma die Potenzierung und stellt die Konjugierten zu theta dar.

Am Anfang meiner Masterarbeit (so auf den ersten 20 Seiten) behandele ich viel algebraische Zahlentheorie, wo ich genau diese Theorie mit verwendet hatte. Jedoch ohne Verbindung zwischen dieser Theorie und dem Frobenius. Auf endlichen Körpern ist er ja tatsächlich ein Automorphismus, bei elliptischen Kurven nur ein Endomorphismus. Ich hatte diese Theorie lediglich für die Diskriminante von Zahlkörpern und so gebraucht.

Tatsächlich muss ich langsam anfangen meinen Kram richtig zu fokussieren und ein lauffähigen Programm auf einem Mikrocontroller zu entwickeln. Mit diesem Ziel betreibe ich gerade "Anwendungsforschung" Big Laugh (wie z.B. im Thread zur Invertierung bei Norm=1)

Also vielen Dank nochmal für die Hilfe.
Sage gibt es übrigens als Online-Cloud-Programm. Das quasi nach Projekten Sortiert wird und eine sehr effiziente Berechnung von einigem Krams bietet. ich glaube der Link ging "cloud.sagemath.com"
Elvis Auf diesen Beitrag antworten »

Die Summe geht nur bis , wenn der Grad des normierten Polynoms mit ist, weil dann ganz konkret gilt.
Wieso steht in der Basis ? Genügen nicht einfach die Potenzen von ? Die Potenzierung ist ja ganz sicher kein Automorphismus.
Shalec Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
Die Summe geht nur bis , wenn der Grad des normierten Polynoms mit ist, weil dann ganz konkret gilt.


Ja stimmt, beim Tippen nicht drauf geachtet.

Zitat:
Original von Elvis
Wieso steht in der Basis ? Genügen nicht einfach die Potenzen von ? Die Potenzierung ist ja ganz sicher kein Automorphismus.

Das stimmt auch, dass die Potenzierung kein Automorphismus ist. Es kommt hier auf die Definition von Konjugationen an, daher allgemein mit sigma. In den Zahlkörpern sind die Konjugationen, falls ich mich korrekt erinnere ist es eins der beiden Alternativen, entweder isomorph zu den Potenzen oder die Potenzen selbst.

Insgesamt reicht es aber, wenn man davon spricht, dass die Basis aus den Konjugierten zu Theta besteht. smile
Elvis Auf diesen Beitrag antworten »

Verstehe ich nicht. Es sind immer die Potenzen von bis zu mit , die eine Basis bilden. Sie liegen in einem Körper. Die konjugierten Elemente bilden konjugierte Körper, bei galoisschen Körpererweiterungen gehören diese zu konjugierten Untergruppen der Galoisgruppe.
Im Fall algebraischer Zahlkörper gilt : Sei ein Zahlkörper vom Grad (also ). Es gibt genau Körper-Homomorphismen . Stellen wir uns als einen Teilkörper von vor, so werden wir als die gegebene Einbettung wählen. Die Elemente heißen die zu konjugierten Elemente. (Das dient nur der Verdeutlichung, ist bei abelschen Körpererweiterungen, speziell bei endlichen Körpern, deren Galoisgruppe immer zyklisch ist, nicht wichtig, da hier alle konjugierten Untergruppen zusammenfallen.)
Shalec Auf diesen Beitrag antworten »

Also ich weiß, dass du recht hast und dass ich meins so ähnlich meinte. Ich werde mir auf jeden Fall sowas nochmal im Detail angucken.

Ich hatte das so in Erinnerung, dass ich dazu die Konjugierten betrachten muss. Ich werde das demnächst nochmal nachschlagen, bin aber grad etwas zu sehr unter Zeitdruck. smile
Neue Frage »
Antworten »



Verwandte Themen

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