Primitives Polynom

In der Theorie mathematischer Körper ist ein primitives Polynom das Minimalpolynom einer primitiven ( p m − 1 ) {\displaystyle (p^{m}-1)} -ten Einheitswurzel einer Körpererweiterung G F ( p m ) {\displaystyle \mathrm {GF} (p^{m})} über G F ( p ) {\displaystyle \mathrm {GF} (p)} endlicher Körper. Anders ausgedrückt ist ein Polynom F ( X ) {\displaystyle F(X)} mit den Koeffizienten aus G F ( p ) = Z / p Z {\displaystyle \mathrm {GF} (p)=\mathbb {Z} /p\mathbb {Z} } ein primitives Polynom, wenn es eine Nullstelle α {\displaystyle \alpha } in G F ( p m ) {\displaystyle \mathrm {GF} (p^{m})} hat, so dass die Menge { 0 , 1 , α , α 2 , α 3 , … , α p m − 2 } {\displaystyle \{0,1,\alpha ,\alpha ^{2},\alpha ^{3},\dots ,\alpha ^{p^{m}-2}\}} der ganze Körper G F ( p m ) {\displaystyle \mathrm {GF} (p^{m})} ist und außerdem F ( X ) {\displaystyle F(X)} das Polynom mit dem kleinsten Grad mit α {\displaystyle \alpha } als Nullstelle ist.

Da alle Minimalpolynome irreduzibel sind, sind primitive Polynome ebenso irreduzibel.

Ein primitives Polynom muss einen von Null verschiedenen konstanten Term haben, da es andernfalls durch X {\displaystyle X} teilbar wäre. Über einem Körper aus zwei Elementen ist X + 1 {\displaystyle X+1} ein primitives Polynom und alle anderen primitiven Polynome haben eine ungerade Anzahl von Termen, da jedes Polynom modulo 2 mit einer geraden Anzahl von Termen durch x + 1 {\displaystyle x+1} teilbar ist.

Ein irreduzibles Polynom F ( X ) {\displaystyle F(X)} des Grades m {\displaystyle m} über G F ( p ) {\displaystyle \mathrm {GF} (p)} für eine Primzahl p {\displaystyle p} ist ein primitives Polynom, wenn p m − 1 {\displaystyle p^{m}-1} die kleinste ganze Zahl n {\displaystyle n} ist, für die F ( X ) {\displaystyle F(X)} ein Teiler von X n − 1 {\displaystyle X^{n}-1} ist.

Über dem Körper G F ( p m ) {\displaystyle \mathrm {GF} (p^{m})} gibt es genau φ ( p m − 1 ) m {\displaystyle {\tfrac {\varphi (p^{m}-1)}{m}}} primitive Polynome des Grades m {\displaystyle m} , wobei φ {\displaystyle \varphi } die Eulersche φ-Funktion ist.

Die Nullstellen eines primitiven Polynoms haben alle die Ordnung p m − 1 {\displaystyle p^{m}-1} .

Primitive Polynome werden für die Darstellung von Elementen eines endlichen Körpers verwendet. Wenn α ∈ G F ( p m ) {\displaystyle \alpha \in \mathrm {GF} (p^{m})} eine Nullstelle eines primitiven Polynoms F ( X ) {\displaystyle F(X)} ist, dann hat α {\displaystyle \alpha } die Ordnung p m − 1 {\displaystyle p^{m}-1} , das heißt alle Elemente von G F ( p m ) {\displaystyle \mathrm {GF} (p^{m})} können als aufeinanderfolgende Potenzen von α {\displaystyle \alpha } dargestellt werden:

G F ( p m ) = { 0 , 1 , α , α 2 , … , α p m − 2 } . {\displaystyle \mathrm {GF} (p^{m})=\{0,1,\alpha ,\alpha ^{2},\ldots ,\alpha ^{p^{m}-2}\}.}

