Titelaufnahme

Titel
Asymptotic analysis of sequences defined by automata / Sara Kropf
VerfasserKropf, Sara
Begutachter / BegutachterinHeuberger, Clemens ; Wagner, Stephan
ErschienenKlagenfurt, Juni 2015
Umfangv, 138 Seiten : Diagramme
HochschulschriftAlpen Adria Universität Klagenfurt, Dissertation, 2015
Anmerkung
Zusammenfassung in deutscher Sprache
SpracheEnglisch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)zentraler Grenzwertsatz / periodische Fluktuation / Fourier Koeffizient / Nicht-Differenzierbarkeit / Automat / Transducer / Hamminggewicht / Überträge / von Neumann Addition / Markovkette
Schlagwörter (EN)central limit theorem / periodic fluctuation / Fourier coefficient / non-differentiability / automaton / transducer / Hamming weight / carry / von Neumanns addition / Markov chain
URNurn:nbn:at:at-ubk:1-23632 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Asymptotic analysis of sequences defined by automata [1.69 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

In der Kryptographie ist Skalarmultiplikation mit groÃen Zahlen eine hÃ$ufig verwendete Operation. Diese wird oft unter Verwendung von Ziffernentwicklungen implementiert. Die Wahl der Ziffernentwicklung beeinflusst die Laufzeit der Skalarmultiplikation. Deshalb bietet sie eine MÃglichkeit, den kryptographischen Algorithmus zu optimieren und dadurch das Sicherheitsniveau zu erhÃhen. Genauer gesagt wird die Laufzeit der Skalarmultiplikation von der GrÃÃe von bestimmten Parametern der Ziffernentwicklung beeinflusst. Beispiele fÃr solche Parameter sind die Ziffernsumme und das Hamminggewicht. Um genaue Angaben zur Laufzeit eines Algorithmus zu geben, ist eine genaue asymptotische Analyse dieser Parameter notwendig. Solche Parameter von syntaktisch definierten Ziffernentwicklungen kÃnnen als Outputsumme von endlichen Zustandsautomaten berechnet werden. In dieser Dissertation werden solche Outputsummen asymptotisch analysiert. Die Resultate geben Auskunft Ãber den Erwartungswert, die Varianz und die Kovarianz von Folgen, welche als Outputsumme von Automaten definiert sind. Auch zentrale GrenzwertsÃ$tze werden bewiesen. Dabei sind bei den Momenten nicht nur die Hauptterme von Interesse, sondern auch die Terme zweiter Ordnung, die im Allgemeinen durch stetige, nirgends differenzierbare, periodische Funktionen gegeben sind. Die Fourierkoeffizienten dieser Funktionen werden ebenfalls bestimmt. Beispiele fÃr Folgen, welche als Outputsumme von endlichen Automaten definiert werden kÃnnen, sind q-additive Funktionen, Block-q-additive Funktionen, sowie Ziffernsumme und Hamminggewicht von syntaktisch definierten Ziffernentwicklungen. Deshalb verallgemeinern die Resultate dieser Arbeit viele bekannte Tatsachen Ãber das asymptotische Verhalten dieser Folgen. Weiters kÃnnen spezielle Rekursionen auch von Automaten berechnet und damit asymptotisch analysiert werden. Im Allgemeinen ist die Outputsumme eines Automaten asymptotisch normal verteilt. Allerdings ist das nicht immer der Fall: Es kann auch der Fall eintreten, dass die Outputsumme eine degenerierte Zufallsvariable ist. Dieser Fall wird in dieser Dissertation algebraisch und kombinatorisch charakterisiert. Dabei stellt sich heraus, dass die Bedingungen fÃr diesen Fall anhand der Darstellung des Automaten als Graph einfach ÃberprÃft werden kÃnnen. Die Resultate dieser Arbeit werden auf mehrere Folgen angewandt, um neue asymptotische Ergebnisse zu erhalten. Eine dieser Folgen besteht aus den ÉbertrÃ$gen, die im Laufe einer schriftlichen Addition auftreten. Dabei sind beide Summanden in einer syntaktisch definierten Ziffernentwicklung gegeben. Auch die Anzahl der Iterationen der Von-Neumann-Addition wird mit Hilfe von Automaten asymptotisch analysiert. Das ist ein Beispiel einer asymptotisch nicht normal verteilten Folge: Die Anzahl der Iterationen konvergiert zu einer Gumbel-Verteilung. Die einzelnen Schritte der asymptotischen Analyse kÃnnen automatisiert werden: Von der konkreten Konstruktion der Automaten bis zur Berechnung der Fourierkoeffizienten kÃnnen die einzelnen Teile im mathematischen Softwaresystem Sage durchgefÃhrt werden. Dazu wird in dieser Arbeit das Automatenpaket prÃ$sentiert, welches im Rahmen dieser Dissertation implementiert wurde. Mittlerweile ist dieses Paket ein integraler Bestandteil von Sage. Die Idee dieses Pakets ist es, praktische Funktionen zu bieten, um mit Automaten zu arbeiten. Deshalb sind auch alle Resultate dieser Dissertation Teil dieses Pakets, und illustrierenden Beispiele wurden mit Hilfe dieses Pakets berechnet.

Zusammenfassung (Englisch)

In cryptography, scalar multiplication with large numbers is a frequently used operation. It is usually implemented using a digit representation of the scalar. The choice of the representation influences the running time of this scalar multiplication. Thus it is one possibility to optimize cryptographic algorithms and increase the security level. More specifically, the running time of the multiplication depends on certain parameters of the digit representation. Such parameters can be the sum of digits, or the number of non-zero digits. To give precise estimates of the running time of an algorithm, a precise asymptotic analysis of these parameters of the chosen digit representation is of interest. For syntactically defined digit representations, these parameters can be computed as the output sum of finite state machines. In this thesis, the output sum of an arbitrary finite state machine is analyzed asymptotically. This includes expectation, variance, covariance and central limit theorem for a sequence defined as the output sum of a finite state machine. For the moments, not only the main terms are provided, but also the existence of a continuous, nowhere differentiable, periodic function as the second order term is proved and a formula for the coefficients of its Fourier series is given. This setting of sequences which can be defined as the output sum of finite state machines includes many well-studied sequences, like q-additive functions, digital sequences and the sum-of-digits function and the Hamming weight of syntactically defined digit representations. Thus, the results in this work generalize well known facts about the asymptotic behavior of all these sequences. Also, sequences defined by certain recursions fit into this setting. The output sum of a finite state machine is in general asymptotically normally distributed. However, this is not guaranteed: It may happen that the output sum degenerates. In this work, this case is characterized algebraically and combinatorially. It turns out that this degeneration only happens in trivial cases and the conditions can be checked easily by inspecting a representation of the finite state machine as a graph. These results are applied to asymptotically analyze several sequences in this thesis. This includes the sequence of carries occurring when performing addition of two numbers given in a syntactically defined digit representation. Furthermore, the number of iterations of von Neumann's addition algorithm is analyzed by using automata. However, this number of iterations is not asymptotically normally distributed, but converges to a double exponential distribution. All the steps to obtain an asymptotic analysis of a given sequence, starting with explicitly constructing the corresponding finite state machine and stopping finally with the computation of the Fourier coefficients, can be performed automatically in the mathematical software system Sage. To do this, the new finite state machine package, developed in the framework of this thesis, is presented. In the meanwhile, this package is included in the mathematical software system Sage. This package was developed to conveniently work with automata and transducers. Thus, all results of this thesis are implemented as methods of this finite state machine package and the examples are computed by using them accordingly.

Statistik
Das PDF-Dokument wurde 16 mal heruntergeladen.