Nichtkanonischer Isomorphismus endlicher Körper

14.09.2009, 19:04

Elvis

Auf diesen Beitrag antworten »

Nichtkanonischer Isomorphismus endlicher Körper

Hallo, wir wissen, daß $\begin{eqnarray*} \mathbb F_9\cong \mathbb F_3[X]/(X^2+1) \cong \mathbb F_3[X]/(X^2+X+2) \end{eqnarray*}$ . Denn die quadratischen Polynome sind irreduzbel über $\begin{eqnarray*} \mathbb F_3 \end{eqnarray*}$ , also haben die Restklassenkörper den Grad 2 über $\begin{eqnarray*} \mathbb F_3 \end{eqnarray*}$ , und $\begin{eqnarray*} \mathbb F_9 \end{eqnarray*}$ ist als Zerfällungskörper von $\begin{eqnarray*} X^9-X \end{eqnarray*}$ isomorph zu jedem Körper mit 9 Elementen.
Kann mir jemand sagen, wie man in diesem Fall (und vielleicht sogar allgemeiner für endliche Körper) einen Isomorphismus explizit konstruiert ?

14.09.2009, 21:58

system-agent

Auf diesen Beitrag antworten »

Leider weiss ich nicht ob meine Idee zielführend ist, aber ich wäre so vorgegangen:
Beide Versionen von $\begin{eqnarray*} \mathbb F_9 \end{eqnarray*}$ sind auch jeweils ein zweidimensionaler $\begin{eqnarray*} \mathbb F_3 \end{eqnarray*}$ -Vektorraum mit Basis $\begin{eqnarray*} (1,\alpha) \end{eqnarray*}$ bzw $\begin{eqnarray*} (1,\beta) \end{eqnarray*}$ wobei $\begin{eqnarray*} \alpha \end{eqnarray*}$ eine Nullstelle von $\begin{eqnarray*} X^2+1 \end{eqnarray*}$ und $\begin{eqnarray*} \beta \end{eqnarray*}$ eine Nullstelle von $\begin{eqnarray*} X^2+X+2 \end{eqnarray*}$ ist.
Dann setze
$\begin{eqnarray*} f:\mathbb F_3[X]/(X^2+1)\to\mathbb F_3/(X^2+X+2) \end{eqnarray*}$
durch
$\begin{eqnarray*} a+\alpha\cdot b\mapsto a+\beta\cdot b \end{eqnarray*}$
[da $\begin{eqnarray*} f \end{eqnarray*}$ auf $\begin{eqnarray*} \mathbb F_3 \end{eqnarray*}$ konstant sein soll].

15.09.2009, 09:37

Mystic

Auf diesen Beitrag antworten »

@system-agent

Bei deiner Abbildung wäre insbesondere

$\begin{eqnarray*} f(\alpha)=\beta \end{eqnarray*}$

Wäre also $\begin{eqnarray*} f \end{eqnarray*}$ tatsächlich ein Isomorphismus, so hätte man dann

$\begin{eqnarray*} \beta^2=f(\alpha)^2=f(\alpha^2)=f(-1)=-1 \end{eqnarray*}$

d.h. $\begin{eqnarray*} \beta \end{eqnarray*}$ wäre ebenfalls Nullstelle von $\begin{eqnarray*} x^2+1 \end{eqnarray*}$ , was aber nicht zutrifft.

15.09.2009, 10:17

Mystic

Auf diesen Beitrag antworten »

@Elvis

Wenn ich die von system-agent eingeführte Notation verwende, so gilt

$\begin{eqnarray*} \alpha^4 ={(\alpha^2)}^2=(-1)^2=1 \end{eqnarray*}$

jedoch

$\begin{eqnarray*} \beta^4 ={(-\beta-2)}^2 = \beta^2+\beta +1 =-1 \end{eqnarray*}$

