Faktorisierung von Kreisteilungspolynomen in endlichen Körpern

Beschreibung

Das Kreisteilungspolynom ist in seinem normalen Umfeld, das heißt in $\mathbb{R}$ ein Irreduzibles Polynom. In endlichen Körpern ist das aber nicht zwingend der Fall.

Sätze

Faktorisierung 1

Sei $f(x)$ ein normiertes Polynom von Grad $n$ mit Koeffizienten aus ${\text{F}}_q$. Sei $h(x)$ ein ${\text{F}}_p$-Polynom mit der Eigenschaften $h(x{)}^q\equiv h(x)\mathrm{mod}f(x)$, dann lässt sich $f(x)$ folgendermaßen faktorisieren: $f(x)={\prod }_{s\in {\text{F}}_q}ggT(f(x),h(x)-s)$¹

Anzahl der Faktoren

Die Zahl der Faktoren ist gleich der Dimension von $R(f)$, wobei $R(f)$ der Vektorraum aller Polynome $h(x)\mathrm{mod}f$ mit der Eigenschaft $h^q\equiv h\mathrm{mod}f$.

Die Dimension (Vektorraum) berechnet man, indem man ein Gleichungssystem (Lineare Algebra) aufstellt, bei dem die Koeffizienten von $h$ die Unbekennten sind. Die Lösungen des Gleichungssystems sollen die Polynomkoeffizienten sein, sodass $h$ die obere Konguenz erfüllt. Dieses Gleichungssystem hat nach den Erkenntnissen der linearen Algebra einen Vektorraum als Lösungsraum. Das ist genau $R(f)$. Die Dimension eines Lösungsraumes zu bestimmen sollte nicht allzu schwer sein.²

Faktorisierung 2

Ein Polynom $h(x)={\sum }_{i=0}^{n-1}{h}_i{x}^i\in {\text{F}}_q[x]$ erfüllt die Kongruenz $h^q\equiv h\mathrm{mod}{x}^n-1$ genau dann, wenn alle Koeffizientenindizes eines $q$-Potenzenzykel den gleichen Wert haben, das heißt $h_i=h_{iq}=h_{i{q}^2}=...$ gilt.

Da in ${\text{F}}_q[x]$ Freshmans Dream gilt und $x^i\equiv x^j\mathrm{mod}{x}^n-1⟺i\equiv j\mathrm{mod}n$ muss $h$ eine Linearkombination der Potenzenzykelpolynome der $q$-Potenzenzykel in $\mathbb{Z}athbbZmathbbZ/n\mathbb{Z}athbbZmathbbZ/n\mathbb{Z}$ sein Ein Potenzzykelpolynom ist ein Polynom mit der Form: $x^a+x^{aq}+x^{a{q}^2}+...$ (Man erkennt durch Anwendung von Freshmans Dream, das das Polynom $h^3\equiv h\mathrm{mod}{x}^n-1$ erfüllt)

Beispiele

Potenzzykelpolynome $\mathrm{mod}{x}^{20}-1$

Jedes Polynom $h$ mit der Eigenschaft $h^3\equiv h\mathrm{mod}{x}^{20}-1$ ist eine Linearkombination der Polyome:

• $1$
• $x+x^3+x^7+x^9$
• $x^2+x^6+x^{18}+x^{14}$
• $x^4+x^{12}+x^{16}+x^8$
• $x^5+x^{15}$
• $x^{10}$
• $x^{11}+x^{13}+x^{17}+x^{19}$

Übungen

McEiliece Übung 7-4

Faktorisiere die folgenden Kreisteilungspolynome in den endlichen Körpern:

• ${\Phi }_{17}(x)$ über $GF(2)$
• ${\Phi }_{11}(x)$ über $GF(3)$ ${\Phi }_{11}(x)=(x^5+x^4-x^3+x^2-1)(x^5-x^3+x^2-x-1)$
• ${\Phi }_{13}(x)$ über $GF(5)$ ${\Phi }_{15}(x)=(x^4+3x^3+3x+1)(x^4+x^3+4x^2+x+1)(x^4+2x^3+x^2+2x+1)$
• ${\Phi }_{19}(x)$ über $GF(7)$ \Phi_{19}(x) = (x^3+3x^2+3x+6)(x^4+4x^2+4x+6)(3x^3+4x^2+2x+4)$$(4x^3+2x^3+3x+3)(x^3+5x^2+6)(3x^3+6x+4)³

McEliece Übung 7-7

Faktorisiere $x^{16}-x$ über folgende Körper:

• ${\text{F}}_{16}$ Das sind genau die Elemente des oberen Körpers, das Polynom zerfällt also in Linearfaktoren
• ${\text{F}}_2$ Das sind genau die Elemente des Körpers ${\text{F}}_{16}$. Das Polynom zerfällt daher in die Minimalpolynome dieser Elemente, die ich zufällig bereits berechnet habe. $x^{16}-x=x(x-1)(x^2+x+1)(x^4+x+1)(x^4+x^3+1)(x^4+x^3+x^2+x+1)$
• ${\text{F}}_4$ Zufälligerweise habe ich das auch schon in 2022 Algebraischer Abschluss von F2 berechnet. Das sind einfach die Polynome von oben aber die Polynome von Grad $2$ und $4$ zerfallen noch weiter.

\newcommand{\R}{\mathbb R}

lit_mcelieceFiniteFieldsComputer2012

Footnotes

1. McEliece - Theorem 7.3 ↩

2. McEilece - Theorem 7.4 ↩

3. 1 ↩