Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around. / Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.

Computing discrete logarithms is a long-standing algorithmic problem, whose hardness forms the basis for numerous current public-key cryptosystems. In the case of finite fields of small characteristic, however, there has been tremendous progress recently, by which the complexity of the discrete logarithm problem (DLP) is considerably reduced. This habilitation thesis on the DLP in such fields deals with two principal aspects. On one hand, we develop and investigate novel efficient algorithms for computing discrete logarithms, where the complexity analysis relies on heuristic assumptions. In particular, we show that logarithms of factor base elements can be computed in polynomial time, and we discuss practical impacts of the new methods on the security of pairing-based cryptosystems. While a heuristic running time analysis of algorithms is common practice for concrete security estimations, this approach is insufficient from a mathematical perspective. Therefore, on the other hand, we focus on provable complexity results, for which we modify the algorithms so that any heuristics are avoided and a rigorous analysis becomes possible. We prove that for any prime field there exist infinitely many extension fields in which the DLP can be solved in quasi-polynomial time. Despite the two aspects looking rather independent from each other, it turns out, as illustrated in this thesis, that progress regarding practical algorithms and record computations can lead to advances on the theoretical running time analysis -- and the other way around. / Die Berechnung von diskreten Logarithmen ist ein eingehend untersuchtes algorithmisches Problem, dessen Schwierigkeit zahlreiche Anwendungen in der heutigen Public-Key-Kryptographie besitzt. Für endliche Körper kleiner Charakteristik sind jedoch kürzlich erhebliche Fortschritte erzielt worden, welche die Komplexität des diskreten Logarithmusproblems (DLP) in diesem Szenario drastisch reduzieren. Diese Habilitationsschrift erörtert zwei grundsätzliche Aspekte beim DLP in Körpern kleiner Charakteristik. Es werden einerseits neuartige, erheblich effizientere Algorithmen zur Berechnung von diskreten Logarithmen entwickelt und untersucht, wobei die Laufzeitanalyse auf heuristischen Annahmen beruht. Unter anderem wird gezeigt, dass Logarithmen von Elementen der Faktorbasis in polynomieller Zeit berechnet werden können, und welche praktischen Auswirkungen die neuen Verfahren auf die Sicherheit paarungsbasierter Kryptosysteme haben. Während heuristische Laufzeitabschätzungen von Algorithmen für die konkrete Sicherheitsanalyse üblich sind, so erscheint diese Vorgehensweise aus mathematischer Sicht unzulänglich. Der Aspekt der beweisbaren Komplexität für DLP-Algorithmen konzentriert sich deshalb darauf, modifizierte Algorithmen zu entwickeln, die jegliche heuristische Annahme vermeiden und dessen Laufzeit rigoros gezeigt werden kann. Es wird bewiesen, dass für jeden Primkörper unendlich viele Erweiterungskörper existieren, für die das DLP in quasi-polynomieller Zeit gelöst werden kann. Obwohl die beiden Aspekte weitgehend unabhängig voneinander erscheinen mögen, so zeigt sich, wie in dieser Schrift illustriert wird, dass Fortschritte bei praktischen Algorithmen und Rekordberechnungen auch zu Fortentwicklungen bei theoretischen Laufzeitabschätzungen führen -- und umgekehrt.

Das erste Thema dieser Dissertation ist der Defekt projektiver Hyperflächen. Es scheint, dass Hyperflächen mit Defekt einen verhältnismäßig großen singulären Ort besitzen. Diese Aussage wird im ersten Kapitel der Dissertation präzisiert und für Hyperflächen mit beliebigen isolierten Singularitäten über einem Körper der Charakteristik null, sowie für gewisse Klassen von Hyperflächen in positiver Charakteristik bewiesen. Darüber hinaus lässt sich die Dichte von Hyperflächen ohne Defekt über einem endlichen Körper abschätzen. Schließlich wird gezeigt, dass eine nicht-faktorielle Hyperfläche der Dimension drei mit isolierten Singularitäten stets Defekt besitzt. Das zweite Kapitel der Dissertation behandelt Bertini-Sätze über endlichen Körpern, aufbauend auf Poonens Formel für die Dichte glatter Hyperflächenschnitte in einer glatten Umgebungsvarietät. Diese wird auf quasiglatte Hyperflächen in simpliziellen torischen Varietäten verallgemeinert. Die Hauptanwendung ist zu zeigen, dass Hyperflächen mit einem in Relation zum Grad großen singulären Ort die Dichte null haben. Weiterhin enthält das Kapitel einen Bertini-Irreduzibilitätssatz, der auf einer Arbeit von Charles und Poonen beruht. Im dritten Kapitel werden ebenfalls Dichten über endlichen Körpern untersucht. Zunächst werden gewisse Faserungen über glatten projektiven Basisvarietäten in einem gewichteten projektiven Raum betrachtet. Das erste Resultat ist ein Bertini-Satz für glatte Faserungen, der Poonens Formel über glatte Hyperflächen impliziert. Der letzte Abschnitt behandelt elliptische Kurven über einem Funktionskörper einer Varietät der Dimension mindestens zwei. Die zuvor entwickelten Techniken ermöglichen es, eine untere Schranke für die Dichte solcher Kurven mit Mordell-Weil-Rang null anzugeben. Dies verbessert ein Ergebnis von Kloosterman. / The first topic of this dissertation is the defect of projective hypersurfaces. It is indicated that hypersurfaces with defect have a rather large singular locus. In the first chapter of this thesis, this will be made precise and proven for hypersurfaces with arbitrary isolated singularities over a field of characteristic zero, and for certain classes of hypersurfaces in positive characteristic. Moreover, over a finite field, an estimate on the density of hypersurfaces without defect is given. Finally, it is shown that a non-factorial threefold hypersurface with isolated singularities always has defect. The second chapter of this dissertation deals with Bertini theorems over finite fields building upon Poonen’s formula for the density of smooth hypersurface sections in a smooth ambient variety. This will be extended to quasismooth hypersurfaces in simplicial toric varieties. The main application is to show that hypersurfaces admitting a large singular locus compared to their degree have density zero. Furthermore, the chapter contains a Bertini irreducibility theorem for simplicial toric varieties generalizing work of Charles and Poonen. The third chapter continues with density questions over finite fields. In the beginning, certain fibrations over smooth projective bases living in a weighted projective space are considered. The first result is a Bertini-type theorem for smooth fibrations, giving back Poonen’s formula on smooth hypersurfaces. The final section deals with elliptic curves over a function field of a variety of dimension at least two. The techniques developed in the first two sections allow to produce a lower bound on the density of such curves with Mordell-Weil rank zero, improving an estimate of Kloosterman.