Einfaches Beispiel: Isomorphismus zwischen endlichen Körpern

18.03.2017, 14:10

Shalec

Einfaches Beispiel: Isomorphismus zwischen endlichen Körpern

Hallo allerseits,

ich kann mir einen Zusammenhang nicht vollständig erklären. Warum gilt $\begin{eqnarray*} \mathbb Z_{p^{12}}\cong \mathbb Z_{p^2}[x]/(x^6-1) \end{eqnarray*}$

Ich sehe anhand des herausgeteilten Ideals, dass x eine 6-te Einheitswurzel ist und, dass $\begin{eqnarray*} (p^2)^6 = p^{12} \end{eqnarray*}$ ist. Mir fehlt gerade aber irgendwie das richtige Argument, warum man diese Isomorphie annehmen kann?

Bei Wikipedia [1] stehen auch andere Beispiele, wie z.B. für $\begin{eqnarray*} \mathbb Z_{7^2}, \mathbb Z_{5^2} \end{eqnarray*}$ wobei $\begin{eqnarray*} \mathbb Z_{5^2}\cong \mathbb Z_5[x]/(x^2-2) \cong \mathbb Z_5[\sqrt{2}] \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb Z_{7^2}\cong \mathbb Z_7[x]/(x^2+1)\cong \mathbb Z_7[i] \end{eqnarray*}$

Könnte mir jemand erklären, welche Überlegungen angestellt werden, um das jeweilige Polynom zu finden? Dies wird was mit dem Minimalpolynom eines primitiven Elements zu tun haben?

Viele Grüße und vielen Dank

[1] https://de.wikipedia.org/wiki/Endlicher_K%C3%B6rper#Der_K.C3.B6rper_mit_25_Elementen

18.03.2017, 14:15

Elvis

Auf diesen Beitrag antworten »

Es gibt bis auf Isomorphie genau einen Körper mit $\begin{eqnarray*} p^{12} \end{eqnarray*}$ Elementen. Allgemein gibt es bis auf Isomorphie genau einen Körper mit $\begin{eqnarray*} q=p^n \end{eqnarray*}$ Elementen, $\begin{eqnarray*} p \end{eqnarray*}$ Primzahl, $\begin{eqnarray*} n \end{eqnarray*}$ natürliche Zahl. Durch welche Nullstelle welches irreduziblen Polynoms man diesen Körper durch Adjunktion aus $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ konstruiert, ist also egal.

18.03.2017, 14:20

tatmas

Auf diesen Beitrag antworten »

Hallo,

was soll $\begin{eqnarray*} \mathbb Z _{p^{12}} \end{eqnarray*}$ für ein Objekt sein?

Soll es ein Körper mit $\begin{eqnarray*} p^{12} \end{eqnarray*}$ Elementen sein, dann wäre die Notation $\begin{eqnarray*} \mathbb F_{p^{12}} \end{eqnarray*}$ oder evtl. auch $\begin{eqnarray*} GF(p^{12}) \end{eqnarray*}$ endeutiger.
Bei der Z- Unterstrich-Notation gibt es überschneidungen mit den ganzen p-adischen Zahlen mit bzw. ggf. Restklassenringen oder Lokalisierungen der ganzen Zahlen.

Der rechte Ring ist allerdings kein Körper, denn $\begin{eqnarray*} x^6-1 \end{eqnarray*}$ hat eine Nullstelle ist also reduzibel.

Zitat:

Könnte mir jemand erklären, welche Überlegungen angestellt werden, um das jeweilige Polynom zu finden?

Ich verstehe nicht wirklich worum es dir hier konkret geht. Welches Polynom willst du finden und warum?

18.03.2017, 15:09

Shalec

Auf diesen Beitrag antworten »

Zitat:

Original von tatmas
Hallo,

was soll $\begin{eqnarray*} \mathbb Z _{p^{12}} \end{eqnarray*}$ für ein Objekt sein?

Soll es ein Körper mit $\begin{eqnarray*} p^{12} \end{eqnarray*}$ Elementen sein, dann wäre die Notation $\begin{eqnarray*} \mathbb F_{p^{12}} \end{eqnarray*}$ oder evtl. auch $\begin{eqnarray*} GF(p^{12}) \end{eqnarray*}$ endeutiger.
Bei der Z- Unterstrich-Notation gibt es überschneidungen mit den ganzen p-adischen Zahlen mit bzw. ggf. Restklassenringen oder Lokalisierungen der ganzen Zahlen.

Der rechte Ring ist allerdings kein Körper, denn $\begin{eqnarray*} x^6-1 \end{eqnarray*}$ hat eine Nullstelle ist also reduzibel.

