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 Í S^* mit Buchstabenhäufigkeiten q_s bzw. p_s für s Î 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 = S^* mit den Buchstabenhäufigkeiten q_s = 1/n, und M habe die Buchstabenhäufigkeiten p_s. Dann ist

k_MS^* = S_sÎS p_s/n = 1/n.

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

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

k_MM = S_sÎS p_s².

k(»sinnvoller Text«, »sinnvoller Text«) » S_sÎS p_s².

3.) Sei L = M_(q) = {a_(q) | a Î M} Í S^*; 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

k_LM = S_sÎS p_s².

k_q(a) » S_sÎS p_s².

Ein Hilfssatz

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

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

a) r ³ 4 × #J/e,

b) |m_sj^(r) - p_s| < e/2 für alle j Î [0 ¼ r]-J.

¨

Bemerkung.

Korollar. limr®¥ ms(r) = ps.

Der Beweis des Satzes

Der zweite und dritte Summand konvergieren nach dem Hilfssatz gegen 0, der vierte konvergiert ebenfalls gegen 0, da |e_sjh_sj| £ 1. Also konvergiert die Summe gegen S_sÎS p_sq_s.¨