[JoGu]

Kryptologie

Perioden von Zustandsänderungen
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

Gegeben sei eine endliche Menge M (statt Σq im Beispiel einer Rotor-Maschine) mit m = #M (statt nq) und eine Abbildung

g: M → M.
Zu jedem Startwert (»Anfangszustand«) x0∈M wird durch die einstufige Rekursionsformel xi = g(xi-1) für i ≥ 1 eine Folge (xi)i∈N in M erzeugt. Diese mündet nach einer Vorperiode der Länge μ in eine periodische Folge der Länge λ:

[Periode]

Wegen der Endlichkeit von M gibt es nämlich kleinste Zahlen μ ≥ 0 und λ ≥ 1 mit xμ+λ = xμ.

Dann gilt auch

xi+λ = xi     für i ≥ μ.
Natürlich ist stets 0 ≤ μ ≤ m - 1, 1 ≤ λ ≤ m, λ + μ ≤ m.

Bezeichnungen: μ heißt Vorperiode(nlänge), λ heißt Periode(nlänge).

Autor: Klaus Pommerening, 31. Dezember 1999; letzte Änderung: 1. Januar 2008.