×

Regulator approximation and fundamental unit computation for real-quadratic orders. (English) Zbl 1079.11061

Darmstadt: TU Darmstadt, Fachbereich Informatik (Dissertation). 221 p. (2000).
From the introduction: In this thesis we study computational problems in a real quadratic order \(O\). In particular, we study algorithms for computing the regulator \(R\) 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 \(aX^2+ bXY+ cY^2= n\). Recently, the difficulty of solving those problems has also been used as the basis of the security of cryptographic protocols.
The first algorithm for solving our problems was invented by Legendre, Lagrange, and Gauss. It is based on the continued fraction algorithm but is rather inefficient. This method requires time \(R\Delta^{o(1)}\) for computing the fundamental unit and an approximation of fixed precision to the regulator \(R\), where \(\Delta\) is the discriminant of \(O\). In 1972 Shanks presented a more efficient algorithm. In the version of Biehl and Buchmann this algorithm has running time \(R^{1/2} \Delta^{o(1)}\). Experiments show that the regulator is very often of the order of magnitude \(\Delta^{1/2}\). Then the algorithm takes time \(\Delta^{(1/4)+o(1)}\). Lenstra and Schoof presented an algorithm, whose running time is \(\Delta^{1/5)+o(1)}\) assuming the extended Riemann hypothesis (ERH). It is still exponential in the binary length of the discriminant. A subexponential algorithm was suggested by Buchmann, Abel, and Vollmer. Its running time is \(\exp((5\sqrt{3}/6+ o(1))(\log \Delta)^{1/2}(\log\log \Delta)^{1/2})\) assuming the ERH.
There is one serious problem with most of the algorithms mentioned above. Since the regulator is a transcendental number, they all 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. Some of our algorithms have been used to implement cryptographic protocols.
In the appendix we present running times and statistical data for the algorithms developed in this thesis. The algorithms have been implemented in LiDIA, a library for computational number theory.

MSC:

11Y40 Algebraic number theory computations
11R11 Quadratic extensions
11R27 Units and factorization

Software:

LiDIA
PDFBibTeX XMLCite
Full Text: Link