Primitives Polynom bestimmen

19.02.2017, 18:38

xvzwx

Primitives Polynom bestimmen

Hallo,

ich beschäftige mich momentan mit linear rückgekoppleten Schieberegistern (kurz engl. LFSR). Diese können einfach als Polynom dargestellt werden.

Ein Theorem besagt:
Ein LFSR erzeugt dann eine Sequenz mit maximaler Periodizität, wenn sein Generatorpolynom primitiv ist.

Anmerkung: Bei den Polynomen handelt es sich immer um Polynom aus dem Körper $\begin{eqnarray*} \mathbb F_{2}[x] \end{eqnarray*}$

Jetzt habe ich gelesen, dass ein primitves Polynom immer irreduzibel ist. Aber ich gehe mal davon aus das ein irreduzibles Polynom nicht automatisch primitv ist, da es sich sonst um identische Aussagen handeln würde.

Als Beispiel hätte ich folgendes Polynom:
$\begin{eqnarray*} p(x) = x^{4} + x^{3} + x^{2} + x + 1 \end{eqnarray*}$

Ich weiß das die Periodizität der Sequenz nicht maximal ( $\begin{eqnarray*} 2^{deg(p(x))}-1 = 2^{4}-1 = 7 \end{eqnarray*}$ ) sonder lediglich $\begin{eqnarray*} 5 \end{eqnarray*}$ beträgt.

Für dieses Polynom konnte ich jedoch keine NST also auch keine Faktorisierung finden. Dieses Polynom wäre also irreduzibel, jedoch nicht primitv, da es sonst eine maximal Periodizität erzeugen würde.

Nun zu meiner eigentliche Frage
Wie kann ich zeigen das ein irreduzibles Polynom primitv oder eben nicht primitiv ist?

19.02.2017, 19:46

Elvis

Auf diesen Beitrag antworten »

p(x) ist irreduzibel, aber nicht, weil es keine Nullstellen in $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ hat, sondern weil es keine linearen oder quadratischen Teiler in $\begin{eqnarray*} \mathbb F_2[x] \end{eqnarray*}$ hat. p(x) ist nicht primitiv, weil seine Nullstelle kein erzeugendes Element von $\begin{eqnarray*} \mathbb F_{16}^* \end{eqnarray*}$ ist: $\begin{eqnarray*} \theta^5=1 \end{eqnarray*}$ (Das ist im allgemeinen nicht leicht zu zeigen. Mir ist kein Verfahren bekannt außer Potenzen berechnen, und das ist mühsam.) Übrigens ist der Grad von p(x) gleich 4, also die multiplikative Gruppe nicht von der Ordnung 7 sondern von der Ordnung 15.

19.02.2017, 20:14

xvzwx

Auf diesen Beitrag antworten »

Danke für die schnelle Antwort. Freude

Oh, da hat sich wohl ein Fehler eingeschlichen, richtig müsste es natürlich:
$\begin{eqnarray*} 2^{deg(p(x))}-1 = 2^{4} - 1 = 15 \end{eqnarray*}$
heißen! Hammer

Zitat:

p(x) ist nicht primitiv, weil seine Nullstelle kein erzeugendes Element von $\begin{eqnarray*} \mathbb F_{16}^* \end{eqnarray*}$ ist: $\begin{eqnarray*} \theta^5=1 \end{eqnarray*}$

Leider konnte ich diesen Teil nicht ganz nachvollziehen.
Wie kommen Sie auf $\begin{eqnarray*} \mathbb F_{16}^* \end{eqnarray*}$ ? Und was ist mit $\begin{eqnarray*} \theta^5=1 \end{eqnarray*}$ gemeint?

20.02.2017, 09:05

Elvis

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \theta \end{eqnarray*}$ ist eine Nullstelle des Polynoms $\begin{eqnarray*} p(x)=x^4+x^3+x^2+x+1 \end{eqnarray*}$ , also ist $\begin{eqnarray*} \theta ^4+\theta^3+\theta^2+\theta+1=0 \end{eqnarray*}$ , und wegen $\begin{eqnarray*} 1+1=0 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ ist $\begin{eqnarray*} -1=1 \end{eqnarray*}$ in $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ , daher gilt $\begin{eqnarray*} \theta ^4=-\theta^3-\theta^2-\theta-1=\theta^3+\theta^2+\theta+1 \end{eqnarray*}$ , also $\begin{eqnarray*} \theta^5 = ( \theta^4) + (\theta^3 + \theta^2 + \theta ) = ( \theta^3 + \theta^2 + \theta + 1 ) + ( \theta^3 + \theta^2 + \theta ) = 2 \theta ^3 + 2\theta^2+2\theta +1= 1 \end{eqnarray*}$
(Das ist das etwas mühsame Verfahren, das ich kenne. Man berechnet Potenzen von $\begin{eqnarray*} \theta \end{eqnarray*}$ so lange, bis man die 1 erhält.)

Wo soll $\begin{eqnarray*} \theta \end{eqnarray*}$ liegen, wenn nicht im Zerfällungskörper von $\begin{eqnarray*} p(x)\in \mathbb F_2[x] \end{eqnarray*}$ , also in $\begin{eqnarray*} \mathbb F_2[x]/(p(x))=\mathbb F_{16} \end{eqnarray*}$ ? Beachte $\begin{eqnarray*} grad(p(x))=4 \end{eqnarray*}$ und $\begin{eqnarray*} p(x) \end{eqnarray*}$ irreduzibel. Und $\begin{eqnarray*} p(x) \end{eqnarray*}$ ist genau dann ein primitives Polynom, wenn $\begin{eqnarray*} \theta \end{eqnarray*}$ ein primitives Element der multiplikativen Gruppe $\begin{eqnarray*} \mathbb F_{16}^* \end{eqnarray*}$ ist, also die Ordnung $\begin{eqnarray*} 2^4-1=16-1=15 \end{eqnarray*}$ hat . Das ist aber nicht so, $\begin{eqnarray*} \theta \end{eqnarray*}$ hat die Ordnung 5, erzeugt also nicht diese multiplikative Gruppe.

Primitive Polynome vom Grad 4 über $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ sind $\begin{eqnarray*} x^4+x+1 \end{eqnarray*}$ und $\begin{eqnarray*} x^4+x^3+1 \end{eqnarray*}$ (das sind auch die einzigen, wie du jetzt "leicht" nachrechnen kannst) . Wenn du nicht rechnen möchtest und Wolfram vertraust, dann siehe hier: http://mathworld.wolfram.com/PrimitivePolynomial.html

20.02.2017, 16:02

xvzwx

Auf diesen Beitrag antworten »

Wow, vielen Dank für diese ausführliche Antwort Freude

20.02.2017, 18:31

Elvis

Auf diesen Beitrag antworten »

Das war mir ein Vergnügen. Bei gut formulierten Frage gebe ich gern gut formulierte Antworten. Ab und zu muss man sich so etwas auch mal wieder selbst zurecht legen, dann bleibt es besser im Gedächtnis.

Neue Frage »

Antworten »

Primitives Polynom bestimmen

Verwandte Themen