Kreisteilungspolynom

Beschreibung

Definition

Ein Polynom (Algebra) das durch das Produkt der Linearfaktoren zu primitiven n-ten Einheitswurzeln entsteht, d.h. ${\Phi }_n={\prod }_{\zeta \in {\mu }_n^{\times }}(x-\zeta )$ wird das $n$-te Kreisteilungspolynom genannt.

Eigenschaften

Grad

Da Kreisteilungspolynome das Produkt von Linearfaktoren errechnet aus Primitive Einheitswurzel ist, kann man den Grad erhalten, indem die Primitiven Einheitswurzeln zählt. Dazu kann man die Eulersche Phi Funktion verwenden: $grad({\Phi }_n(x))=\varphi (n)$

Produkte

Für alle $n\in \mathbb{N}$ gilt $x^n-1={\prod }_{d\mid n}{\Phi }_d$[^1]

Kreisteilungspolynome sind Ganzzahlig

Es gilt ${\Phi }_n\in \mathbb{Z}[x]$ für alle $n\in \mathbb{N}$.

In speziellen Fällen lassen sich explizite Formeln angeben.

• Für $p$ Primzahl ${\Phi }_p=x^{p-1}+...+x+1$
• Für $p^r$ Primzahlpotenz ${\Phi }_{p^r}={\sum }_{k=0}^{p-1}{x}^{k{p}^{r-1}}$ Zum Beispiel ${\Phi }_{25}=x^{20}+x^{15}+x^{10}+x^5+1$

Irreduzibel

Die Kreisteilungspolynome sind irreduzibel in $\mathbb{Z}[x]$ und $\text{Q}[x]$ aber nicht notwendigerweise in Endlicher Körper.

Berechnung

Kreisteilungspolynome lassen sich durch die Formel ${\Phi }_n(x)={\prod }_{d\mid n}(x^d-1{)}^{\mu (n/d)}$ berechnen, wobei $\mu$ die Möbius Mu Funktion ist.

Beweis: Es gilt $x^n-1={\prod }_{d\mid n}{\Phi }_d$. Das ist bloß eine Summatorische Funktion mit Multiplikation statt Summe geschrieben. Wir können also den Möbiusschen Umkehrsatz anwenden und erhalten die obere Formel.

Rechenformel

Sei $p$ eine Primzahl und $n$ eine dazu teierfremde Zahl. Dann gilt

• ${\Phi }_{n{p}^k}(x)={\Phi }_{np}(x^{p^{k-1}})$
• ${\Phi }_{n{p}^k}(x)=\frac{{\Phi }_n(x^{p^k})}{{\Phi }_n(x^{p^{k-1}})}$
• ${\Phi }_{n{p}^k}(n)={\Phi }_n(x{)}^{p^k-p^{k-1}}$ in einem Körper der Charakteristik $p$

Beispiele

Liste aller Kreisteilungspolynome

$n$	Polynom
$1$	$x-1$
$2$	$x+1$
$3$	$x^2+x+1$
$4$	$x^2+1$
$5$	$x^4+x^3+x^2+x+1$
$6$	$x^2-x+1$
$7$	$x^6+x^5+x^4+x^3+x^2+x+1$

Kreisteilungspolynom 5

${\Phi }_5=x^4+x^3+x^2+x+1$ Verwenden wir die Möbiustransformation: ${\Phi }_5(x)={\prod }_{d\mid 5}(x^d-1{)}^{\mu (5/d)}=\frac{x^5-1}{x-1}$ Das hätte man sich eigentlich denken können, denn es müsste $4$ Primitive Einheitswurzel geben. Wenn man also die Nullstelle $1$ als Linearfaktor aus dem Polynom entfernt, sollte man das gesuchte Polynom erhalten. Da ${\Phi }_5$ ein Polynom von Grad $\varphi (5)=4$ ist, müsste ${\Phi }_5(x)=\frac{x^5-1}{x-1}\mathrm{mod}{x}^5$ genauso aussehen, wie ${\Phi }_5(x)$. Wir können uns das zu Nutze machen, da rechnen in $\mathrm{mod}{x}^5$ viel leichter ist. \begin{align}\frac{x^5-1}{x-1} &= \frac{(x^5-1)(x^4+1)(x^2+1)(x+1)}{x^8-1}\\ &= (x^4+1)(x^2+1)(x+1) \\&= (x^4+1)(x^3+x^2+x+1) \\&= x^4+x^3+x^2+x+1\end{align} Da $x^5\equiv x^4\equiv 0\mathrm{mod}{x}^5$ und so weiter.

