[Folie 1]
Wir haben gestern gesehen, dass X^2+X+1 ein geeignetes irreduzibles, primitives Polynom ist, um bei einem LFSR der Länge 2 die maximale Periode zu erhalten. Bevor wir uns um Grad 3 und 4 kümmern, halten wir fest, dass es das einzige in Frage kommende Polynom vom Grad 2 ist.
Reduzibel sind nämlich die drei anderen:
X^2=X*X, X^2+X=X(X+1), X^2+1=(X+1)*(X+1) <- bitte nachrechnen
Sind das wirklich die drei einzigen, die noch übrig bleiben? Ja. Denn X^2 steht als Term fest, damit es vom Grad 2 ist. Für die anderen beiden Koeffizienten gibt es die Möglichkeiten 0 und 1. Also zwei Möglichkeiten für jeden Koeffizient, macht zusammen 2*2 Möglichkeiten für alle Polynome vom Grad 2.
[Folie 2]
Bei Grad 3 steht X^3 als Term fest und es gibt 2*2*2=8 Möglichkeiten für Grad-3-Polynome insgesamt. Wir schließen die aus, bei denen der konstante Term =0 ist. Bei diesen kann man nämlich X ausklammern und hat eine Zerlegung. Das ist die Hälfte, also bleiben vier übrig. Diese stehen auf der Folie. Sowohl X^3+1 als auch X^3+X^2+X+1 haben X=1 als Nullstelle. Also muss deren Darstellung nach Polynomdivision von der Form
(X+1)*(X^2+...)
sein, also reduzibel.
Es bleiben die beiden X^3+X+1 und X^3+X^2+1 übrig.
Bleibt noch zu klären, ob diese primitiv sind.
Für X^3+X+1 ist es auf der Folie gezeigt.
Für X^3+X^2+1 bitte als Übung nachrechnen.
Es gibt eine Formel für die Anzahl primitiver Polynome, diese ergibt für den Fall n=3, dass es zwei sind, also haben wir alle gefunden.
Wir wenden uns Grad 4 zu.
Wir schließen wieder die mit konstantem Term 0 aus.
Wir schließen auch die mit einer geraden Anzahl von Termen aus. Dort kann man nämlich X=1 einsetzen und sieht, dass X=1 eine Nullstelle ist, also zerlegbar als (X+1)*(X^3+...)
Es bleiben die vier gezeigten übrig.
Die mit Nullstellen haben wir schon ausgeschlossen, also kann eine Zerlegung eines solchen Polynoms vom Grad vier nur die Zerlegung in zwei irreduzible Polynome vom Grad 2. Es gibt aber nur ein irreduzibles Polynome vom Grad 2, nämlich wie oben gesehen: X^2+X+1.
Die einzig mögliche Zerlegung (X^2+X+1)*(X^2+X+1) ergibt das Polynom X^4+X^2+1. Also sind die übrig bleibenden X^4+X+1, X^4+X^3+1, X^4+X^3+X^2+X+1 alle irreduzibel.
Wir prüfen nun noch Primitivität mit den Teilern von 2^4-1, also X^3 und X^5 dürfen beide nicht =1 sein. Das ist der Fall für X^4+X+1, X^4+X^3+1, aber nicht für X^4+X^3+X^2+X+1 . Also ist X^4+X^3+X^2+X+1 das irreduzible, aber nicht primitive Polynom kleinsten Grades.
[Folie 3]
Das durch LFSRs auf der Hand liegende Design für Stromchiffren ist hier gezeigt. Man kombiniere LFSRs. Diese müssen unterschiedliche Länge haben, damit die Perioden unterschiedlich sind. Da LFSRs algebraisch alle analysierbar sind, muss die Combiner-Funktion f() ein nicht-lineares Aussehen haben. Was bedeutet in diesem Zusammenhang nicht-linear?
Nun, es müssen zwei verschiedene Variablen miteinander multipliziert werden. Das ist hier im Beispiel in rot mit Grad 2 markiert.
Eine andere Möglichkeiten sind nicht-lineare Schieberegister (NFSR=nonlinear-feedback-shift-register). Also Einträge werden nicht nur addiert, sondern auch multipliziert.