Regulator approximation and fundamental unit computation for real-quadratic orders

In this thesis we study computational problems in a real quadratic order O. In particular, we study algorithms for computing the regulator and the fundamental unit of O, for deciding equivalence of O-ideals, and for determining generators of principal O-ideals. Those are some of the most difficult and important problems in computational number theory. They are closely related to the problem of solving the Pell equation and, more generally, the diophantine equation a X^2 + b XY + c Y^2 = n. Recently, the difficulty of solving those problems has also been used as the basis of the security of cryptographic protocols. There is one serious problem with most of the algorithms for solving the above problems. Since the regulator is a real number, they use approximations to real numbers. However, the analysis of the algorithms does not determine the precision of approximation necessary for the algorithms to be correct. Therefore, the proofs of the correctness and the estimates for the running times of the algorithms are incomplete. In this thesis we give complete descriptions, correctness proofs, and complexity analyses of the important algorithms for approximating regulators, computing fundamental units, deciding ideal equivalence, and computing generators of principal ideals of quadratic orders. We describe improvements for several algorithms. We also present an object oriented implementation of all algorithms including experimental results.

In dieser Arbeit studieren wir Berechnungsprobleme für reell-quadratische Ordnungen O. Wir untersuchen Algorithmen zur Berechnung der Fundamentaleinheit und des Regulators von O, zum Entscheiden der Äquivalenz zweier O-Ideale und zur Berechnung eines Hauptidealerzeugers. Diese Probleme gehören zu den schwierigsten und wichtigsten in der algorithmischen Zahlentheorie. Sie sind eng verwandt mit dem Lösen der Pellschen Gleichung, und allgemeiner, mit dem Lösen der diophantischen Gleichung a X^2 + b XY + c Y^2 = n. Seit einigen Jahren gibt es auch kryptographische Protokolle, deren Sicherheit auf der Schwierigkeit dieser Probleme beruht. Für die meisten dieser Algorithmen besteht jedoch ein großes Problem. Da der Regulator eine reelle Zahl ist, verwenden die Algorithmen Approximationen an reelle Zahlen. In der Analyse der Algorithmen werden jedoch nicht die benötigten Genauigkeiten hergeleitet. Deshalb sind die Korrektheitsbeweise und die Abschätzungen der Laufzeiten unvollständig. In dieser Arbeit geben wir vollständige Beschreibungen, Korrekheitsbeweise und Komplexitätsanalysen für die wichtigen Algorithmen zur Approximation von Regulatoren, Berechnung von Fundamentaleinheiten, Berechnung von Hauptidealerzeugern und zum Entscheiden der Äquivalenz von O-Idealen für reell-quadratische Ordnungen O an. Wir beschreiben Verbesserungen für einige Algorithmen. Wir präsentieren auch eine objektorientierte Implementierung aller Algorithmen einschließlich experimenteller Resultate.