Kreisteilungspolynom 6

${\Phi }_6=x^2-x+1$. Das erhält man, indem man die Formel oben verwendet $x^6-1={\Phi }_1{\Phi }_2{\Phi }_3{\Phi }_6$ und die Gleichung nach ${\Phi }_6$ auflöst.

Kreisteilungspolynome Primzahlen

Für eine Primzahl $p$ hat das Kreisteilungspolynom die Form ${\Phi }_p(x)=x^{p-1}+x^{p-2}+...+x+1$ Beweis: Die $p$ Nullstellen des Polynom $x^p-1$ sind die $p$-ten Einheitswurzel. Diese bilden eine Zyklische Gruppe von Primzahlordnung $p$. Damit gibt es $\varphi (p)=p-1$ Erzeuger der Gruppe und damit $p-1$ Primitive Einheitswurzel. $1$ ist eine primitive Einheitswurzel, also sind es alle andere. Entfernen wir daher den Linearfaktor der Einheitswurzel $1$ aus $x^p-1$, dann müssten wir ${\Phi }_p(x)$ erhalten. ${\Phi }_p(x)=\frac{x^p-1}{x-1}=x^{p-1}+x^{p-2}+...+x+1$ denn ${\Phi }_p(x)=x^p-1=(x-1)(x^{p-1}+x^{p-2}+...+x+1)$

Übungen

McEliece Übung 7-1

Zeige, wenn $n$ ungerade, dann gilt ${\Phi }_{2n}(x)={\Phi }_n(-x)$

Wenn $n$ ungerade, dann sind $2$ und $n$ teilerfremd und es gilt: ${\Phi }_{n\ast 2^1}(x)=\frac{{\Phi }_n(x^2)}{{\Phi }_n(x^1)}=\frac{{\prod }_{d\mid n}(x^{2d}-1{)}^{\mu (n/d)}}{{\prod }_{d\mid n}(x^d-1{)}^{\mu (n/d)}}={\prod }_{d\mid n}(x^d+1{)}^{\mu (n/d)}$ Da $n$ ungerade ist, ist auch $d$ ungerade und es gilt: ${\prod }_{d\mid n}(x^d+1{)}^{\mu (n/d)}={\prod }_{d\mid n}(-(-x{)}^d+1{)}^{\mu (n/d)}={\prod }_{d\mid n}(-(1-(-x{)}^d){)}^{\mu (n/d)}$ Zerlege den Wert in $\mu$ in Primfaktoren: $\mu (n/d)=\mu (p_1^{e_1}...p_m^{e_m})$. Gibt es ein $e_i$ mit $e_i>1$, dann ist $\mu (p_1^{e_1}...p_m^{e_m})=0$. In dem Fall ist $(-(1-(-x{)}^d){)}^{\mu (n/d)}=(-(1-(-x{)}^d){)}^0=1=(1-(-x{)}^d{)}^{\mu (n/d)}$

Gibt es kein $e_i$ mit $e_1<1$, dann ist $\mu (n/d)=\pm 1$. In dem Fall gilt $(-(1-(-x{)}^d){)}^{\mu (n/d)}=-(1-(-x{)}^d{)}^{\mu (n/d)}$ Für jeden Teiler Faktor $n/d=p_1^0{p}_2^{e_2}...p_m^{e_m}$ gibt es einen eineindeutigen anderen Teiler $n/d^{\prime }=p_1^0{p}_2^{e_2}...p_m^{e_m}$, den man erhält, indem man die Zahl des ersten Promzahlexponenten zwischen $0$ und $1$ wechselt. Für jeden Faktor $(-(1-(-x{)}^d){)}^{\mu (n/d)}$ aus dem oberen Produkt gibt es damit einen eineindeutigen anderen Faktor $(-(1-(-x{)}^{d^{\prime }}){)}^{\mu (n/d^{\prime })}$, sodass $(-(1-(-x{)}^d){)}^{\mu (n/d)}(-(1-(-x{)}^{d^{\prime }}){)}^{\mu (n/d^{\prime })}=(1-(-x{)}^d{)}^{\mu (n/d)}(1-(-x{)}^{d^{\prime }}{)}^{\mu (n/d^{\prime })}$ Die Produkte, bei denen $\mu (d/n)=\pm 1$ haben also immer ein Gegenstück, bei dem sich das Minus auslöscht. Damit gilt ${\prod }_{d\mid n}(-(1-(-x{)}^d){)}^{\mu (n/d)}={\prod }_{d\mid n}(1-(-x{)}^d{)}^{\mu (n/d)}={\Phi }_n(-x)$

Ich glaube, das bringt uns nicht weiter, ich brobiere es stattdessen mit der Möbiustransformation: ${\Phi }_{2n}(x)={\prod }_{d\mid 2n}(x^d-1{)}^{\mu (n/d)}$

McEliece Übung 7-2

Uns fällt auf, dass in allen Kreisteilungspolynom außer im ersten der konstante Term $+1$ ist. Steckt da eine Regel dahinter?

Ja, es ist eine Regel. Man erhält ein Kreisteilungspolynom durch: ${\Phi }_n(x)={\prod }_{d\mid n}(x^d-1{)}^{\mu (n/d)}$ Das ist ein rationaler Bruch von Polynomen der Form $(x^d-1)$. Man kann den Bruch in ein Produkt aus Polynomen umschreiben, indem man den Schritten aus dem Beispiel Kreisteilungspolynom 6 folgt. Der konstante Term ist dann das Produkt aller konstanten Terme der Polynomfaktoren. Diese tauchen, wie ich in McEliece Übung 7-1 gezeigt habe in Paaren auf. Also muss der konstante Term $+1$ sein.

McEliece Übung 7-4

Berechne einige Polynome

a) ${\Phi }_{24}(x)$

${\Phi }_{24}(x)={\Phi }_{3\ast 2^3}(x)={\Phi }_6(x^4)=x^8-x^4+1$

b) $\Phi (35)$

$\varphi (35)=24$

&= \frac{\Phi_5(x^7)}{\Phi_5(x)} \\ &= \frac{\Phi_5(x^7)(x-1)}{x^5-1} \\ &= \frac{\Phi_5(x^7)(x-1)(x^5+1)(x^{10}+1)(x^{20}+1)}{x^{40}-1}\\ &= -(x^{28}+x^{21}+x{14}+x^7+1)(x-1)(x^5+1)(x^{10}+1)(x^{20}+1)\\ &= -(x^{22}-x^{21}+x^{15}-x^{14}+x^8-x^7+x-1)(x^5+1)(x^{10}+1)\\ &= -(x^{22}-x^{21}+x^{20}-x^{19}+x^{15}-x^{14}+x^{13}-x^{12}+x^8-x^7+x^6-x^5+x-1)(x^{10}+1)(x^{20}+1) \\ &= -(-x^{24}+x^{23}-x^{21}+x^{20}-x^{19}+x^{18}-x^{17}+x^{16}-x^{14}+x^{13}-x^{12}+x^{11}-x^{10}+x^8-x^7+x^6-x^5+x-1)(x^{20}+1)\\ &= -(-x^{24}+x^{23}-x^{19}+x^{18}-x^{17}+x^{16}-x^{14}+x^{13}-x^{12}+x^{11}-x^{10}+x^8-x^7+x^6-x^5+x-1)\\ &= x^{24}-x^{23}+x^{19}-x^{18}+x^{17}-x^{16}+x^{14}-x^{13}+x^{12}-x^{11}+x^{10}-x^8+x^7-x^6+x^5-x+1)\end{align}$$ ### c) $\Phi_{40}$ ## McEliece Übung 7-6 Sei $K$ ein Feld der Charakterisitik $2$. Berechne - $\Phi_{10}(x) = \Phi_5(x^{2-1}) = \Phi_5(x) = x^4+x^3+x^2+x+1$ - $\Phi_{12}(x) = \Phi_3(x^{4-2}) = \Phi_3(x^4+x^2+1)$ - $\Phi_{14}(x) = \Phi_7(x) = x^6+x^5+x^4+x^3+x^2+x+1$ - $\Phi_{16}(x) = \Phi_1(x^{16-8}) = x^{8}-1$ y [[lit_mcelieceFiniteFieldsComputer2012]] [^1]: Gerkmann - Lemma 13.4