Diskrepanzberechnungen für bestimmte Folgen durch Anwendung der Theorie der Gleichverteilung modulo Eins

Abstract

Das Thema dieser Diplomarbeit war eine effiziente Berechnung der exakten Diskrepanz von rellen Zahlenfolgen sowie auch die Berechnung von oberen Abschätzungen dieser Größe. Für diesen Zweck wurden grundlegende Resultate der Theorie der Gleichverteilung modulo Eins, sowie der Kryptographie angewendet. Bei der Diskrepanzberechnung war die Cordes-Folge von besonderem Interesse. Diese wurde mit einem, sich aktuell noch in Entwicklung befindlichen, Stromverschlüsselungsverfahren namens LDU erzeugt. Die Diskrepanz der Cordes-Folge kann als Maß für die Güte deren Gleichverteilung betrachtet werden. Je niedriger der Wert der Diskrepanz einer Folge, umso besser ist diese gleichverteilt. Das Ergebnis der Untersuchungen ist, dass die Diskrepanz der Cordes-Folge größer ist als die Diskrepanz einer bestimmten nicht gleichverteilten Folge. Das legt die Vermutung nahe, dass die Cordes-Folge ebenfalls keine modulo Eins gleichverteilte Folge ist. Dieses Resultat für die Cordes-Folge bedeutet aber nicht, dass das LDU-Verfahren kryptologisch schwach ist.<br />Für die Abschätzung der oberen Grenze der Diskrepanz einer Zahlenfolge wurde die Ungleichung von Erdös-Turan angewendet. Dabei hängt die Schärfe dieser Ungleichung von einem ganzzahligen Parameter H ab. Es konnte gezeigt werden, dass für alle Zahlenfolgen ein eindeutiges H* existiert, für welches die besagte Abschätzung am genausten ist.<br />Basierend auf diesem Ergebnis wurden auch die, in MATLAB implementierten, Algorithmen zur Berechnung der Diskrepanzabschätzungen optimiert.<br />

The topic of this diploma thesis was the efficient computation of the actual discrepancy and of upper bound estimates of sequences of real numbers. For this purpose both fundamental results concerning the theory of equidistribution modulo one and of cryptology have been applied. In that respect the discrepancy of the Cordes-sequence was of particular interest. This special sequence was created by means of a stream cipher called LDU. This cipher is currently being developed and enhanced by Michael Cordes and his team. The discrepancy of the Cordes-sequence can be regarded as a measure for the quality of its equidistribution. The result of this thesis is that the discrepancy of the Cordes-sequence is higher than the discrepancy of a certain sequence which is known for not being equidistributed modulo one. Therefore one could also assume that the Cordes-sequence is not equidistributed modulo one. Otherwise, this result does not necessarily indicate that the LDU-algorithm is a cryptologically weak method.<br />For the estimation of the upper bound of the discrepancy of real sequences the inequality of Erdös-Turaan has been used. This inequality depends on an integral parameter H. It was shown, that for any sequence of real numbers there exits a unique H* for which the estimation takes its minimum value. Based on these result, efficient algorithms for the computation of upper bounds for the discrepancy have been implemented.