Hey,
ja in der Zahlentheorie gibt es da durchaus Überschneidungen. In den Papern, die ich derzeit lese wird $\begin{eqnarray*} \mathbb F_q =\mathbb Z_q := \mathbb Z/q\mathbb Z \end{eqnarray*}$ identifiziert. (Normalerweise geht man bei $\begin{eqnarray*} \mathbb F_q \end{eqnarray*}$ von einem Körper mit q Elementen aus. Die Autoren sind da aber auch nicht unbedingt immer präzise, in der Einleitung wird von einem "Field $\begin{eqnarray*} \mathbb F_q \end{eqnarray*}$ gesprochen, später notieren die dann in Beweise eine Ordnung, die allerdings nur auf $\begin{eqnarray*} \mathbb Z_q \end{eqnarray*}$ hindeutet. Exakt definiert wird es in keinem der Paper. Am Ende betrachte ich ohnehin nur $\begin{eqnarray*} \mathbb F_{2^{12}}, \mathbb F_{2^2} \end{eqnarray*}$ und $\begin{eqnarray*} \mathbb F_{2} \end{eqnarray*}$ )

Zitat:

Original von tatmas

Zitat:

Könnte mir jemand erklären, welche Überlegungen angestellt werden, um das jeweilige Polynom zu finden?

Ich verstehe nicht wirklich worum es dir hier konkret geht. Welches Polynom willst du finden und warum?

In einem Paper wurde das Polynom $\begin{eqnarray*} x^6-1 \end{eqnarray*}$ herausgeteilt und in dem Ring modulo dieses Polynom weiter Rechnungen angestellt. Dieses Polynom lässt sich übrigens in 4 Faktoren zerlegen. $\begin{eqnarray*} (x\pm 1) \end{eqnarray*}$ und $\begin{eqnarray*} (x^2 \pm x +1) \end{eqnarray*}$

Wie ich sehe, ist die Aussage von Elvis nur in einer der beiden Interpretationsmöglichkeiten von $\begin{eqnarray*} \mathbb F_q \end{eqnarray*}$ sinnvoll. Ich finde leide die Stelle nicht mehr genau, in der die Ordnung des Ringes betrachtet wurde. Sobald ich sie gefunden habe, editiere ich diesen Post oder füge einen hinzu.

18.03.2017, 16:55

tatmas

Auf diesen Beitrag antworten »

Zitat:

In den Papern, die ich derzeit lese wird $\begin{eqnarray*} \mathbb F_q =\mathbb Z_q := \mathbb Z/q\mathbb Z \end{eqnarray*}$ identifiziert.

Ich kenn solche Paper auch. Dennoch oder gerade deswegen ist es sinnvoll selbst die präzisere Notation zu verwenden.

Zitat:

. Dieses Polynom lässt sich übrigens in 4 Faktoren zerlegen. $\begin{eqnarray*} (x\pm 1) \end{eqnarray*}$ und $\begin{eqnarray*} (x^2 \pm x +1) \end{eqnarray*}$

Das ist durchaus richtig. Und zeigt dass Kontext sehr viel hilft.
Worum geht es in dem Paper (evtl. zyklische Codes?) dann könnte man/ich auch mehr dazu sagen.

18.03.2017, 17:41

Shalec

Auf diesen Beitrag antworten »

Tatsächlich geht es um kryptographische Pairings. [2] baut auf [1] auf. Ich weiß nicht mehr genau, in welchem der beiden Paper die Ungenauigkeit zu finden war. Ich konnte mir nur nicht genau erklären, wie man darauf kommt, dass $\begin{eqnarray*} \mathbb F_{p^{12}}\cong \mathbb F_{p^2}[x]/(x^6-1) \end{eqnarray*}$ obwohl ich mich an sowas aus einer kommutativen Algebra Vorlesung erinnere smile

Im Endeffekt geht es nur darum, dass jedes Element aus $\begin{eqnarray*} \mathbb F_{p^{12}} \end{eqnarray*}$ als Element in $\begin{eqnarray*} \mathbb F_{p^2}[x]/(x^6-1) \end{eqnarray*}$ darstellen lässt und daher nur $\begin{eqnarray*} \mathbb F_{p^2} \end{eqnarray*}$ Arithmetik implementiert werden muss. Dazu wird dann in [2, S. 5 unter Table 2] eine Nullstelle des Polynoms gewählt und das Element als formale Summe notiert.

In [1] wird nicht $\begin{eqnarray*} x^6-1 \end{eqnarray*}$ sondern allgemeiner $\begin{eqnarray*} x^6-\xi \end{eqnarray*}$ betrachtet, mit der Einschränkung, dass $\begin{eqnarray*} \xi \end{eqnarray*}$ so gewählt werden muss, dass dieses Polynom irreduzibel über $\begin{eqnarray*} \mathbb F_{p^2} \end{eqnarray*}$ ist. (Allgemein frage ich mich gerade, woher ich $\begin{eqnarray*} x^6-1 \end{eqnarray*}$ habe.. vermutlich aus der Point Compression in [2] als einer der Faktoren der "Final-exponentiation" der Miller-Loop)

Da in beiden Papern von Körpern gesprochen wird, und $\begin{eqnarray*} \mathbb Z/q\mathbb Z \end{eqnarray*}$ i.A. keine Körper sind (für Primzahlpotenzen q), gehe ich doch lieber davon aus, dass hiermit GF(q) gemeint ist.

Wie dem auch sei, ich werde diese Klasse der elliptischen Kurven nicht verwenden können, da sie zu langsam in der angestrebten Sicherheit sind. (D.h. die Algorithmen sind nicht effizient genug..)

[1] http://eprint.iacr.org/2005/133
[2] http://eprint.iacr.org/2007/390

18.03.2017, 20:11

tatmas

Auf diesen Beitrag antworten »

Zitat:

Ich konnte mir nur nicht genau erklären, wie man darauf kommt, dass $\begin{eqnarray*} \mathbb F_{p^{12}}\cong \mathbb F_{p^2}[x]/(x^6-1) \end{eqnarray*}$ obwohl ich mich an sowas aus einer kommutativen Algebra Vorlesung erinnere smile

Dann ist jetzt die Frage was für eine Isomorphie das sein soll.
Eine von Ringen oder Körpern kann es nicht sein.
Eine von Vektorräumen oder Gruppen dagegen schon.

Zitat:

Ich weiß nicht mehr genau, in welchem der beiden Paper die Ungenauigkeit zu finden war.

Ich sehe in keinem der beiden Paper ein $\begin{eqnarray*} X^6-1 \end{eqnarray*}$ noch ein $\begin{eqnarray*} \mathbb Z_{whatever} \end{eqnarray*}$

Zitat:

D.h. die Algorithmen sind nicht effizient genug..

Hier sind wir langsam aber sicher in der Kategorie: Dann musst du halt schauen obdu selbst die Algorithmen verbessern kannst.

19.03.2017, 07:57

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Shalec
In den Papern, die ich derzeit lese wird $\begin{eqnarray*} \mathbb F_q =\mathbb Z_q := \mathbb Z/q\mathbb Z \end{eqnarray*}$ identifiziert

Für eine Primzahl $\begin{align*} q \end{align*}$ stimmt das ja auch. Und für andere Primzahlpotenzen ist es falsch.
Den Ring $\begin{align*} \mathbb{Z} / q \mathbb{Z} \end{align*}$ gibt es immer. Und warum nicht abkürzend dafür $\begin{align*} \mathbb{Z}_q \end{align*}$ schreiben? Der Ring ist allerdings nur für den Fall, daß $\begin{align*} q \end{align*}$ eine Primzahl ist, ein Körper.
Mich beschleichen leise Zweifel, daß du deine Paper sorgfältig genug durchgearbeitet hast. Vielleicht geht es an den von dir bezweifelten Stellen tatsächlich um den Ring $\begin{align*} \mathbb{Z}_q \end{align*}$ und gar nicht um einen Körper. Oder $\begin{align*} q \end{align*}$ ist an diesen Stellen eine Primzahl, womit dann $\begin{align*} \mathbb{Z}_q \end{align*}$ auch ein Körper wäre.

19.03.2017, 09:54

tatmas

Auf diesen Beitrag antworten »

Zitat:

Und warum nicht abkürzend dafür ℤq schreiben?

Weil $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ bereits eine Bedeutung hat: Der Ring der ganzen p-adische Zahlen.
Und wie ich bereits auch im ,einem letzten Post geschrieben hab, ist die Z_Unterstrich -Notation in den 2 verlinkten Papern nicht zu finden, die Diskussion hier also müßig.

19.03.2017, 10:16

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von tatmas

Zitat:

Und warum nicht abkürzend dafür ℤq schreiben?

Weil $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ bereits eine Bedeutung hat: Der Ring der ganzen p-adische Zahlen.

Nun ja, so etwas ist ja immer kontextabhängig. Und ich glaube kaum, daß es in Shalecs Papers um die Henselschen Zahlkörper geht. Aber wie auch immer - wenn die Bezeichnung nicht vorkommt, ist die Diskussion wirklich müßig.

19.03.2017, 10:32

tatmas

Auf diesen Beitrag antworten »

Das sind paper über Pairings auf elliptischen Kurven. Da können durchaus so Sachen wie Tate-Module auftauchen, und das sind $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ _mOdulen . wenn sich sogar der Grundring seöbst.
Die kamen vor ich glaub zwei Wochen bei einer Frage von shalec auf.
p-adische Zahlen tauchen in der Zahlentheorie sehr oft irgendwo auf

Zitat:

Nun ja, so etwas ist ja immer kontextabhängig.

Ja, und es gibt eine Schreibweise die nicht Kontextabhängig ist und auch nicht mehr Schreibarbeit braucht.
Die mit F.

19.03.2017, 18:47

Shalec

Auf diesen Beitrag antworten »

Ich werde die Paper nochmal durchgehen und meine Frage dann mal in einem weiteren Post aktualisieren. Vielen Dank schonmal soweit. Ich scheine mich da entweder in meinen Notizen oder meiner Erinnerung verzettelt zu haben und nehme daher Leopolds Vorschlag, mich nochmal mit den Papern zu beschäftigen, zu herzen. smile

Neue Frage »

Antworten »

Einfaches Beispiel: Isomorphismus zwischen endlichen Körpern

Verwandte Themen