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.
Darmstadt, Technische Universität, TU Darmstadt,
[Ph.D. Thesis]

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.

Item Type: Ph.D. Thesis
Erschienen: 2000
Creators: Maurer, Markus
Title: Regulator approximation and fundamental unit computation for real-quadratic orders
Language: English
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.
Place of Publication: Darmstadt
Publisher: Technische Universität
Uncontrolled Keywords: real quadratic order, quadratic number field, regulator, fundamental unit, quadratic ideal, Dirichlet L-series
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 17 Oct 2008 09:20
URL / URN: urn:nbn:de:tuda-tuprints-878
License: only the rights of use according to UrhG
PPN:
Referees: Buchmann, Prof. Dr. Johannes ; Nigel, Prof. Dr. Smart
Refereed / Verteidigung / mdl. Prüfung: 13 November 2000
Alternative Abstract:
Alternative abstract Language

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.

German
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details
OAI 2.0-Basis-URL: https://tubiblio.ulb.tu-darmstadt.de/cgi/oai2 TUbiblio verwendet EPrints 3.
Drucken | Impressum | Datenschutzerklärung