This article describes a computer algorithm which exhibits a sufficient condition for a number field to be euclidean for the norm. In the survey [3] p 405, Franz Lemmermeyer pointed out that 743 number fields where known (march 1994) to be euclidean (the first one, $\mathbb{Q}$, discovered by Euclid, three centuries B.C.!). In the first months of 1997, we found more than 1200 new euclidean number fields of degree 4, 5 and 6 with a computer algorithm involving classical lattice properties of the embedding of...

Numerous important lattices ($D_4,E_8$, the Coxeter-Todd lattice $K_{12}$, the Barnes-Wall lattice ${\Lambda }_{16}$, the Leech lattice ${\Lambda }_{24}$, as well as the $2$-modular $32$-dimensional lattices found by Quebbemann and Bachoc) possess algebraic structures over various Euclidean rings, e.g. Eisenstein integers or Hurwitz quaternions. One obtains efficient algorithms by performing within this frame the usual reduction procedures, including the well known LLL-algorithm.

When Henri Cohen and his coworkers set out to write PARI twenty years ago, GP was an afterthought. While GP has become the most commonly used interface to the PARI library by a large margin, both the gp interpretor and the GP language are primitive in design. Paradoxically, while gp allows to handle very high-level objects, GP itself is a low-level language coming straight from the seventies.We rewrote GP as a compiler/evaluator pair, implementing several high-level features (statically scoped variables,...

The algorithm described in this paper is a practical approach to the problem of giving, for each number field $K$ a polynomial, as canonical as possible, a root of which is a primitive element of the extension $K/\mathbb{Q}$. Our algorithm uses the $LLL$ algorithm to find a basis of minimal vectors for the lattice of ${ℝ}^n$ determined by the integers of $K$ under the canonical map.

We give a survey of computational class field theory. We first explain how to compute ray class groups and discriminants of the corresponding ray class fields. We then explain the three main methods in use for computing an equation for the class fields themselves: Kummer theory, Stark units and complex multiplication. Using these techniques we can construct many new number fields, including fields of very small root discriminant.

We show how to adapt Terr’s variant of the baby-step giant-step algorithm of Shanks to the computation of the regulator and of generators of principal ideals in real-quadratic number fields. The worst case complexity of the resulting algorithm depends only on the square root of the regulator, and is smaller than that of all other previously specified unconditional deterministic algorithm for this task.

The computation of polynomial greatest common divisor (GCD) ranks among basic algebraic problems with many applications, for example, in image processing and control theory. The problem of the GCD computing of two exact polynomials is well defined and can be solved symbolically, for example, by the oldest and commonly used Euclid’s algorithm. However, this is an ill-posed problem, particularly when some unknown noise is applied to the polynomial coefficients. Hence, new methods for the GCD computation...

In this paper we study the algorithmic problem of finding the ring of integers of a given algebraic number field. In practice, this problem is often considered to be well-solved, but theoretical results indicate that it is intractable for number fields that are defined by equations with very large coefficients. Such fields occur in the number field sieve algorithm for factoring integers. Applying a variant of a standard algorithm for finding rings of integers, one finds a subring of the number field...

Canonical number systems can be viewed as natural generalizations of radix representations of ordinary integers to algebraic integers. A slightly modified version of an algorithm of B. Kovács and A. Pethő is presented here for the determination of canonical number systems in orders of algebraic number fields. Using this algorithm canonical number systems of some quartic fields are computed.

In a recent paper we proved that there are at most finitely many complex numbers $t\ne 0,1$ such that the points $(2,\sqrt{2(2-t)})$ and $(3,\sqrt{6(3-t)})$ are both torsion on the Legendre elliptic curve defined by $y^2=x(x-1)(x-t)$. In a sequel we gave a generalization to any two points with coordinates algebraic over the field $\mathbf{Q}\left(t\right)$ and even over $\mathbf{C}\left(t\right)$. Here we reconsider the special case $(u,\sqrt{u(u-1)(u-t)})$ and $(v,\sqrt{v(v-1)(v-t)})$ with complex numbers $u$ and $v$.