Universelle elliptische Gauß-Summen und der Algorithmus von Schoof

Abstract

Die vorliegende Arbeit beschäftigt sich mit verschiedenen neuen Ansätzen im Kontext des Punktezählens auf elliptischen Kurven über endlichen Primkörpern mit großer Charakteristik. Sie baut dabei auf der Grundidee von Schoof auf, die Punktanzahl mithilfe der charakteristischen Gleichung, die der Frobenius-Homomorphismus im Endomorphismenring der Kurve erfüllt, zu bestimmen. Modulo sogenannten Elkies-Primzahlen zerfällt die Gleichung in Linearfaktoren, was die Laufzeit beschleunigt.<br /> Wir untersuchen, wie die von Mihăilescu analog zu den zyklotomischen Gauß-Summen definierten elliptischen Gauß-Summen, die die Zeit-Komplexität für Elkies-Primzahlen weiter reduzieren können, effizient bestimmt werden können. Hierzu werden mithilfe galois-theoretischer Überlegungen zunächst einige Resultate zu Körpern von Modulfunktionen bewiesen. Unter Verwendung der Tate-Kurve, die die Isomorphieklassen elliptischer Kurven über den komplexen Zahlen parametrisiert, definieren wir die universellen elliptischen Gauß-Summen als Verallgemeinerung der elliptischen Gauß-Summen. Nachfolgend zeigen wir, dass sie im Körper der Modulfunktionen von Gewicht 0 für eine bestimmte Untergruppe von SL₂(Z) liegen und daher als rationaler Ausdruck in zwei wohlbekannten Modulfunktionen dargestellt werden können.<br /> Weitere Untersuchungen dieser Aussage liefern eine Standardform für diesen Ausdruck, die tatsächliche Rechnungen überhaupt erst effizient durchführbar macht. Wir betrachten die Darstellung in dieser Standardform im Detail und lösen verschiedene Probleme, um eine effiziente algorithmische Umsetzung zu erreichen, wobei wir zwei Alternativen für die Wahl der zweiten Modulfunktion ausführlich untersuchen und sowohl qualitativ als auch mithilfe unserer Implementierung quantitativ vergleichen. Anschließend zeigen wir detailliert, wie sich aus den vorberechneten Ausdrücken für Elkies-Primzahlen effizient berechenbare Formeln für gewisse Potenzen der elliptischen Gauß-Summen auf konkreten Kurven über endlichen Körpern ergeben, mit deren Hilfe wie oben beschrieben die Punktzahl der Kurven mit geringer Laufzeit bestimmt werden kann.<br /> Hierauf folgen verschiedene weitere Abschnitte, in denen eine Verallgemeinerung auf die Potenzen von Elkies-Primzahlen sowie eine Modifikation der Ideen zur Verwendung von Atkin-Primzahlen untersucht werden, modulo denen die charakteristische Gleichung des Frobenius-Homomorphismus irreduzibel bleibt.

<strong>Universal elliptic Gauß sums and Schoof’s algorithm</strong><br /> This thesis is concerned with several new approaches in the context of point-counting on elliptic curves over finite prime fields with large characteristic. It builds upon Schoof’s basic idea to determine the number of points using the characteristic equation satisfied by the Frobenius homomorphism in the endomorphism ring of the curve. Modulo so-called Elkies primes the equation factors into linear factors, which improves the run-time.<br /> We investigate how to efficiently compute the elliptic Gauß sums, defined by Mihăilescu in analogy with the cyclotomic Gauß sums, which allow to further reduce the time-complexity for Elkies primes. First, several results on fields of modular functions are proven by galois-theoretic arguments. We next define universal elliptic Gauß sums as a generalisation of the elliptic Gauß sums using the Tate curve, which parametrises isomorphism classes of elliptic curves over the complex numbers. We subsequently show that they lie in the field of modular functions of weight 0 of a certain subgroup of SL₂(Z) and can hence be represented as a rational expression in two well-known modular functions.<br /> Further inspection of this statement yields a standard form for this expression that renders computations efficient in the first place. We consider the representation in this standard form in detail and solve several problems for achieving an efficient algorithmic implementation, where we extensively study two alternatives for the choice of the second modular function and compare them both qualitatively and quantitatively using our implementation. We afterwards show in detail how efficiently computable formulae for certain powers of the elliptic Gauß sums on concrete curves over finite fields can be gleaned from the pre-computed expressions for Elkies primes. Using these formulae the number of points on the curves can be determined with low run-time as described above.<br /> These sections are followed by several others which investigate a generalization to the powers of Elkies primes as well as a modification of the ideas for using Atkin primes, modulo which the characteristic equation of the Frobenius homomorphism remains irreducible.