d.h. $\begin{eqnarray*} \beta \end{eqnarray*}$ ist primitives Element, $\begin{eqnarray*} \alpha \end{eqnarray*}$ ist es nicht. Bei einem Isomorphismus müssen aber natürlich primitive Elemente auf primitive Elemente mit dem gleichen Minimalpolynom abgebildet werden. Wenn man umgekehrt im ersten Körper ein

$\begin{eqnarray*} \gamma = a+b \alpha \end{eqnarray*}$

findet, für das ebenfalls gilt

$\begin{eqnarray*} \gamma^2+\gamma +2 =0 \end{eqnarray*}$

sollte es dann mit der durch

$\begin{eqnarray*} 0 \mapsto 0 , \qquad \gamma^k \mapsto \beta^k, k=0,1,..,7 \end{eqnarray*}$

definierten Abbildung dann auch klappen.

15.09.2009, 18:59

Elvis

Auf diesen Beitrag antworten »

Vielen Dank, das klappt prima, bei der Rechnung haben mir auch die Gruppentafeln der Multiplikation geholfen. Man sieht dann sehr schnell daß $\begin{eqnarray*} 1+\alpha \end{eqnarray*}$ und $\begin{eqnarray*} 1+2\alpha \end{eqnarray*}$ die beiden Nullstellen von $\begin{eqnarray*} \gamma^2+\gamma+2\in (\mathbb F_3[X]/(X^2+1))[\gamma] \end{eqnarray*}$ sind.
Damit definiere ich den Isomorphismus $\begin{eqnarray*} \phi:\mathbb F_3/(X^2+X+2) \to \mathbb F_3/(X^2+1) \end{eqnarray*}$ durch $\begin{eqnarray*} \beta \to 1+\alpha \end{eqnarray*}$ . Es ist dann $\begin{eqnarray*} \phi^{-1} (0,1,2,\alpha ,1+\alpha ,2+\alpha ,2\alpha ,1+2\alpha ,2+2\alpha )=(0,1,2,2+\beta ,\beta ,1+\beta ,1+2\beta ,2+2\beta ,2\beta ) \end{eqnarray*}$ .

Mit ein bißchen Rechnung ergibt sich
$\begin{eqnarray*} \phi((a+b\beta)+(c+d\beta))=...=(a+b+c+d)+(b+d)\alpha=...=\phi(a+b\beta)+\phi(c+d\beta) \end{eqnarray*}$
und
$\begin{eqnarray*} \phi((a+b\beta)(c+d\beta))=...=(ac+ad+bc)+(ad+bc-bd)\alpha=...=\phi(a+b\beta)\phi(c+d\beta) \end{eqnarray*}$
und nur im letzten Rechenschritt braucht man $\begin{eqnarray*} (1+\alpha)^2=2\alpha=-\alpha \end{eqnarray*}$ , der Rest ist trivial.

Nochmals vielen Dank, jetzt habe ich ein schönes Beispiel, nach dem ich doch immerhin ein paar Tage gesucht habe.

Lässt sich diese Konstruktion zu einem Prinzip erheben, ungefähr so ?
Man nehme ein erzeugendes Element $\begin{eqnarray*} \beta\in\mathbb (F_q^*,\beta) \end{eqnarray*}$ mit $\begin{eqnarray*} f(\beta)=0 \end{eqnarray*}$ und bilde es ab auf ein Element $\begin{eqnarray*} \gamma\in\mathbb (F_q^*,\alpha) \end{eqnarray*}$ für das $\begin{eqnarray*} f(\gamma)=0 \end{eqnarray*}$ gilt.

15.09.2009, 20:55

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Lässt sich diese Konstruktion zu einem Prinzip erheben, ungefähr so ?
Man nehme ein erzeugendes Element $\begin{eqnarray*} \beta\in\mathbb (F_q^*,\beta) \end{eqnarray*}$ mit $\begin{eqnarray*} f(\beta)=0 \end{eqnarray*}$ und bilde es ab auf ein Element $\begin{eqnarray*} \gamma\in\mathbb (F_q^*,\alpha) \end{eqnarray*}$ für das $\begin{eqnarray*} f(\gamma)=0 \end{eqnarray*}$ gilt.