Wenn diese Elemente modulo F ( X ) {\displaystyle F(X)} reduziert werden, dann bildet die Darstellung als polynomielle Basis aller dieser Elemente einen Körper.

Da die multiplikative Gruppe eines endlichen Körpers immer eine zyklische Gruppe ist, ist für ein primitives Polynom F ( X ) {\displaystyle F(X)} das Element X {\displaystyle X} ein Generator der multiplikativen Gruppe in G F ( p ) [ X ] / ( F ( X ) ) ≅ G F ( p m ) {\displaystyle \mathrm {GF} (p)[X]/(F(X))\cong \mathrm {GF} (p^{m})} .

Primitive Polynome definieren eine wiederkehrende Relation, die verwendet werden kann, um Bits von Pseudozufallszahlen zu erzeugen. Tatsächlich steht jedes linear rückgekoppelte Schieberegister mit maximalem Zyklus (dieser ist 2^{lrsr length} - 1) mit primitiven Polynomen in Beziehung.

Sei z. B. ein primitives Polynom X 10 + X 3 + 1 {\displaystyle X^{10}+X^{3}+1} gegeben. Man beginnt mit einem benutzerdefinierten Startwert (engl. seed, Saatkorn, dieser muss nicht unbedingt zufällig gewählt werden). Man nimmt dann das 10-te, 3-te und 0-te Bit, gezählt vom niederwertigsten Bit, verknüpft diese mit XOR und erhält ein neues Bit. Die Saatzahl wird dann nach links verschoben und das neue Bit wird zum niederwertigsten Bit der Saatzahl. Dies kann wiederholt werden um 2 10 − 1 = 1023 {\displaystyle 2^{10}-1=1023} Pseudo-Zufalls-Bits zu erzeugen. Für eine Maximum Length Sequence sind ganz bestimmte Ausgänge des Schieberegisters erforderlich.^[1]

Allgemein gilt für ein primitives Polynom des Grades m {\displaystyle m} , dass dieser Vorgang 2 m − 1 {\displaystyle 2^{m}-1} Pseudo-Zufallszahlen erzeugt, bevor die Sequenz sich wiederholt.

Primitive Trinome sind primitive Polynome mit nur drei von Null verschiedenen Termen. Die Trinome sind sehr einfach und werden für sehr effiziente Zufallszahlengeneratoren verwendet. Es gibt verschiedene Methoden, um primitive Trinome zu ermitteln und zu prüfen. Ein einfacher Test funktioniert wie folgt: Für jedes r {\displaystyle r} , für das 2 r − 1 {\displaystyle 2^{r}-1} eine Mersenne-Primzahl ist, ist ein Trinom des Grades r {\displaystyle r} primitiv, genau dann wenn es irreduzibel ist. Durch kürzlich von Richard P. Brent entwickelte Algorithmen ist es möglich geworden, primitive Trinome von hohem Grad zu finden, wie z. B. X 6972593 + X 3037958 + 1 {\displaystyle X^{6972593}+X^{3037958}+1} . Damit können Pseudozufallsgeneratoren mit einer riesigen Periode von 2 6972593 − 1 {\displaystyle 2^{6972593}-1} , oder ca. 10 2098959 {\displaystyle 10^{2098959}} erzeugt werden.^[2]

• Elwyn R. Berlekamp: Algebraic Coding Theory, Revised Edition. 2. Auflage. Aegean Park Press, 1984, ISBN 0-89412-063-8. 
• Peterson, W.W., Weldon, E.J., "Error correcting codes", Cambridge, The MIT – Press, 1972
• Anderson, G.C., Finnie, B. W., "Pseudo-random and random test signals", HP Journal 19, Nr. 1,2 1967

• MathWorld entry on primitive polynomial

1. ↑ Tietze/Schenk, "Halbleiter-Schaltungstechnik", 3. Auflage 1976, S.590 ff, in späteren Auflagen nicht mehr beschrieben.
2. ↑ Search for Primitive Trinomials (mod 2).