Primitives Polynom

Primitives Polynom

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

In der Ringtheorie wird der Begriff primitives Polynom anders verwendet. Hier ist es ein Polynom über einem faktoriellem Ring (z.B die Ganze Zahlen), dessen größter gemeinsamer Teiler seiner Koeffizienten eine Einheit ist. Dieser Artikel befasst sich nicht mit der Verwendung in der Ringtheorie. Siehe dazu Inhalt eines Polynoms.

Inhaltsverzeichnis

Eigenschaften

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

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

Ein Irreduzibles Polynom F(x) des Grades m über GF(p) für eine Primzahl p ist ein primitives Polynom, wenn pm − 1 die kleinste ganze Zahl n ist, für die F(x) ein Teiler von xn − 1 ist.

Über dem Körper GF(pm) gibt es genau \frac{\varphi(p^m - 1)}{m} primitive Polynome des Grades m, wobei ϕ die Eulersche φ-Funktion ist.

Die Nullstellen eines primitiven Polynoms habe alle die Ordnung pm − 1.

Anwendungen

Darstellung von Körper-Elementen

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


\mathrm{GF}(p^m) = \{ 0, 1, \alpha, \alpha^2, \ldots, \alpha^{p^m-2} \} .

Wenn diese Elemente modulo 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 das primitives Polynom f(x) x ein Generator der multiplikativen Gruppe in GF(p)[x]/f(x) ist.

Erzeugung von Pseudo-Zufallszahlen

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

Sei z.B. ein primitives Polynom x10 + x3 + 1 gegeben. Man beginnt mit einer benutzerdefinierten Saatzahl (diese 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 210−1 = 1023 Pseudo-Zufalls-Bits zu erzeugen.

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

Primitive Trinome

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, für das 2r−1 eine Mersenne-Primzahl ist, ist ein Trinom des Grades r primitiv, genau dann wenn es irreduzierbar 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. x6972593 + x3037958 + 1. Damit können Pseuodzufallsgeneratoren mit einer riesigen Periode von 26972593−1, oder ca. 102098959 erzeugt werden.[1]

Literatur

  • Elwyn R. Berlekamp: Algebraic Coding Theory, Revised Edition. 2. Auflage. Aegean Park Press, 1984, ISBN 0-89412063-8.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Primitives Element — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen …   Deutsch Wikipedia

  • Allgemeiner Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonacci-Generator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonacci-Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonaccigenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Fibonaccikongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Gemischter linearer Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Linearer Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Multiplikativer Kongruenzgenerator — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

  • Satz von Knuth — Die Kongruenzgeneratoren bilden eine Klasse von Algorithmen, die zufällig aussehende Zahlenfolgen erzeugen. Die dadurch erzeugten Zahlen nennt man Pseudozufallszahlen, da sie deterministisch erzeugt werden und somit nicht wirklich zufällig sind.… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”