Wenn f(x) das Minimalpolynom von $\begin{eqnarray*} \beta \end{eqnarray*}$ über dem Primkörper war, ist das sicher richtig.

Anzeige

16.09.2009, 18:51

Elvis

Auf diesen Beitrag antworten »

Ja, und weil man weiß, daß die Körper unabhängig von der Konstruktion isomorph sind, muß es immer passende Nullstellen $\begin{eqnarray*} \gamma \end{eqnarray*}$ in jedem dieser Körper geben.
Sind (einige) endliche Körper in der Literatur oder im Internet tabelliert ? Gibt es Tabellen von irreduziblen Polynomen vorgegebenen Grades über $\begin{eqnarray*} \mathbb F_p \end{eqnarray*}$ und explizite Beschreibungen dieser Isomorphismen, oder so etwas wie "Kochrezepte" ?

16.09.2009, 19:48

Mystic

Auf diesen Beitrag antworten »

Nachfolgender Link

Handbook of Applied Cryptography, Chapter 4

sollte eigentlich in dem Abschnitt über irreduzible Polynome über $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ alle Fragen ebendiese betreffend beantworten. Speziell für p=2 gibt's übrigens die berühmte Vermutung, dass man auf der Suche nach irreduziblen Polynomen mit höchstens 5 Monomen stets auskommt.

16.09.2009, 20:03

Elvis

Auf diesen Beitrag antworten »

Danke.

smile

17.09.2009, 19:18

Elvis

Auf diesen Beitrag antworten »

Korollar: Jeder endliche Körper $\begin{eqnarray*} \mathbb F_{p^n} \end{eqnarray*}$ enthält alle Nullstellen aller Polynome $\begin{eqnarray*} f(X)\in\mathbb F_p[X] \end{eqnarray*}$ n-ten Grades.

Weiß das sowieso jeder außer mir, oder können wir das "Satz von Elvis" nennen ? Augenzwinkern

Augenzwinkern

Oder ist das gar nicht wahr ? verwirrt

verwirrt

17.09.2009, 20:05

kiste

Auf diesen Beitrag antworten »

Ich hoffe ich hab mich nicht verrechnet, aber x^3+x^2+x sollte über F_8 keine Nullstelle haben(außer natürlich 0).

Aber ich vermute mal stark wenn man n durch n! ersetzt dass es passt.

17.09.2009, 21:14

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Korollar: Jeder endliche Körper $\begin{eqnarray*} \mathbb F_{p^n} \end{eqnarray*}$ enthält alle Nullstellen aller Polynome $\begin{eqnarray*} f(X)\in\mathbb F_p[X] \end{eqnarray*}$ n-ten Grades.

Weiß das sowieso jeder außer mir, oder können wir das "Satz von Elvis" nennen ? Augenzwinkern

Augenzwinkern

Oder ist das gar nicht wahr ? verwirrt

verwirrt

Das ist wahr, aber leider auch ein alter Hut... Augenzwinkern

Augenzwinkern

Die Minimalpolynome n-ten Grades über $\begin{eqnarray*} \mathbb Z_p \end{eqnarray*}$ teilen ja alle das Polynom

$\begin{eqnarray*} x^{p^n}-x \end{eqnarray*}$

und dieses zerfällt in $\begin{eqnarray*} \mathbb F_{p^n} \end{eqnarray*}$ bekanntlich vollständig in Linearfaktoren...

Und ja, das Beispiel von Kiste ist falsch, denn sein Polynom zerfällt ja sogar schon über $\begin{eqnarray*} \mathbb F_4 \end{eqnarray*}$ in Linearfaktoren...

