TU Darmstadt / ULB / TUbiblio

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):

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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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:
Referenten: Buchmann, Prof. Dr. Johannes ; Nigel, Prof. Dr. Smart
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 13 November 2000
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen