Kryptologie Der globale Koinzidenzindex eines Textes

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

Definition

Sei a ∈ Σ^r ein Text (mit r ≥ 2) und κ₁(a), ..., κ_r-1(a) die Folge der Autokoinzidenzindizes. Dann heißt der Mittelwert

φ(a) := [κ₁(a) + ... + κ_r-1(a)] / [r - 1]

Dadurch ist also eine Abbildung

φ : Σ^(≥2) → Q

Andere Beschreibung

Wie oft findet man, wenn man zwei beliebige Stellen des Textes a herauspickt, ein »Zwillingspaar«, also zweimal den gleichen Buchstaben s ∈ Σ? (= eine »Koinzidenz«)

Sei h_s = #{j | a_j = s} die Häufigkeit von s in a. Dann ist die Antwort:

h_s×(h_s-1)/2 -mal.

Insgesamt ist die Anzahl der Zwillingspaare also

Man kann diese Koinzidenzen (= Zwillingspaare) auch anders zählen:

Sei dazu zq die Anzahl der bereits gefundenen Koinzidenzen im Abstand q für q = 1, ..., r-1, initialisiert mit zq := 0.
Für i = 0, ..., r-2				[Zählschleife über den Text a]
	für j = i+1, ..., r-1			[Zählschleife über den Resttext]
		falls ai = aj		[Koinzidenz gefunden]
			inkrementiere zj-i	[im Abstand j-i]
			inkrementiere zr+i-j	[und im Abstand r+i-j]

Genauso wurde übrigens in dem Perl-Programm gezählt.

Am Ende der Schleife enthalten z₁, ..., z_r-1 Werte, für die gilt:

Hilfssatz. (i) z1 + ... + zr-1 = Σs∈Σ hs×(hs-1). (ii) κq(a) = zq/r    für   q = 1, ..., r-1.

Beweis. (i) Alle Koinzidenzen sind doppelt gezählt.

(ii) κ_q(a) = (1/r) × #{j | a_j+q = a_j} nach Definition (Indizes mod r).♦

Satz (Kappa-Phi-Theorem) Der Koinzidenzindex eines Textes a ∈ Σ* (der Länge r ≥ 2) ist der Anteil der Koinzidenzen unter allen Buchstabenpaaren von a.

Beweis.

Korollar 1.

Beweis. Das folgt aus dem Zwischenschritt

Korollar 2 (Invarianzsatz 2) Der Koinzidenzindex eines Textes ist invariant unter monoalphabetischer Substitution und unter Transposition.

Beweis. Die Anzahl der Zwillingspaare ändert sich nicht.♦

Im Beispiel des (deutschen) Rheingedichts war φ(a) ≈ 0.0715, beim (englischen) »If ...« φ(c) ≈ 0.0623. Diese Werte entsprechen der Erwartung, da sie ja als Mittelwerte der Autokoinzidenzindizes selbst den typischen Wert der Zeichenkoinzidenz zweier Texte der gleichen Sprache annehmen sollten.

Im Beispiel des analysierten Geheimtextes war φ(c) ≈ 0.0440. Auch dies ist ein typischer Wert, den wir bald verstehen werden.