Edit: Sorry, gilt nur für IRREDUZIBLE Polynome n-ten Grades in dieser Form...Das Beispiel von Kiste ist zwar falsch, aber man muss deine Behauptung schon insofern einschränken, als nur die irreduziblen Polynome, deren Grad m ein Teiler von n ist, über $\begin{eqnarray*} \mathbb F_{p^n} \end{eqnarray*}$ vollständig zerfallen...

17.09.2009, 21:39

Mystic

Auf diesen Beitrag antworten »

Ok, ist heute offenbar nicht mein Tag... Das Beispiel von Kiste und was er sonst gesagt hat ist natürlich richtig und die Begründung habe ich ja auch selbst oben gegeben... Aus der Lösbarkeit in $\begin{eqnarray*} \mathbb F_4 \end{eqnarray*}$ folgt natürlich nicht die in $\begin{eqnarray*} \mathbb F_8 \end{eqnarray*}$ ... Hammer

Hammer

18.09.2009, 19:00

Elvis

Auf diesen Beitrag antworten »

Danke ... da kann man gar nicht lange genug drüber nachdenken ...

19.09.2009, 12:02

Elvis

Auf diesen Beitrag antworten »

Klar ist : $\begin{eqnarray*} 2\not | 3 \Rightarrow \mathbb F_4 \not\subset \mathbb F_8 \end{eqnarray*}$ .

Und das Gegenbeispiel von Kiste habe ich auch nachgerechnet. $\begin{eqnarray*} x^3+x^2+x=x(x^2+x+1) \end{eqnarray*}$ hat 0 als Nullstelle, der quadratische Faktor hat keine Nullstelle in $\begin{eqnarray*} \mathbb F_8 \end{eqnarray*}$ .

Bleibt immerhin "der kleine Satz von Elvis Augenzwinkern

Augenzwinkern

": Jeder endliche Körper $\begin{eqnarray*} \mathbb F_{p^n} \end{eqnarray*}$ enthält alle Nullstellen aller irreduziblen Polynome $\begin{eqnarray*} f(X)\in\mathbb F_p[X] \end{eqnarray*}$ n-ten Grades.

19.09.2009, 14:05

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Bleibt immerhin "der kleine Satz von Elvis Augenzwinkern

Augenzwinkern

": Jeder endliche Körper $\begin{eqnarray*} \mathbb F_{p^n} \end{eqnarray*}$ enthält alle Nullstellen aller irreduziblen Polynome $\begin{eqnarray*} f(X)\in\mathbb F_p[X] \end{eqnarray*}$ n-ten Grades.

Ja, so habe ich das auch zunächst gelesen und daher auch meine ursprünglich zustimmende Antwort auf dein Posting weiter oben, bis mir dann langsam gedämmert ist, dass du die Irreduzibilität von f(x) ja gar nicht vorausgesetzt hattest. unglücklich

unglücklich

Ich würde übrigens deinen obigen Satz eine Spur allgemeiner so formulieren:

Genau dann zerfällt ein Poynom $\begin{eqnarray*} f(X)\in\mathbb F_p[X] \end{eqnarray*}$ n-ten Grades in $\begin{eqnarray*} \mathbb F_{p^n}[X] \end{eqnarray*}$ vollständig in Linearfaktoren, wenn alle irreduziblen Teiler von f(X) in $\begin{eqnarray*} \mathbb F_p[X] \end{eqnarray*}$ einen Grad haben, der n teilt. Dies trifft insbesondere dann zu, wenn $\begin{eqnarray*} f(X)\in\mathbb F_p[X] \end{eqnarray*}$ selbst schon irreduzibel ist.

19.09.2009, 14:58

Elvis

Auf diesen Beitrag antworten »

Das gefällt mir, danke. Irreduzible Faktoren vom Grad $\begin{eqnarray*} m|n \end{eqnarray*}$ zerfallen ja schon in $\begin{eqnarray*} \mathbb F_{p^m}\subset \mathbb F_{p^n} \end{eqnarray*}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »