Regulator approximation and fundamental unit computation for real-quadratic orders

Maurer, Markus (2000)
Regulator approximation and fundamental unit computation for real-quadratic orders.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

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.

Typ des Eintrags:

Dissertation

Erschienen:

2000

Autor(en):

Maurer, Markus

Art des Eintrags:

Erstveröffentlichung

Titel:

Regulator approximation and fundamental unit computation for real-quadratic orders

Sprache:

Englisch

Referenten:

Buchmann, Prof. Dr. Johannes ; Nigel, Prof. Dr. Smart

Berater:

Buchmann, Prof. Dr. Johannes

Publikationsjahr:

20 Dezember 2000

Ort:

Darmstadt

Verlag:

Technische Universität

Datum der mündlichen Prüfung:

13 November 2000

URL / URN:

urn:nbn:de:tuda-tuprints-878

Kurzbeschreibung (Abstract):

Alternatives oder übersetztes Abstract:

Alternatives Abstract

Sprache

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.

Deutsch

Freie Schlagworte:

real quadratic order, quadratic number field, regulator, fundamental unit, quadratic ideal, Dirichlet L-series

Sachgruppe der Dewey Dezimalklassifikatin (DDC):

500 Naturwissenschaften und Mathematik > 510 Mathematik

Fachbereich(e)/-gebiet(e):

20 Fachbereich Informatik
20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra

Hinterlegungsdatum:

17 Okt 2008 09:20

Letzte Änderung:

14 Jan 2019 10:10

PPN: