FWF - Analysis Extremal Discrete Structu - Asymptotische Analyse extremaler diskreter Strukturen

Strukturen oder Algorithmen zu optimieren, ist in verschiedenen Bereichen der Mathematik und ihrer Anwendungen von Bedeutung. Dabei sind nicht nur die Lösungen selbst von Interesse, sondern auch ihr qualitatives und quantitatives Verhalten für große Parameterwerte, wodurch ein besseres Verständnis ihrer Eigenschaften sowie ein Vergleich mit anderen Ansätzen und Strategien ermöglicht wird. Dies erfordert jedoch eine genaue asymptotische und probabilistische Analyse diskreter Strukturen und Algorithmen. In diesem Kontext interessieren wir uns besonders für mathematische Probleme aus der Graphentheorie und aus Anwendungen in der Kryptographie. In den vergangenen Jahrzehnten wurde eine Reihe von unterschiedlichen graphentheoretischen Indices intensiv untersucht. Ein Grund hierfür ist, dass Moleküle als ungerichtete Graphen dargestellt werden können und gewisse physikochemische Eigenschaften von der Struktur dieser Graphen abhängen, was sich wiederum in den Werten ihrer graphentheoretischen Indices widerspiegelt. Es ist nur natürlich, nach den Wertebereichen dieser Indices zu fragen und jene Graphen zu bestimmen, welche die Indices über gewissen Graphenklassen (z.B. Bäume) maximieren bzw. minimieren. Somit ist es ein Ziel dieses Projekts, extremale Graphen bezüglich Indices im Zusammenhang mit dem Wiener-Index (Summe der paarweisen Distanzen), dem Merrifield-Simmons-Index (Anzahl unabhängiger Mengen) sowie dem Hosoya-Index (Anzahl der Matchings) unter verschiedenen Nebenbedingungen zu bestimmen. Solche extremale Graphen können manchmal nur durch Verwendung anderer mathematischer Konzepte beschrieben werden, beispielsweise spezieller Ziffernentwicklungen für die relevanten Parameter wie etwa die Ordnung des Graphen. Andererseits sind Ziffernentwicklungen auch ein zentrales Konzept in unseren Untersuchungen von Fragestellungen in der Kryptographie. Asymmetrische Kryptographie beruht auf der effizienten Berechnung von Einwegfunktionen, wobei wir uns hier auf die Berechnung von skalaren Vielfachen nP eines Elements P einer abelschen Gruppe konzentrieren. Klassischerweise stellt man n durch eine Ziffernentwicklung dar und führt die Skalarmultiplikation mittels Horner-Schemas durch, was zum sogenannten "double-and-add"-Verfahren führt. Neben der multiplikativen Gruppe eines endlichen Körpers ist auch die Punktgruppe einer elliptischen (oder auch hyperelliptischen) Kurve weit verbreitet, wobei hier zusätzliche Strukturen dieser Gruppen viele Variationen des ursprünglichen Verfahrens zulassen. Insbesondere sind Ziffernentwicklungen zu gewissen nicht-rationalen Basen von Interesse. Ein Ziel des Projekts ist es, in verschiedenen Konfigurationen optimale Entwicklungen zu bestimmen und die resultierenden Algorithmen einer präzisen asymptotischen und probabilistischen Analyse im Sinne von D. E. Knuth zu unterziehen.