Kryptologie Die mittlere Zeichenkoinzidenz zweier stochastischer Sprachen

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

Für stochastische Sprachen L, M ⊆ Σ^* mit Buchstabenhäufigkeiten q_s bzw. p_s für s ∈ Σ wird die mittlere Zeichenkoinzidenz von Texten der Länge r betrachtet:

Satz. Die mittlere Zeichenkoinzidenz der stochastischen Sprachen L und M ist asymptotisch gleich

Der Beweis folgt unten.

Deutung

Die Zeichenkoinzidenz genügend langer gleichlanger Texte a ∈ L und b ∈ M ist ungefähr

Spezialfälle

1.) Sei L = Σ^* mit den Buchstabenhäufigkeiten q_s = 1/n, und M habe die Buchstabenhäufigkeiten p_s. Dann ist

κ_MΣ^* = ∑_s∈Σ p_s/n = 1/n.

κ(»sinnvoller Text«, »zufälliger Text«) ≈ 1/n.

2.) Sei L = M. Dann erhält man die Formel

κ_MM = ∑_s∈Σ p_s².

κ(»sinnvoller Text«, »sinnvoller Text«) ≈ ∑_s∈Σ p_s².

3.) Sei L = M_(q) = {a_(q) | a ∈ M} ⊆ Σ^*; L besteht also aus den um q Stellen zyklisch verschobenen Texten. Dann ist mit M auch L stochastisch, und zwar mit den gleichen Buchstabenhäufigkeiten. Also ist

κ_LM = ∑_s∈Σ p_s².

κ_q(a) ≈ ∑_s∈Σ p_s².

Ein Hilfssatz

Hilfssatz. Sei M eine stochastische Sprache. Dann gilt für die mittlere Abweichung für alle Buchstaben s ∈ Σ:

Beweis. Sei ε > 0 gegeben und r so groß, dass

a) r ≥ 4 × #J/ε,

b) |μ_sj^(r) - p_s| < ε/2 für alle j ∈ [0 … r]-J.

♦

Bemerkung.

Korollar. limr→∞ μs(r) = ps.

Der Beweis des Satzes

Der zweite und dritte Summand konvergieren nach dem Hilfssatz gegen 0, der vierte konvergiert ebenfalls gegen 0, da |ε_sjη_sj| ≤ 1. Also konvergiert die Summe gegen ∑_s∈Σ p_sq_s.♦