KANT-2 – A Programmer’s Guide

Johannes Graf v. Schmettow, Max Jüntgen

Mathematisches Institut der Heinrich-Heine-Universität Düsseldorf

4000 Düsseldorf 1, Germany

Draft (March , 1993)

Contents

1 Introduction 4 1.1 KANT-1 and KANT-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Orders, number fields and algebraic numbers – an outline 7 2.1 The general idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Using the Platform 12 3.1 The Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 The Integer Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 The Real Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 The Polynomial Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 The Anf Package 18

4.1 Working with KANT data types . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.1.1 Lattices and lattice elements . . . . . . . . . . . . . . . . . . . . . . 18 4.1.2 Number fields and orders . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1.3 Algebraic numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.4 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1.5 Ceilings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 More sophisticated features of KANT . . . . . . . . . . . . . . . . . . . . . . 26 4.2.1 Constructing overorders . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2.2 Factor basis and relations . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2.3 Subfields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2.4 Dealing with real numbers . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3 Developing KANT programs . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3.1 Main Rules for KANT programmers . . . . . . . . . . . . . . . . . . 30 4.3.2 Developing functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.3.3 Developing main programs . . . . . . . . . . . . . . . . . . . . . . . 32 4.3.4 Debugging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.5 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.6 Interface to KANT-1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 Data types, functions and macros 38 5.1 The data types of KANT (and the Platform) . . . . . . . . . . . . . . . . . 38 5.2 The Integer Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.3 The Rationals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.4 The Real Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.5 The Complex Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.6 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5.7 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.8 lattices, lat elts and lat enum envs . . . . . . . . . . . . . . . . . . . . 49

5.8.1 lattice macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 5.8.2 lattice functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.9 orders, anfs etc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.9.1 The macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 5.9.2 The functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5.10 Interface routines orders ↔ lattices . . . . . . . . . . . . . . . . . . . . . 76 5.11 Main KANT programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5.11.1 Arithmetic with orders, algebraic numbers and ideals . . . . . . . . . 76 5.11.2 Enlarging orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.11.3 Units, class groups and norm equations . . . . . . . . . . . . . . . . 78 5.11.4 etc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.12 Debugging functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6 Sample program listings 82 6.1 Elements of small T_{2}-value . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.2 p-maximal overorders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.3 Nice primitive elements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

7 Installation of KANT-2 88 7.1 Installing KANT-2 on Unix machines . . . . . . . . . . . . . . . . . . . . . . 88 7.2 Installing KANT-2 on non-Unix machines . . . . . . . . . . . . . . . . . . . 89

7.3 How to get KANT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Bibliography 91

Chapter 1

Introduction

Since we want to help the reader avoiding to read too much of this manual we start with a

Quick Guide to this manual:

Main rules for KANT programmers  Section 4.3.1, page 30
Data types  Section 5.1, page 38
Sample KANT programs  Section 4.3.1, page 30
Debugging KANT programs and functions Section 4.3.4, page 33
Creation and deletion functions  Section 5.1, page 40
Macros accessing lattices  Section 5.8.1, page 50
Functions dealing with lattices  Section 5.8, page 49
Macros accessing orders etc.  Section 5.9.1, page 54
Functions dealing with orders etc.  Section 5.9.2, page 57

The manual is subdivided into two major parts. The first one (the Macropædia) tries to give an overview of the main ideas and the philosophy of KANT, going into details only every now and then. The second part (the Micropædia), starting with Section 5, page 38, tries to explain almost every macro and function which might be of use for KANT programmers.

1.1 KANT-1 and KANT-2

Increasing speed and decreasing cost of computers has had a considerable impact on number theoretic research in the last decades. Many algorithms which originally had been invented for theoretical reasons could be utilized within efficient computer programs – an example is the proof of the Dirichlet theorem describing the unit group structure of an algebraic number field and its practical version by Buchmann and Pethö [6].

Our first prototype of a subroutine library performing methods of algebraic number theory was KANT-1. It was developed in Düsseldorf by the KANT Group in 1987–1991 under the project leadership of M. E. Pohst (see [32] for a description). KANT-1 is an ANSI-Fortran library consisting of about 40,000 statements. It can be used for various applications; especially it was designed for computing integral bases, unit groups and class groups of number fields of degree up to 20.

However, the architecture of KANT-1 turned out to be too narrow for many demands originating from number theoretic research. Moreover, the concept of static memory management is inefficient, especially since many number theoretic algorithms have to cope with large intermediate numbers (Hermite normal form, e.g.).

Since August 1991, a completely new algebraic number theory package has been under development, taking into account the experiences with KANT-1. This new system, KANT-2, is written in ANSI-C and is built on a foundation consisting of

– a memory management package (MEM)

– an arbitrary precision integer package

– an arbitrary precision real number package

– a multivariate polynomial package over arbitrary rings

– and a general linear algebra package.

These packages are provided by the Cayley Group in Sydney and include the so-called Platform which became public domain in 1991 (for a description see [2]). The generous support by the Cayley Group made it possible for the first release of KANT-2 to be available so shortly after the implementations had started.

We call the number theoretic algorithms of KANT-2 the Anf Package. The functions of the Anf Package are being developed by the KANT Group in Düsseldorf; we are very grateful for much technical advice and support from the Cayley Group in Sydney.

The source code of KANT-2 is entirely public domain and is available from the KANT Group. Nevertheless most of its features are also accessible through the general computer algebra system Cayley V4.

Like KANT-1, the new version of KANT is a subroutine library. The development of a (public domain) dialogue shell is in planned, nevertheless – if one intends to use the complete power of KANT-2 – it will be necessary to write C-programs which call the KANT-routines.

At present, the Anf Package provides the user with

– an arbitrary precision integer and real lattice package (reduction methods, enumeration of lattice points, short and shortest vectors)

– an order and number field package

– an algebraic number package

– an ideal package for fractional ideals of algebraic number fields

– interface routines lattices ↔ orders

The intention of this guide is to support a programmer who wants to use the library. We assume that the user knows how to write, compile and link programs in C and that he has access to the introductory paper on the Platform [2]. Additionally, we expect that the reader has some basic knowledge about algebraic number theory. However, good algorithmic approaches to algebraic number theory are given in [10, 27] and the general background is outlined for example in [19, 29].

It is probably necessary for a programmer to study the Header files and some of the Anfroutines for learning all details of the Anf Package. Here we present a Hands-on manual intending to get the user started as soon as possible without overloading him with technical details.

Orders, number fields and algebraic numbers – an outline

2.1 The general idea

While designing this package it was a natural goal to keep most of the concepts as open as possible. An example is the possible existence of relative integral bases of number fields. There are only very few practical algorithms to compute bases of relative extensions (in many cases there does not even exist such a basis). In spite of this the machinery should be able to deal with relative bases easily. Experiments with KANT-1 have indicated that the availability of this feature might be very promising.

Moreover, a first computational approach to computing relative integral bases by KANT has been done in [11].

In KANT-1 an algebraic integer α was an array of n > 1 integers representing the coefficients of α in a given ZZ-Basis of an order.

Now an algebraic number (anf elt) can be:

– a rational integer with arbitrary precision

– an array of coefficients referring to a given basis of an order. The coefficients can again be algebraic integers of a subfield. The handling of a denominator – which has to be a rational integer – is supported.

– an array of arbitrary precision real numbers which represent approximations to the conjugates of that algebraic number

Additional representations are easy to implement. This will be done whenever necessary.

KANT-2 performs arithmetic with algebraic numbers by using generic routines. So for example for multiplication of algebraic numbers the user has to keep in mind just one subroutine name (anf elt mult, in this example) which is to be called for any combination of the representations above.

The same philosophy applies to ideals in algebraic number fields (anf ideal). Again, there are several ways to represent ideals. This is explained in greater detail in [27]; we mention here that at present three representations are supported:

– via an O-Basis (where O is a suborder)

– as a sum of two principal ideals (two-element presentation)

– in the so-called two-element-normal presentation which allows componentwise multiplication and easy inversion (see [27]).

Again, generic routines supply the user with the ideal arithmetic.

In algebraic number theory we often want to determine invariants of number fields or orders, whereas algebraic numbers and ideals are mainly used for intermediate considerations. H. Zassenhaus regarded the determination of Galois groups, integral bases, unit groups and class groups of number fields as the major tasks of computational algebraic number theory. Many of the general purpose algorithms computing these structures use extensive arithmetic in various orders of a particular number field (for a description of the methods see [27, 29]). In particular, the methods for computing unit groups apply to any order and not necessarily to the maximal order of a number field.

So we decided to install order as a central type for the Anf Package. In the actual declaration an order should provide ways to determine how arithmetic with order elements is to be done. Here we have several options:

– via a multiplication table of the order basis elements

– via particular flags which – for example – indicate that the actual order is the equation order of a pure (relative) extension and that the actual basis is a power (relative) basis. Now the multiplication of order elements can be done fast by simple arithmetic in the order of the coefficients.

The coefficients of an anf elt (as explained above) refer to a basis of the order. Since we also allow denominators for the anf elts we actually have elements of the quotient field of the actual order (which is a number field). This is the reason why we call an algebraic number anf elt instead of order elt.

Nevertheless, arithmetic operations with algebraic numbers refer to orders. So the correct syntax for multiplication of anf elts is:

                  gamma = anf elt mult(ord, alpha, beta);

where ord represents the order which alpha, beta and gamma belong to. The representation of gamma (in one of the ways explained above) is dependent on the representation of alpha

and beta.

The C-structure describing an order contains many items which will be explained later. In spite of this KANT-2 provides the user with macros, subroutines and default options which allow almost all complicated details to be concealed.

The definition of an order in the Anf Package has been made according to the conventions for generic rings in Cayley. So for example it is possible to deal with matrices and polynomials over algebraic integers without any additional programming effort.

Although most of the algorithms apply to orders we need a structure which describes an algebraic number field itself. We called it anf. The task of an anf is to provide the user with a table of the actual orders belonging to the number field and – if necessary – with a table of generating polynomials of the field over one or several ground fields. Since every order basis is also a basis of the number field we do not need to define a particular basis for an anf.

Of course the user can deal with many orders or anfs at the same time allowing recursive code.

There are many coercion routines: So it is comparatively easy to “lift” or “move” representations of algebraic numbers referring to different order bases or even bases of different orders. The coercion function of KANT automatically tries to install homomorphisms between orders so that subsequent coercions can be done much faster.

2.2 An example

We will now give an example of a KANT program dealing with relative bases. We should emphasize that this is an example for doing arithmetic and not for determining bases. Please note that this example is not trivial! See Section 6, page 82 for simpler ones.

Let us consider the number field

Q ( ^{m} \sqrt{η})

where m ∈ ZZ^{>1} and η an algebraic integer of a pure extension of ZZ. We want to demonstrate how one can implement calculations using the order

O_{2} := O_{1} [ ^{m} \sqrt{η}]

where

O_{1} := ZZ[ ^{n} \sqrt{a}],

η ∈ O_{1}, m ∈ ZZ^{>1} and a ∈ ZZ chosen appropriately.

The following program initializes O_{1} and O_{2} and multiplies algebraic numbers α and β of O_{2}:

#include "kant.h"                /* Compulsory Header file */
main(
)
{
        block_declarations;      /* Convention for Platform users */
        order           Z, ord_1, ord_2;
        anf_elt         a, eta, alpha, beta, gamma;
        char            str[200];
        t_int           m, n;
/* Startup */
        kant_start();

/*  The ring of rational integers */
Z = structure_z;
/*  Input of n and a */
printf("Give n and a!\n");
scanf("%d", &n);
a = anf_elt_read(Z); gets(str);
/*  We create the pure extension of Z */
ord_1 = order_create_pure(Z, a, n);
/*  Input of m and eta */
printf("Give m and eta!\n");
scanf("%d", &m);
eta = anf_elt_read(ord_1); gets(str);
/*  We create the pure extension of the first order */
ord_2 = order_create_pure(ord_1, eta, m);

/* Application (here: Multiplication of algebraic numbers) */
for (;;)
{
        printf("Give two algebraic numbers:\n");
        alpha = anf_elt_read(ord_2);
        beta  = anf_elt_read(ord_2);
        gets(str);
        if (!alpha || !beta) break;
        gamma = anf_elt_mult(ord_2, alpha, beta);
        printf("Product: ");
        anf_elt_write(ord_2, gamma);
        printf("\n");
        anf_elt_delete(ord_2, &alpha);
        anf_elt_delete(ord_2, &beta);
        anf_elt_delete(ord_2, &gamma);
}
integer_delref(a);
anf_elt_delete(ord_1, &eta);

KANT-2 – Outline 11

        order_delete(&ord_1);
        order_delete(&ord_2);
}

The program mainly consists of I/O statements and comment lines. The compulsory statement

                               kant start();

initializes the MEM and the mp Package. The routine

                             order create pure

creates a pure extension and a power relative basis over an arbitrary order. It also assures that arithmetic within the order can be done. The multiplication routine

                               anf elt mult

implicitly allocates space for the result of the multiplication. The space of the anf elts must be released by calling the macro

                              anf elt delete

when alpha, beta and gamma are not needed anymore.

Using the Platform

The description of the Platform in this chapter is far from being complete but in [2] one will find a very good survey of most of its features. We will be a bit more explicit when talking about polynomials, since this part is somewhat more difficult to deal with.

3.1 The Basic Idea

The memory management of the Platform is done by MEM, which takes care of

– memory allocation

– memory deletion

– resizing of blocks

– memory compaction (garbage collection and coalescion).

Almost all of the MEM features are hidden by higher-level manipulation functions and macros, so we do not need become too technical in this section.

At the very beginning of a program one has to initialize MEM by a single function call (mem init()). From then on it acts as a server for the various packages. Access to any block of memory is possible via a so-called t handle, usually a small negative integer. The internal macro mem access(h), where h is a handle, returns the actual pointer to the block under consideration. This additional level of indirection makes it easy to shift around blocks without making the handles invalid. They are the visible part of a block. However, currently no active blocks will be shifted by MEM – so also pointer access is possible without any danger.

A block itself contains a so-called block type and a block ref count. The block type (=Tracked Block Type) identifies the type of the contents of the block. The trbl refcnt (reference count) is a counter maintaining the number of actual references to the block.

We will give an example: For the multiplication of two integer bigs a and b one has to perform

                          c = integer mult(a, b);

The multiplication routine checks whether a or b are unity. If for example b is a large number (represented by its handle) but a=1 no copying of the block is performed: The function will simply increment the reference count of b and return the same handle.

Understanding this concept is very important for users of KANT and the Platform: Copying of blocks is executed virtually. If one wants to “copy” the integer big b to c one has to write

                          c = integer incref(b);

The second important concept of the Platform is that blocks have to be freed by the user. Here the deletion is usually only a decrementation of the reference count – in case of an

integer big b for example
                            integer delref(b);

which doesn’t affect c in any way. In case the reference count is 1 the block will be freed also.

In Section 5.1, page 40, there is a survey of all deletion macros for the different types of KANT. The names of the incrementation macros are more consistent: They usually start with the type name and end with incref.

3.2 The Integer Package

There are two types of integers. One is t int and refers to all integers whose absolute value does not exceed BETA (which is currently 2^{29}). Parameters of this type are used for example as loop indices and needn’t be created or deleted explicitly.

The second type is integer big and refers to an arbitrary precision integer. If the absolute value of an integer big is less than BETA it is immediate. This means that it does not refer to a handle but it represents itself .

The syntaxes of the sequences

                integer_big a, b, c;
                a = 1234567;
                b = 2345678;
                c = integer_mult(a, b);

and

                integer_big  c;
                c = integer_mult(1234567, 2345678);

are equivalent and both correct. In this example c won’t be immediate – it will be a socalled disguised handle, which is in fact BETA-h where h is the handle representing the block with c’s value. So an integer big which exceeds BETA is represented via a disguised handle and all the others are immediate. This gives an enormous speed advantage for the arithmetic with small values. – The handle of an integer big i (if not immediate) can be accessed to via the macro inthdl big to handle(i).

In Section 5.2, page 40 is an overview of all functions of the integer package.

3.3 The Real Package

The real package is based on the mp Package of Richard Brent [3] and was transferred to C by the Cayley Group. A good survey on the C-mp Package is given in [2]. Since the mp Package obeys slightly different rules than the rest of the Platform an interface package has been developed. All these functions and macros start with real .

Working with reals (type: t real) requires an additional handle containing the field of real numbers. This can be created via

                handle R;
                R = real_str_create(100);

where 100 is an example for the approximate decimal precision of the real numbers used in the sequel. Every function dealing with t reals expects the appropriate field handle, usually as first parameter.

A t real, say x, is deleted via

                             real delete(&x);

and the real ring R via

                             ring delete(&R);

An overview of the functions and macros dealing with reals is in Section 5.4, page 43.

The ring concept is explained in more detail in Section 3.5, page 16.

3.4 The Polynomial Package

Polynomials (t poly) in the Platform are either simple ring elements (integers, for example) or “real” polynomials over a certain variable. In the latter case the coefficients might be polynomials again – so in the most general case we can handle multivariate polynomials. Although the functions provided by the Platform can also deal with multivariate polynomials we will only refer to univariate ones, since at the moment KANT only needs this special case.

The coefficients of a polynomial are stored in sparse notation, i.e. as pairs of exponent and coefficient. Almost every function expects so-called clean polynomials which have to fulfill the following conditions:

Either:

– it is stored as an integer

or:

– the exponents must be in increasing order,

– the coefficients must be clean polynomials, – the coefficients of the polynomial cannot be zero,

– it must not be a zero-term polynomial,

– it must not be a single-term polynomial with zero exponent.

A semi-clean polynomial satisfies much less strict conditions, namely either

– it is stored as an integer

or:

– the exponents must be in non-decreasing order,

– the coefficients must be clean polynomials.

The function poly z clean() (or poly clean for polynomials over arbitrary rings) takes a single, isolated (having only one reference) semi-clean polynomial, and produces a clean polynomial. This function deletes its argument, returning another polynomial. The argument must be isolated as the polynomial may be modified in site.

All functions in the package must return (either directly, or through pointers) clean polynomials, and expect their arguments to be clean polynomials.

Thus, any functions which create their own polynomials via access to the coefficient/exponent pairs must guarantee their final form to be clean. This is either done by creating a semi-clean polynomial and then calling poly clean or doing the checks by hand (usually as the polynomial is created).

As said above, a t poly might be a simple integer big. This fact is not evaluated by certain macros and functions and one has to be aware of that. So for example the macro m poly coefft(ph, i) expects the handle of a t poly and not the t poly itself, which is usually a disguised handle. In this case, assuming p is a t poly (and not a simple ring element) one has to perform

        c = m_poly_coefft(m_poly_poly_to_handle(p), 1);

or

        t_handle  ph;
        ph = m_poly_poly_to_handle(p);
        c  = m_poly_coefft(ph, 1);

Here c must have been declared appropriately.

In the following example we show how, say, five elements of a dynamic integer array arr, viewed as coefficients of a polynomial, can be moved into a t poly. Let f be a polynomial of degree four:

f(t) = a_{0} + a_{1}t + a_{2}t^{2} + a_{3}t^{3} + a_{4}t^{4}

where for i ∈ {0,1,2,3,4}:

                        dyn arr element(arr, i) = a_{i}.

Then we have to perform:

        t_handle     polh; PZ;
        t_poly       pol;
        t_int        i;
        PZ = structure_pring_z;
        m_poly_u_create_empty(&polh, 5);
        for (i=0; i!=5; ++i)
        {
             m_poly_coefft(polh, i) =
                         integer_incref(dyn_arr_element(arr, i));
             m_poly_expt  (polh, i) = i;
        }
        pol = poly_z_clean(PZ, m_poly_handle_to_poly(polh));

Note that polh is not deleted explicitly because this is already done by poly z clean. – The creation macro m poly u create empty expects as second parameter the number of terms.

Note also that poly z clean expects a polynomial ring as first argument. In this case we took structure pring z which is a global variable pointing on the univariate polynomial ring over ZZ. This ring (and the anlogon vor Q, structure pring q) is initialized in the general KANT startup function kant start.

The general syntax for polynomial functions expects the polynomial ring as first argument, if it does not exist as a global structure it has to be created by poly str create.

A collection of the most important macros accessing t polys is in Section 5.6, page 45. There you will also find a table of the functions dealing with t polys or their handles.

3.5 Linear Algebra

The functions described in this section do not belong to the Platform. They are additional contributions of the Cayley Group to KANT.

Although there are different functions for, say, multiplying integer bigs (integer mult) or t reals (real mult) it is possible to do this in a generic way: There is a generic ring multiplication feature which expects an arbitrary ring (for example ZZ, an order or a real field) and two elements of this ring.

This feature is mainly used by the matrix package of KANT. So two matrices a, b, over a ring R (which can be ZZ, Q or even an order) are multiplied by the function

        c = mat_ring_mult(R, a, b);

If you want to use this feature in a function of your own you should have a look into a

KANT-2 – Macropædia 17

source like for example mat ring mult. The main idea is to set a set function pointers to the actual ring arithmetic functions.

The Anf Package

4.1 Working with KANT data types

4.1.1 Lattices and lattice elements

The lattice package has been developed as a support for the Anf Package. It emphasizes computing elements of small and smallest Euclidean norm and is tailored to the needs of the Fincke/Pohst strategy as described for example in [13].

The header file for the lattice package is lattice.h (which is implicitly #included by kant.h) and it provides the user with three data types:

lattice  (free ZZ-module of IR^{n}, n ∈ ZZ^{>0})
lat enum env (“enumeration environment”)
lat elt  (lattice element).

A lattice can be given via a ZZ-Basis or via a Gram matrix, each defined over integer bigs or t reals. So – assuming id denotes an ideal in an order ord – the lattice of the ideal (under the canonical map) can be created by

                     anf ideal lat(ord,id,&lat,&env);

(see below for env) where the basis of the lattice will be given over the reals with the same precision as in the real values of the order ord. In the case that the number field under consideration is totally real the Gram matrix is integral. This situation will be detected and evaluated adequately by the creation routine.

The enumeration strategy of Fincke/Pohst also needs a Cholesky type decomposition of the Gram matrix. This auxiliary matrix is also contained in the structure and will be computed when necessary. The user can explicitly trigger this computation of the Cholesky matrix by

                lat_chol_calc(lat);

but in practice this is not necessary.

A table of the lattice-related macros is in Section 5.8.1, page 50.

For the creation of a lattice lat (if not done automatically by, for example, anf ideal lat) two things have to be done: First it has to be allocated by

lat = lat_create();

Then the following structure elements have to be set:

lat_rank(lat)
lat_basis(lat)
lat_basis_ring(lat)

or, alternatively,

lat_rank(lat)
lat_gram(lat)
lat_gram_ring(lat)
Here lat basis (and lat gram) is of matrix type with lat rank(lat) columns, and

lat basis ring (or lat gram ring(lat)) is the ring from which the entries of the matrix are taken.

An example for the creation of a lattice whose basis elements are the columns of

( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 0 & 5 \end{matrix} )

is

lattice         lat;
matrix          mat;
t_int   i, j;
mat = mat_new(5, 5);
for (i=1; i!=6; ++i)
{
     for (j=1; j!=6; ++j) mat_elt(mat, i, j) = 0;
     mat_elt(mat, i, i) = i;
}
lat                 = lat_create();
lat_rank(lat)       = 5;
lat_basis(lat)      = mat;
lat_basis_ring(lat) = m_z_str_incref(structure_z);

Note that – when initializing the basis of a lattice – the columns must be ZZ-linearly independent. However, there are also functions of (modified) LLL-type to compute a basis when only a generating system is given.

Attached to a particular lattice is a so-called enumeration environment (lat enum env). This is an interface between the user and the lattice enumeration routine lat enum: The Fincke/Pohst method for the computation of all (x_{1},…, x_{k}) ∈ ZZ^{k} subject to

||∑_{i=1}^{k} x_{i}b_{i}|| ≤ B

(where b_{1},…, b_{k} is a basis of the lattice Λ and B ∈ IR^{>0} a given bound) first computes a Cholesky type decomposition of the matrix whose columns are given by the coefficients of the b_{i}:

∑_{i=1}^{k} q_{ii} (x_{i} + ∑_{j=i+1}^{k} q_{ij}x_{j})^{2} ≤ B

and successively gets bounds for the coefficients x_{k}, x_{k−1},…, x_{1}.

The lat enum env stores the actual situation of the enumeration process in a particular moment. This makes it easy to work with many lattices at a time. Moreover, via macros it is possible to ask lat enum to compute the next coefficient vector or directly a shortest vector ≠ 0. Another possible decision is whether a shortest or a nearest vector (referring to a given reference vector) will be computed.

An application of this feature is the following. For a given order O and an algebraic number α ∈ O, try to compute an element α̃ associate to α such that the conjugates of α̃ are “well conditioned”. This is done by the function anf elt reduce, see Section 5.9.2, page 63.

So far we have four combinations of “requests” to lat enum. There is still another feature: We can influence the order in which the short vectors are computed: The usual method, as described in [13], starts with the maximal possible coefficient for x_{k}, which is

⌊\sqrt{B/q_{nn}}⌋ ,

then computes the bounds for x_{k−1}, x_{k−2},. . .. The last x-vector will be (0,…, 0). We will call this the downwards strategy. If we reverse the order of these vectors we will have vectors with small coefficients (and probably small Euclidean length) first. This upwards strategy is the default strategy for lat enum but there are macros to switch (but please only before starting lat enum).

It is also possible to set additional upper or lower coefficient bounds, see the header file lattice.h for details. A table of the lat enum -macros is in Section 5.8.1, page 50.

A lat enum env for a lattice lat has to be initialized by

                        env = lat enum create(lat);

Certain lattice creation functions (like order lat and anf ideal lat) automatically

create the lat enum env for the lattice.

On page 82 is an example of an application of the lattice package. It computes the algebraic norm of all elements of a given anf ideal whose so-called T_{2}-value is bounded (see [29]).

The enumeration is done by the function lat enum which returns the value TRUE as long as it finds another lat elt. It automatically computes the Cholesky matrix if this has not been done before.

The lattice enumeration technique is explained in detail in [13], [27, pp. 28–30] and [29, pp. 186–191]. The following table maps some of the lat - and lat enum -macros to the notation used in these sources.

[13]  [27]  [29]

           lat rank(l)  m  k  k
           lat basis(l)  B  B  -
           lat gram(l)  A  A  A
           lat chol(l)  Q  Q  Q
           lat disc(l)  -  d(.)  d(.)
           lat succ min(l, i)  -  M_{i}  M_{i}
           lat succ min vec(l, i)  -  -  y_{i}
           lat enum ubound(e)  C  C  C
           lat enum lbound(e)  C’  -  -
           lat enum ref vector(e)  -  ṽ  -
           lat enum coef ubounds user(e)  -  -  -
           lat enum coef lbounds user(e)  -  -  -
           lat enum act real coef(e, i)  x_{i}  z_{i}  x_{i}
           lat enum act length(e)  Q(x)  Q(z)  Q(x)
           lat enum coef lbound(e, i)  -  -  -
           lat enum coef ubound(e, i)  UB(x_{i}) UB(z_{i}) UB(x_{i})
           lat enum part length(e, i)  U_{i}  S_{i}  U_{i}
           lat enum tmp bound(e, i)  T_{i}  T_{i}  T_{i}

Elements of lattices are called lat elts. They are basically coefficient vectors with integer entries, referring to the actual lattice basis. For example, the type of the actual lattice element given by lat enum act coefs(env), as computed by lat enum, is lat elt. The example above shows how to access it. A single integer coefficient of a lat elt called

elt is accessed to via lat elt coef(elt, i).

A table of all lattice related functions can be found in Section 5.8.2, page 51.

4.1.2 Number fields and orders

The number field and order package is the central part of KANT. It enables the user to compute invariants of algebraic number fields and provides a powerful tool for running experiments with number fields easily.

The central datatype of this package is the order which is defined via rules for the arithmetic in the order (for example by using a multiplication table of the basis elements).

Since it may be useful to deal with several orders of a particular number field at a time we introduced the collecting type of an anf (=algebraic number field). Its role is to maintain a table of its orders and, additionally, tables of minimal polynomials of some of its primitive elements. These polynomials might be given over ZZ or over suborders.

The user does not really need to know the existence of anfs. They usually live in the background. As an example let us assume we want to create the maximal order of a number field defined via Q(ρ) where ρ is a root of the t poly pol over Z. We define two

orders:

                order ord1, ord2;

compute the equation order of pol:

                ord1 = order_equation_create(Z, pol);

and then calculate the maximal order, starting with ord1:

                ord2 = order_maximal(ord1);

The quotient field of ord1 and ord2 is of course the same number field. In this example it was created implicitly when computing the equation order of pol. After the calculation of ord2 the anf in the background would contain a table of two orders and one minimal polynomial, together with information about the signature.

Virtually all subsequent arithmetic functions dealing with the order ord1 or ord2 won’t need the anf they belong to. However, it can be retrieved easily by using the macro

order anf(ord1).

Once the orders will be deleted one doesn’t need to care about their anf. It will automatically be deleted, too.

There are very many functions dealing with orders. They are all explained in Section 5.9.2, page 57. The names usually start with order . The most important functions are:

Function name  Explanation
order read  reads an order
order write  prints an order
order pure create  creates an equation order of a pure field
order equation create  creates an equation order
order maximal  computes a maximal order
order find hom  tries to find homomorphisms between orders
order unit group calc  complete unit group of an order

    order torsion subgroup calc torsion subgroup of an order

order units calc  torsion free part of the unit system
order class group calc  class group of a maximal order

Once an order is created one wants (or needs) to perform arithmetical operations with order elements. The problem of assuring that these operations are possible is tackled in the background by KANT. So the user doesn’t need to compute a multiplication table referring to the basis elements explicitly. This is not even the best possibility in all situations: When we have a pure equation order with power basis it is of course better to directly reduce modulo the generator. We have to note at this point that KANT currently only uses multiplication tables of order basis elements, the implementation of special algorithms for equation orders and pure equation orders is planned. But, as said above, the user doesn’t need to know anything about these internals. However, we should mention that the macro

                order_mult_assure(ord);

for a given order ord assures that multiplication between elements of ord is possible from now on.

We now give a survey on the most important features contained in an order structure. The table in Section 5.9.2, page 57 shows how to access these items. We emphasise that of course many of the entries in an order structure might be “empty slots”. It can be checked by macros whether this is the case. These are the features of the order structure:

– the signature

– a handle of the quotient field if known

– flags denoting properties of the order basis and the units of the order given

– a handle of the polynomial (if the order basis is power basis referring to a polynomial over ZZ or another order).

– if the order is given via a transformation matrix ∈ Q^{n×n} referring to another order: the matrix (integral with denominator), the index, the inverse of the matrix and a handle of the suborder

– if the order is a pure equation order with power basis: a handle of the generator – the order discriminant (if known)

– the multiplication table of the order basis elements

– a handle of the coefficient order. This is not necessarily ZZ (for example when considering relative extensions). The entries of the multiplication table are from this coefficient order.

– information about how to represent the 1 in the order

– real approximations of the conjugates of the order basis elements (see Section 4.2.4, page 29 for details)

– a table of generating elements of the unit system given in the order. The unit system might not have maximal rank. Also the logarithm matrix of the units is stored and the regulator (if the rank is maximal).

– a lattice (and even its lat enum env) referring to the logarithms of the units – information about the torsion subgroup of the unit group

– information about the class group structure (of course only if the order is maximal).

Here the class group Cl_{F} = I_{F}/H_{F} is given via a list of ideals a_{1},…, a_{v} where

Cl_{F} = ⟨a_{1}O⟩ ×… ⟨a_{v}O⟩

and the a_{i} are power products of prime ideals ℘_{1},…, ℘_{w}:

∀i ∈ {1,…, v} : a_{i} = ∏_{j=1}^{w} ℘_{j}^{e_{ij}}.

Here the ℘_{j}, the e_{ij} and the orders of the a_{i}O are stored.

– information about orders of subfields. This includes handles to such subfield orders, the relative degree and the basis elements of the subfield orders (but expressed as elements of the actual order).

– additional items to maintain and evaluate the Eimer, see Section 4.2.2, page 27.

The structure of an anf is much less complex.

We have:

– information about the signature (if known)

– a table of minimal polynomials over ZZ

– a table of minimal polynomials over orders

– a table of orders of the field.

4.1.3 Algebraic numbers

An algebraic number (anf elt) cannot live without the order it refers to. Every function dealing with algebraic numbers needs its order ord, usually as first parameter. The functions dealing with algebraic numbers are listed in Section 5.9.2, page 57. We now explain the different ways anf elts can look like.

The first way is that an anf elt is nothing else than an integer big. So it can be understood as generalization of integers which seems to make sense.

The second way (which might be the most usual one) is that an anf elt is represented by an array of coefficients, referring to the basis of ord. The coefficients must be from the “coefficient order” of ord, usually ZZ. There is also a denominator (which is an integer big). So our anf elts are not necessarily elements of ord, they are elements of the quotient field of ord. This explains why we choose the notation anf elt instead of order elt.

The (currently) last possibility is that an anf elt is represented by an array of real approximations of the conjugates of the number (see Section 4.2.4, page 29 for dealing with real numbers). The current presentation of these conjugates avoids dealing with complex numbers. So the conjugates of a primitive, say, algebraic number α are stored in the following way: If n = r_{1} + 2r_{2} is the signature of the current order and if the conjugates α^{(1)},…, α^{(r_{1})} are the real and α^{(r_{1}+1)} = \overline{α^{(r_{1}+r_{2}+1)}},…, α^{(r_{2})} = \overline{α^{(n)}} the nonreal conjugates of α, then the conjugate vector of α is defined to be

α^{(1)},…, α^{(r_{1})}, \sqrt{2} · ℜα^{(r_{1}+1)},… \sqrt{2} · ℜα^{(r_{1}+r_{2})}, \sqrt{2} · ℑα^{(r_{1}+1)},… \sqrt{2} · ℑα^{(r_{1}+r_{2})}.

The reason of the use of \sqrt{2} in this expression is that now the Euclidean length of such a conjugate vector becomes equal to

T_{2}(α) = ∑_{j=1}^{n} |α^{(j)}|^{2}.

Of course there are lots of more ways to express an algebraic number (for example via its minimal polynomial). They are not yet implemented in KANT but this will be done whenever necessary.

Note that all arithmetic routines take care of the possibilities an anf elt can look like. However, if he wants, the user can distinguish these variants and even (try to) convert them into one another.

4.1.4 Ideals

In KANT an ideal (anf ideal) is an object which should be regarded as element rather than as module. Like an anf elt, an anf ideal needs an order to make sure where it comes from. It also can have a denominator (so it might be a fractional ideal).

Up to now there are two ways expressing an ideal:

– via a ZZ-basis which is given in form of an integer matrix with a denominator.

– via a 2-element presentation of two anf elts, the first one is usually an integer big. This might also be a normal presentation (see [29]).

Contrary to the variants of anf elts an anf ideal can be given in both presentations simultaneously. All the arithmetic features dealing with ideals first look whether the ideal is given in the “facvorite” presentation and, if not, might recalculate some of the internals. So for example the function

                anf_elt_in_ideal

(which checks whether an algebraic number is contained in an ideal) prefers the ZZ-basis presentation (where the transformation matrix should be in Hermite form). If the ideal is given in 2-element presentation only, the function automatically calculates the desired Z-basis presentation.

The user has access to all of these presentations and can manipulate them, if he wishes. They are explained in detail in Section 5.9.1, page 56. Further in the same chapter is a table containing all functions dealing with anf ideals, up to now quite a few ways of converting ideals are implemented.

4.1.5 Ceilings

The concept of ceilings has first been introduced by Mahler in [21]. A ceiling can be viewed as an array of positive real numbers λ_{1},…, λ_{n} (n is the absolute degree of the actual order) subject to

∏_{i=1}^{n} λ_{i} = 1.

They are used as weights in very many situations and turned out to be extremely helpful when solving norm equations in number fields [12] or computing units [26]. In KANT an anf ceiling (which belongs to an order) consists of these λ_{1},…, λ_{n} and, additionally, of an integer vector (r_{1},…, r_{n}) which sometimes may contain additional information. These exponents needn’t be touched at all but they are for example evaluated by the norm equation functions of KANT following the method of Fincke. This method starts with a certain lattice (given by the order or an ideal) and successively distorts this lattice by multiplication with certain ceilings (using order lat ceiling mult).

4.2 More sophisticated features of KANT

4.2.1 Constructing overorders

Let F be an algebraic number field. Then it is a non-trivial task to compute the ring of integers of F. This problem has been extensively tracted by Zassenhaus who was the first to give an efficient method to compute the maximal order of F if another order of F is already given. This method is called Round-2 and a variant of it is implemented in KANT. The method is explained in detail in the original paper [39] of Zassenhaus, but also in [27, 10].

The main idea is as follows: One can prove that the global maximal order can be expressed as a sum of finitely many local maximal orders, the so-called p_{i}-maximal orders where {p_{i}} is a list of primes. For all those p_{i} one computes the p_{i}-radical ℘_{i,1} of the starting order O_{0}. The next step is (still for a particular p_{i}) to compute the ring of multipliers O_{i,1} of ℘_{i,1}. It can be shown that either O_{i,1} is a larger order than O_{0} or that O_{i,1} is already p_{i}-maximal. This leads to an iteration procedure eventually yielding p_{i}-maximal overorders for each p_{i}. The sum of these orders is the maximal order.

The table of primes {p_{i}} is usually computed with the help of a factorization of the discriminant of O. This is explained in greater detail in the literature cited above.

The most important functions related to the computation of overorders are (see Section 5.9.2, page 57 for a detailed description):

Function name  Explanation
order maximal  global maximal order
order max p  p-maximal order
order p radical  p-radical of a given order
anf ideal mult ring ring of multipliers of an ideal
order add  addition of two orders of the same field
disc factors get  factorization of order discriminant

One doesn’t really need to know all these functions. So for a given order ord (for example an equation order generated by order equation create(Z, pol) where pol is a monic and irreducible t poly over the ring Z) one can simply create the maximal order by

                ord2 = order_maximal(ord);

This is a generic function in a certain way: It does not necessarily imply that the maximal order is computed by the Round-2 method. It is intended to implement certain features from the Round-4 method of Zassenhaus [22, 29]. They are more efficient for larger degrees (> 10). In future the function will automatically decide which method is the best for the starting order given.

KANT also provides the user with two main programs performing maximal order features: round2.x and ordmax.x, see Section 5.11.2, page 78 for details on using these programs.

4.2.2 Factor basis and relations

The currently best technique for the computation of unit groups and class groups of number fields of arbitrary degree seems to be the so-called Relation Method. A variant of it has been already used by Pohst and Zassenhaus in [28], more elaborate considerations can be found in [5, 14]. We will outline the main idea:

Let {℘_{1},…, ℘_{v}} be a factor basis of prime ideals of an order O (which should be maximal). Let us now assume that we have a table of algebraic numbers {α_{1},…, α_{w}} which decompose into the factor basis, i.e. there exist exponents (e_{ij}) such that

∀j ∈ {1,…, w}: α_{j}O = ∏_{i=1}^{v} ℘_{i}^{e_{ij}}.

We will call equalities of this form relations and the matrix

(e_{ij})_{i∈{1,...,v}, j∈{1,...,w}}

the (actual) relation matrix. Note that every unit yields a relation regardless of which factor basis is given. Note further that column operations on the relation matrix preserve its properties.

Under certain additional assumptions [33] one can derive the class group structure of O from the Hermite normal form of the relation matrix. If unimodular transformations on the relation matrix yield columns consisting only of zeroes these columns refer to units of O.

KANT has many functions manipulating the factor basis and the relation matrix of an order. The user can trigger the evaluation of the relation matrix with respect to computing the class group structure or a system of units (which usually will be a fundamental system).

Since the applications of KANT very often generate algebraic integers of small norm it makes sense to offer a “collecting” function which keeps track of the relations which are found. We will call this feature the Eimer^{1}.

Using the Eimer is very simple. For a given algebraic number alpha of an order ord one has to perform

                anf_elt_factorize(ord, alpha);

which tries to factorize the principal ideal given by alpha into the actual factor basis of the order ord. Here the factor basis has either to be created before by

                order_fac_basis_create(ord, ibnd);

or it is initialized automatically when the first call of anf elt factorize is performed. In the latter case all prime ideals with norm below a default bound (currently 50) are taken.

If anf elt factorize succeeds it will put alpha into the Eimer, store its factorization and return TRUE. In the other case it will simply return FALSE.

The Eimer can then be evaluated: Performing

1german word for bucket

                order_relation_eval_units(ord);

causes KANT to extract all units given explicitly (via units which have been already anf elt factorized) or implicitly (via relations). Before doing this it anf elt factorizes all independent units of ord which are known already. The function then computes a generating system of the units given and writes it (and – if the rank is maximal – its regulator, too) into the order structure of ord.

Another evaluation function is

                order_relation_eval_class_group(ord);

whose task it is to compute the class group structure (or an “estimation” of it) using the Eimer.

These functions are explained in greater detail in Section 5.9.2, page 57. Nevertheless we briefly summarize the most important Eimer-related functions of KANT.

Function name  Explanation

   order fac basis create  create a factor basis

order relations find  construct a certain amount of relations
order units relations  use relation method for units computation
order relation eval units  evaluate Eimer for unit group

   order relation eval class group evaluate Eimer for class group

4.2.3 Subfields

If a number field is non-primitive a typical mathematical approach for computing its properties is first calculating the properties of its subfields, and then trying to transfer the information “up”. In certain cases it is well-known that for example the unit group of a number field has a finite index (which is very often very small) in the group generated by the units of its subfields (see [16, 18]).

KANT is able to deal with subfields or, more precise, with orders of subfields, easily. It provides methods to install homomorphisms between orders and for “lifting” elements to and fro. The detection of a subfield of a number field is in general a very complicated problem and might be tackled in one of the future KANT versions.

Assuming that we have two KANT orders ord1 and ord2, the function

                order_find_hom(ord1, ord2)

tries to embed ord1 into ord2 and returns a logical value indicating its success. The method it uses is sketched in [24]. It tries to find a primitive element of ord1 in ord2 by number geometric methods. The function order find hom is rigorous: When it returns FALSE there is no homomorphism. In the other case it installs a link in the order structure of ord2, pointing to ord1, a table of algebraic numbers of ord2 which are the images of the basis elements of ord1 under the map, and a real transformation matrix for the conversion of conjugate vectors. These macros are listed in the table in Section 5.9.1, page 54.

From now on coercion of elements from ord1 to ord2 is possible. This is done by the general coercion function

                anf_elt_order_coerce(ord1, a, ord2, b).

This function returns a logical value, indicating whether the coercion was successful. In case of an uplift it will be TRUE in any case, but of course not necessarily in case of a downlift.

The aforementioned coercion function can also be used in the case that the orders have a different relation than just one being “direct subfield order” of the other. It also tries to find a chain of homomorphisms between the two orders and applies the mappings found. Finally, it also works if the orders are connected via one being coefficient order of the other or if they are orders of the same number field.

If anf elt order coerce is called without a homomorphism being installed – no worries, this function tries to install one by calling order find hom.

As said above, KANT does not yet have a function detecting subfields – it is only able to install homomorphisms, provided the user offers KANT two orders. However, the function order find subfield orders dirty tries to find a few subfield orders by a rude method without any guarantee of finding all.

4.2.4 Dealing with real numbers

Dealing with real numbers means leaving the exact area of integers. One has to be aware of that when choosing the precision of the real numbers. As far as orders and their datae are concerned, KANT gives some support of how not to loose precision.

Certain KANT features need approximations of the conjugates of the order basis elements. This for example applies to the function order units logs calc. Functions of this type perform

                order_reals_assure(ord);

which is a macro assuring that these real values can be accessed to. Every order ord has an item

                order_reals(ord);

which is a handle of a real field with a real precision of (default) 20 decimal digits. One can (re-)set this precision by

                order_reals_set(ord, p);

where p is the number of decimal digits wanted. The function

                order_reals_create(ord);

then (re-)calculates all real values (including the conjugates of the basis and the logarithms of the units) with the precision set before.

So one has two possibilities. The first one is not to care about it and letting KANT automatically perform its real calculations with 20 digits precision.

The second is to deliberately (re-)set the precision by

                order_reals_set(ord, p);
                order_reals_create(ord);

Once a particular precision has been choosen KANT might automatically reset it. At the moment this only applies to the two functions

                anf_elt_minpoly
                order_relation_eval_units

Both of these functions reset the precision of the real order values when they find out that it might not be exact enough.

You also can set the precision when reading an order, see Section 4.3.5, page 36. A good “rule of thumb” is – if units are involved – to set the precision to at least 20 digits higher than the number of digits of the “largest unit”.

4.3 Developing KANT programs

4.3.1 Main Rules for KANT programmers

(1) Every KANT source file must #include "kant.h".

(2) You have to initialize a main KANT program by

                     kant_start();

(3) You are responsible for the deletion of variables when not needed anymore. The table on page 40 also includes the deletion macros.

(4) You are responsible for allocating space for your variables – unless they are returned by functions. In this case the functions allocate the space themselves. A table for allocation functions and macros is on page 40.

(5) The first declaration statement in every function and main program should be

                     block_declarations;

4.3.2 Developing functions

There are not many rules you have to obey when writing a new function for KANT.

(1) It should #include "kant.h", the meta header file which defines the Anf Package and the interface to the Platform.

(2) The first declaration statement should be block declarations;. This is necessary if you use any incref- or delref-macros.

(3) Please keep in mind the incref/delref concept as outlined in Section 3.1, page 12. This especially means that everything what has been created by a function call or by an incref macro has to be deleted again. For deletion macros see Section 5.1, page 40.

We now list a complete KANT function.^{2} It computes the representation matrix of an algebraic integer (whose denominator must be 1).

#include "kant.h"
matrix
anf_rep_mat (ord, alpha)
order    ord;
anf_elt  alpha;
{
block_declarations;
t_int           i, j, k, deg;
matrix          mat;
anf_elt         accu, temp1, temp2;
order           ordcoef;
/*
Is the order equal Z?
*/
if (ring_type(ord) == RING_Z)
{
    mat = mat_new(1,1);
    mat_elt(mat, 1, 1) = integer_incref(alpha);
    return mat;
}
deg     = order_rel_degree(ord);
ordcoef = order_coef_order(ord);
/*
Is alpha an integer? In this case the result is a
diagonal matrix.
*/
if (anf_elt_is_integer(alpha))
{
    mat = mat_ring_create_zero(ordcoef, deg);
    for (i=1; i!=deg+1; ++i)
          mat_elt(mat,i,i) = integer_incref(alpha);
    return mat;
}
order_mult_assure(ord);
/*
Allocation

2Since I took a few useful features from the GAP manual [35] redefining the < symbol strange things happen when I try to use < within a verbatim environment. So I now wrote != instead. We work on that.

*/
        mat = mat_new(deg, deg);
/*
    Loop for matrix elements. The representation matrix is the
    scalar product of the coefficient vector of alpha times
    the array of multiplication matrices in the multiplication table.
*/
        for (i=1; i!=deg+1; ++i)
        {
            for (j=1; j!=deg+1; ++j)
            {
                accu = 0;
                for (k=1; k!=deg+1; ++k)
                {
                     temp1 = accu;
                     temp2 = anf_elt_mult(ordcoef, anf_elt_coef(alpha,k),
                     mat_elt(order_mult_matrix(ord,k), i, j));
                     accu  = anf_elt_add(ordcoef, temp1, temp2);
                     anf_elt_delete(ordcoef, &temp1);
                     anf_elt_delete(ordcoef, &temp2);
                }
                mat_elt(mat, i, j) = accu;
            }
        }
        return mat;
}

4.3.3 Developing main programs

The development of a main program is underlying the same rules as the development of functions as explained in the preceding section. Additionally, you have to startup KANT via a single call

                kant_start();

This function initializes MEM and the mp Package. In addition, it creates four global structures which now can be used in every KANT function:

name explanation

                        structure z  ZZ
                        structure q Q

structure pring z polynomial ring over ZZ
structure pring q polynomial ring over Q

Examples for main programs are in Section 6, page 82.

4.3.4 Debugging

Debugging a KANT program is nothing else but debugging a C-program. So if you are used to a particular debugger it may help you. It would be of great help if you could call KANT or Platform functions from the debugger level. Especially MEM has got a lot of useful features which easily help finding leaks in a program complex. In Section 5.12, page 79 is a table of the most important debugging features of MEM.

4.3.5 Input and Output

The I/O-interface of KANT-2 is not yet developed very far. The following table shows which functions are available at the moment:

Type  Input  Output

  integer big     a = integer read(strng)        integer write(a)
  rational  –  q write(r)
  t real                                        real write(R, x, width)
  t comp                                        comp write(CR, x, width)
  t poly          p = poly order read(ord, deg)  poly z write(PZ, ipol)
  matrix          mat = mat anf read(ord, dim)   mat ring write(R, mat)
  vector                                        mat ring write(R, vec)
  dyn arr handle                                 dyn int arr print(int arr)
  anf                                           anf dump(anf)

  order

                 order read(&ord)
                 order read v1(&ord)

                                                order write(ord)
                                                order dump(ord)
  anf elt         alpha = anf elt read(ord)

                                                anf elt write(ord, alpha)
                                                anf elt dump(ord, alpha)
  anf ideal       id = anf ideal 2 read(ord)

                                                anf ideal 2 write(ord, id)
                                                anf ideal z write(ord, id)

The function order read needs more explanation. It provides the user with a technique to read an order of an algebraic number field and is almost completely compatible to the KANT-1 routines COMINP and CMOUT2^{3}. At the moment order read only supports two certain types of orders:

– given as equation order of a polynomial over ZZ which is monic and irreducible

– given via a transformation matrix ∈ Q^{n×n} referring to an order of the first type.

A sample input file for an order of the first type is

(F=)

a_{n−1} a_{n−2} ⋯ a_{0}

(END=)

which describes the equation order of the polynomial

f(t) = t^{n} + a_{n−1}t^{n−1} + ⋯ + a_{0}.

3Here I would like to say “See the KANT-1 manual for further details on these formats” – unfortunately there is no KANT-1 manual.

Here the coefficients might have arbitrary many digits and have to be separated by anything which is no digit or sign.

In case using this format by the old KANT-1 one must separate the coefficients by commas.

A more general way of describing an order is the (FLD=)-format which is used by the routine order write as well. An example is

(FLD=)   4,  2,  3,  0,  2,  3,  0, 16,  0,  0,  4,   *
-2 -93 94 -1
1 0 0 0 1
-80 178 3 -2 19
-99 197 3 -2 19
-397 -108 8 1 19
5 0 1 0
-4 -1 0 0
0 1 1 0
16 3 2 2 4
4
1 17 12 -1 1 0 1
1 5 4 -1 1 0 1
2 3 1 -1 2 2 1
2 2 0 0 1 0 1
1 0 0 0
0 0 1 0
0 1 0 1

The first line is a command line containing data describing how the order is coded by the subsequent lines. The eleven (compulsory) flags following the string (FLD=) contain the following information:

Flag #0: absolute degree over Q

Flag #1: \underline{if -1 or 1}: The order is an equation order and the basis is power basis. \underline{if -2 or 2}: The order is given via a transformation matrix referring to a power basis. \underline{if positive}: The order is the maximal order.

Flag #2: number of independent units given

Flag #3: (obsolete)

Flag #4: \underline{if positive}: order of the torsion subgroup

Flag #5: \underline{if equal to Flag #2}: The units are fundamental units.

Flag #6: (obsolete)

Flag #7: \underline{if non-zero}: The class group structure is given.

Flag #8: (obsolete)

Flag #9: (obsolete)

Flag #10: \underline{if positive}: Number of real places of the field (optional).

The number and contents of the lines following the command line is dependent on the information announced by the Flags in the (FLD=)-line. They are in particular:

– n coefficients of a monic and irreducible polynomial over ZZ, starting with the coefficient of the second highest power of t, ending with the coefficient of t^{0}.

– \underline{if Flag #1 is -2 or 2}: The following n lines contain the transformation matrix describing a ZZ-Basis of the order. Each line has n + 1 entries:

a_{0},…, a_{n−1}, d

which is to be read that

\frac{1}{d} ∑_{i=0}^{n−1} a_{i}ρ^{i}

is a basis element ω_{j} (j ∈ {1,…, n}). Here ρ denotes a zero of the polynomial defined in the second line.

– \underline{if Flag #2 is positive}: The units announced above are now given, each in a row. A unit is described via its n coefficients referring to the basis.

– \underline{if Flag #4 is larger than 2}: The following line contains the coefficients of a generator of the torsion subgroup.

– \underline{if Flag #7 is non-zero and not 1}: the next lines describe the class group structure in the following way: First line: Class number, number of cyclic factors of the class group, orders of these cyclic factors. Next line: Number of prime ideals used for the presentation of the class group generators Next line(s): The prime ideals in 2-Element presentation (degree, first generator and second generator with denominator). Next line(s): Exponent array(s); each one attached to the array of prime ideals yields an ideal from one of the ideal classes which generate the cyclic factors of the class group.

The (FLD=)-format might be somewhat cryptic – usually one would start with an equation order which is much easier to type in by using the (F=)-format explained before. On the other hand the (FLD=)-format is compatible with the output function order write which thus produces an output which can be read by order read.

So we now can “decode” the order given on page 34:

We consider a totally real quartic number field F. A generating polynomial of F is:

f(t) = t^{4} − 2t^{3} − 93t^{2} + 94t − 1.

An integral basis ω_{1}, ω_{2}, ω_{3}, ω_{4} (referring to a root ρ of f) is given by:

\begin{aligned}ω_{1} & = & 1 \\ ω_{2} & = & (−80 + 178ρ + 3ρ^{2} − 2ρ^{3})/19 \\ ω_{3} & = & (−99 + 197ρ + 3ρ^{2} − 2ρ^{3})/19 \\ ω_{4} & = & (−397 − 108ρ + 8ρ^{2} + ρ^{3})/19 \end{aligned}

A system of fundamental units is:

\begin{aligned}η_{1} & = & 5ω_{1} + ω_{3} \\ η_{2} & = & −4ω_{1} − ω_{2} \\ η_{3} & = & ω_{2} + ω_{3} \end{aligned}

The class number of F is 16 and the class group is isomorphic to

ZZ_{2} × ZZ_{2} × ZZ_{4}.

Let now:

℘_{1} = 17o_{F} +  (12ω_{1} − ω_{2} + ω_{3})o_{F}  (norm=17)
℘_{2} = 5o_{F} +  (4ω_{1} − ω_{2} + ω_{3})o_{F}  (norm=5)
℘_{3} = 3o_{F} + (ω_{1} − ω_{2} + 2ω_{3} + 2ω_{4})o_{F}  (norm=3^{2})
℘_{4} = 2o_{F} +  (ω_{3})o_{F}  (norm=2^{2}).

Then the cyclic factors of the class group are generated by the classes of

℘_{1} (order: 2)
℘_{3} (order: 2)
℘_{2}℘_{4} (order: 4).

(By the way, the field discriminant is 78145600 and the regulator approximately 46.42436.)

There are two more features of order read worthwile to explain. One is employed by the two lines

(TSTFLG=)
t

before any (F=) or (FLD=) command. Here t is a non-negative small integer. It causes some of the KANT functions to produce intermediate output – the size of t determines the amount of output. Usually t=1 or t=2 gives a nice survey of what happens in between.

The second feature is the command

(PRECIS=)
p

where p is an integer greater than or equal to 20. Also this command has to be given before the input of an order (before or after a (TSTFLG=) command). The (PRECIS=) command causes order read to perform

                         order reals set(ord, p);

which means that all subsequent real computations within the order will be carried out with decimal precision of at least p, see Section 4.2.4, page 29.

4.3.6 Interface to KANT-1

KANT-2 is written entirely in C whereas the implementation language of KANT-1 is Fortran. So any communication between KANT-1 and KANT-2 on programming level has to be done via non-standard features. The only communication routine written up to now is order read v1 which has the same syntax as order read. It indirectly calls the KANT-1 input routine COMINP and initializes an order appropriately. Since order read has almost entirely the same features (exception: Reading units in “long” KANT-1 format) the subroutine order read v1 has now become practically obsolete.

However, KANT-2 includes a main program v1 to v2.x whose task is to KANT-1-COMINP-read an order and then to KANT-2-order write it. The only use of this program is to convert “long units” of KANT-1 to the syntax of KANT-2.

Data types, functions and macros

We here intend to list every macro or function which may be of use for KANT programmers. This is not yet realized, so there will be some situations in which you still have to look into the sources and header files.

5.1 The data types of KANT (and the Platform)

We give a short summary of the data types of KANT and the Platform, together with deletion and creation routines.

These are the data types KANT employs:

t int:

Nothing else than the ordinary C-type int. t ints needn’t be allocated or deleted. The absolute value is bounded by BETA, currently 2^{29}.

integer big:

The main integer type of KANT and the Platform. Either an immediate integer or a disguised handle = BETA+h where h is the handle.

t real:

Arbitrary precision real data type.

t comp:

Arbitrary precision complex data type.

t poly:

Polynomials ober arbitrary rings, stored in sparse representation.

matrix:

Generic matrix type with arbitrary coefficients.

vector:

Generic vector type. Currently built upon the matrix type.

dyn arr handle:

Dynamic arrays of arbitrary length. Note that for the deletion first the entries and then the array itself must be deleted.

rings:

Arbitrary rings, declared as handle.

lattice:

The KANT lattice type.

lat elt:

Elements of lattices.

lat enum env:

Enumeration environment for a lattice. Tailored for the needs of the Fincke/Pohst enumeration technique [13].

anf:

Algebraic number field. Mainly used in the background by KANT functions.

order:

The central KANT-2 data type. Contains (or should contain) all valuable information about orders one could think of.

anf elt:

Element of an algebraic number field. Might also be an integer big. If not, it is given as a disguised handle. Usually refers to an order basis – so arithmetic routines for anf elts also expect an order. An anf elt can also be a vector of its conjugates.

anf ideal:

Ideal of an algebraic number field. Might be presentated via 2 elements or via a ZZ-Basis (or in both ways).

anf ceiling:

Ceiling of an algebraic number field.

We now summarize allocation and deletion functions and macros. Note that every routine returning a particular type allocates the space itself.

Type  Creation  Deletion

t int  –  –

integer big

i=conv double to int round(d)
i=conv real to int round(R,r)
i=conv real to int ceil(R,r)

                                     integer delref(i)

t real

r=conv int to real(R,i)
r=conv real to real(ROLD, rold, RNEW)
r=comp re(R, c)
r=comp im(R, c)

                                     real delete(&r)

t comp

c=comp make(R,re,im)
c=conv int to comp(C,i)
c=conv real to comp(C,r)
c=conv comp to comp(cold,CNEW)

                                     comp delete(&c)

t poly           p=m poly u create empty(&p, Ntrms)

                                     m poly z delref(PZ, p)
                                     m modpoly delref(PR, p)
                                     poly elt delete(PR, &p)

matrix

x=mat new(n1,n2)
m=mat ring create zero(R,n)
m=mat ring create id(R,n)
m=mat ring create minus1(R,n)

                                     mat delref(R, &m)

vector          v=vec new(n)                          vec delete(R, &v)

dyn arr handle

a=dyn arr alloc(len)
dyn arr assure space(a,req,minext)

first: delete entries

                                     then: dyn arr delete(&a)

t handle (rings)

Zm=zm ring create(m)
R=real str create(prec)
PR = poly str create(CR, rank)

globals (see Section 4.3.3, page 32)

                                     ring delete(&R)
                                     poly str delete(0, &CR)

lattice

l=lat create()
order lat(ord,&l,&env)
anf ideal lat(ord,id,&l,&env)

                                     lat delete(&l)

lat elt          lat elt alloc(e,k)                    lat elt delete(l,&e)
lat enum env     env=lat enum create(l)                lat enum delete(l,&env)
anf             f=anf create()                        anf delete(&f)

order

o=order create(f,ordc,n,poly pos)
o=order create pure(ordc,a,n)
o=order equation create(ordc,pol)

                                     ring delete(&o)

anf elt

anf elt alloc(a,deg)
a=lat elt to anf elt(l,e,ord)
a=lat elt ideal to anf elt(l,e,o,id)

                                     anf elt delete(ord, &a)

anf ideal

id=anf ideal alloc()
id=anf ideal 2 create(ord, a, b)
id=anf ideal z create(ord,trans,den)

                                     anf ideal delete(ord,&id)

anf ceiling

ceil=anf ceiling alloc(ord)
ceil=anf elt ceiling(ord,alpha)

                                     anf ceiling delete(o,&c)

5.2 The Integer Package

For clarity reasons we omit the types of the arguments since they are obvious in most of the cases. In some situations it might be necessary to have a look in the source code.

Functions whose names begin with modint refer to operations modulo integer bigs.

Type  Syntax

t logical    anf elt is integer sub(ord, alpha, &a)
integer big  conv double to int round(d)
t comp       conv int to comp(CR, a)
double       conv int to double(a)
t real       conv int to real(a)
integer big  conv real to int ceil(R, r)
integer big  conv real to int floor(R, r)
integer big  conv real to int round(R, r)
integer big  i next prime(a, proof)
integer big  i previous prime(a, proof)
integer big  integer abs(a)
integer big  integer add(a, b)
anf elt      integer anf elt lift(ord, a)
integer big  integer carmichael lambda(a)
t int        integer compare(a, b)
integer big  integer div(a, b)
t void       integer euclid(a, b, &gcd, &s, &t, &u, &v)
integer big  integer gcd(a, b)
t void       integer gcd mult(a, b, &gcd, &m1, &m2)
t logical    integer is prime(n, cert, wantcert, trbnd)
t logical    integer is prime small(n)
t logical    integer is prime 25E9(n)
t logical    integer is squarefree(n)
t int        integer jacobi symbol(d, n)
integer big  integer lcm(a, b)
t void       integer lcm gcd(a, b, &lcm, &gcd)
t void       integer least prime divisor(n, &p, &e, &m)
t int        integer log2(a)
integer big  integer long random(n)
t void       integer lst factorise(n,&f,&rem,mra,trbnd,rit,0,0,0,0,bnd,prf)
Example:  integer lst factorise(n,&flst,&rem,50,1000,10000,0,0,0,0,n,0)
integer big  integer matrix gcd(Z, mat)
integer big  integer max(a, b)
integer big  integer min(a, b)
t int        integer moebius mu(a)
integer big  integer mult(a, b)
integer big  integer negate(a)
integer big  integer nfactorial(a)
t int        integer num decimal digits(iabs)
t int        integer num partitions(a)
t int        integer num prime divisors(a)
integer big  integer power(a, n)
t void       integer ppart(m, flag, p, &n, &exact)
t int        integer prime exponent(p, n)

KANT-2 – Micropædia 42

Type  Syntax

t int           integer prime val(n, p)
t int           integer prime val div(&n, p)
t void          integer prod factorise(list, len, &facts)
t void          integer quot rem(a, b, &q, &r)
integer big     integer read(str)
dyn arr handle  integer read primes(bound)
t void          integer root(a, n, &root, &sign)
t int           integer sign(a)
integer big     integer solve congruence(a, b, m)
t void          integer sqrt(a, &sqrt, &sign)
integer big     integer subtract(a, b)
t void          integer write(a)
integer big     modint add(q, a, b)
integer big     modint div(q, a, b)
integer big     modint hom(q, a)
integer big     modint invert(q, a)
integer big     modint mult(q, a, b)
integer big     modint negate(q, a)
integer big     modint subtract(q, a, b)
integer big     modint exp(q, a, power)
t int           utl rand int(lo, hi)

5.3 The Rationals

The rational functions need a rational field, say Q, as first argument. One can use the global structure structure q for Q.

Type  Syntax

            rational     integer to q(Q, i)
            rational     q abs(Q, r)
            rational     q add(Q, r1, r2)
            integer big  q ceil(Q, r)
            t int        q compare(Q, r1, r2)
            t void       q delref(r)
            rational     q divide(Q, r1, r2)
            t logical    q eq(Q, r1, r2)
            integer big  q floor(Q, r)
            t logical    q ge(Q, r1, r2)
            t logical    q gt(Q, r1, r2)
            rational     q int add(Q, r, i)
            rational     q int mult(Q, r, i)
            rational     q inverse(Q, r)
            t logical    q is minus one(Q, r1)
            t logical    q is one(Q, r1)
            t logical    q le(Q, r1, r2)

KANT-2 – Micropædia 43

Type  Syntax

     t logical    q lt(Q, r1, r2)
     rational     q make(Q, num, den)
     rational     q max(Q, r1, r2)
     rational     q min(Q, r1, r2)
     rational     q mult(Q, r1, r2)
     rational     q negate(Q, r)
     rational     q power(Q, r1, iexp)
     integer big  q round(Q, r)
     t int        q sign(Q, r)
     rational     q subtract(Q, r1, r2)
     t void       q write(r)

5.4 The Real Package

The first argument of the real functions is usually the field where the elements live in. This field can be created by the function

 R = real_str_create(p);

whith p being the actual precision.

Type  Syntax

t real       comp im(R, c)
t real       comp re(R, c)
t real       conv double to real(d)
t real       conv int to real(i)
t comp       conv real to comp(CR, a)
double       conv real to double(R, a)
integer big  conv real to int ceil(R, a)
integer big  conv real to int floor(R, a)
integer big  conv real to int round(R, a)
t real       conv real to real(OLDR, a, NEWR)
t real       real abs(R, a)
t real       real add(R, a, b)
t real       real arcsech(R, a)
t real       real arcsinh(R, a)
t real       real arccosech(R, a)
t real       real arccosh(R, a)
t real       real arccoth(R, a)
t real       real arctanh(R, a)
t real       real besj(R, x, nu)
t real       real catalan(R)
t int        real compare(R, a, b)
t int        real compare eps(R, a, b, eps)
t real       real daw(R, a)

KANT-2 – Micropædia 44

Type  Syntax

t real     real divide(R, a, b)
t real     real ei(R, a)
t logical  real eq(R, a, b)
t logical  real eq eps(R, a, b, eps)
t real     real erf(R, a)
t real     real erfc(R, a)
t real     real euler(R)
t real     real exp(R, a)
t real     real gamma(R, a)
t logical  real ge(R, r1, r2)
t logical  real gt(R, r1, r2)
t real     real inverse(R, a)
t logical  real le(R, r1, r2)
t real     real li(R, a)
t real     real log(R, a)
t real     real logb(R, b, a)
t real     real log gamma(R, a)
t logical  real lt(R, r1, r2)
t real     real make(R)
t real     real mult(R, a, b)
t real     real negate(R, a)
t real     real pi(R)
t real     real power(R, a, iexp)
t real     real real power(R, a, b)
t real     real root(R, a, n)
t int      real sign(R, a)
t real     real sqrt(R, a)
t handle   real str create(prec)
t void     real str delete(0, &R)
t real     real subtract(R, a, b)
t void     real write(R, a, width)
t real     real zeta(R, n)
t real     real compare eps(R)
t real     real eq eps(R)

5.5 The Complex Package

The complex numbers are designed similarly ro as the reals. Here the field creation function

is comp str create.

Type Syntax

t comp  comp add(C, c1, c2)
t real  comp arg(C, c)
t void  comp cart to polar(C, are, aim, &amod, &arg)
t comp  comp conjugate(C, c)
t comp  comp divide(C, c1, c2)

Type  Syntax

t logical  comp eq(C, a, b)
t real     comp im(C, c)
t comp     comp inverse(C, c)
t comp     comp make(C, re, im)
t comp     comp minus one(C)
t real     comp modulus(C, c)
t comp     comp mult(C, c1, c2)
t comp     comp negate(C, c)
t real     comp norm(C, c)
t comp     comp one(C)
t comp     comp power(C, c, n)
t void     comp polar to cart(C, amod, arg, &are, &aim)
t real     comp re(C, c)
t comp     comp sqrt(C, c)
t handle   comp str create(prec)
t void     comp str delete(0, &C)
t comp     comp subtract(C, c1, c2)
t void     comp write(C, c, width)
t comp     comp zero(C)

5.6 Polynomials

This section can only give a rough overview on the polynomial features. If one really wants to write polynomial code one definitely needs a look into a few source files.

Note that in the following tables a parameter ending with h denotes a handle of a polynomial and not a t poly.

The names of the macros and functions start with:

poly z : for polynomials over ZZ. poly : for arbitrary polynomials. modpoly : for polynomials over ZZ/mZZ. poly u zm : for univariate polynomials over ZZ/mZZ.

Note: In the following tables we will identify PZ with structure pring z and PR with an arbitrary polynomial ring.

We first list the macros accessing t polys respectively their handles. Here poly deg is also listed in the macro table although it is actually a function.

macro name  explanation
m poly z delref(PZ, p)  deletes a polynomial over ZZ
m poly z incref(PZ, p)  increment of reference count of polynomial over ZZ
poly deg(p)  degree of a polynomial

m poly u create empty(&ph, nt) Create a univariate t poly
m poly coefft(ph, i)  i-th coefficient

macro name  explanation

m poly expt(ph, i)  i-th exponent
m poly handle to poly(p) converts handle to a t poly

m poly poly to handle(p) returns handle of a polynomial
m poly is const(p)  checks whether p is a ring element
m poly is poly(p)  excludes p being a ring element

m poly is small int(p)  checks whether p is an t int

m poly nterms(ph)  returns number of terms of a polynomial

These are the most common polynomial functions:

Type  Syntax

t poly     anf elt minpoly(ord, alpha)
t poly     anf poly zeroes(anf, R, index)
t poly     dyn arr to poly(R, arr)
t poly     modpoly add(PR, m, f, g)
t poly     modpoly div(PR, m, f, g)
t poly     modpoly evaluate(PR, m, f, numvar, aint)
t poly     modpoly evaluate princvar(PR, m, f, aint)
t poly     modpoly exp(PR, m, f, power)
t poly     modpoly hom(PR, m, f)
t poly     modpoly integer div(PR, m, f, aint)
t poly     modpoly interpolate(PR, m, B, b, Bp, Apol, A1pol)
t poly     modpoly max norm(PR, m, f)
t poly     modpoly monic(PR, m, f)
t poly     modpoly mult(PR, m, f, g)
t poly     modpoly negate(PR, m, f)
t poly     modpoly quot rem(PR, m,f,g,&p,&q)
t poly     modpoly resultant(PR, m, f, g)
t poly     modpoly subtract(PR, m, f, g)
t poly     modpoly sum norm(PR, m, f)
t poly     modpoly uni cont(PR, m, f)
t poly     modpoly uni quot(PR, m, f, unipol)
t poly     poly add(PR, f, g)
t poly     poly clean(PR, f)
t poly     poly copy poly(PR, f)
t int      poly deg(f)
t poly     poly deriv princvar(PR, f)
t logical  poly eq(PR, f, g)
t poly     poly evaluate(PR, f, i, a)
t poly     poly exp(PR, f, aint)
t poly     poly gcd(PR, f, g)
t poly     poly handle delete(PR, fh)
t logical  poly is minus one(PR, f)
t logical  poly is one(PR, f)
t logical  poly is zero(PR, f)

Type  Syntax

t poly          poly lcm(PR, f, g)
t poly          poly mult(PR, f, g)
t poly          poly negate(PR, f)
t poly          poly power(PR, f, i)
t poly          poly order read(ord, deg)
t void          poly quot rem(PR, f, g, &q, &r)
t poly          poly scalar add(PR, f, num)
t handle        poly str create(Rng, rank)
t handle        poly str delete(0, &PR)
t poly          poly subtract(PR, f, g)
anf elt         poly to anf elt(ord, f)
dyn arr handle  poly to dyn arr(R, f)
t void          poly u z factorize(PR, m, f, &sgn, &icnt, &facs)
t poly          poly u zm deriv(PR, m, f)
t int           poly u zm different(PR, m, f, g)
t poly          poly u zm div(PR, m, f, g)
t handle        poly u zm fact(PR, m, f)
t handle        poly u zm factorize(PR, f)
t poly          poly u zm gcd(PR, m, f, g)
t void          poly u zm hensel lemma(PR,m,f,A1,B1,S1,T1,M,C,&A,&B)
t poly          poly u zm mult(PR, m, f, g)
t poly          poly u zm nat rem(PR, m, f, g)
t logical       poly u zm reducible(PR, m, f)
t int           poly u zm resultant(PR, m, f, g)
t void          poly xgcd(PR, f, g, &gcd, &s, &t,&u,&v)
t poly          poly z Qmatrix write()
t poly          poly z abs(PZ, f)
t poly          poly z add(PZ, f, g)
t poly          poly z clean(PZ, f)
integer big     poly z const chim rem(m1, m2, m1d, a1, a2)
t poly          poly z copy poly(PZ, f)
t logical       poly z dedekind test(PZ, f, modul)
t void          poly z denom simplify(PZ, &f,&den)
t logical       poly z different(PZ, f, g)
integer big     poly z discriminant(PZ, f)
t poly          poly z div(PZ, f, g)
t poly          poly z evaluate(PZ, f, numvar, aint)
t poly          poly z eval princvar(PZ, f, aint)
t poly          poly z exp(PZ, f, iexp)
t handle        poly z factorize(PR, f)
t poly          poly z gcd(PZ, p1, p2)
integer big     poly z integer content(PZ, f)
t poly          poly z integer div(PZ, f, aint)

Type  Syntax

t poly       poly z integer mult(PZ, f, aint)
t poly       poly z ith deriv(PZ, f, i)
t poly       poly z lead coefft(PZ, f)
integer big  poly z max norm(PZ, f)
t poly       poly z mult(PZ, f, g)
t poly       poly z negate(PZ, f)
t poly       poly z pseudo rem(PZ, f, g)
t void       poly z quot denom(PZ, f, df, g, dg, &q, &dq, &r, &dr)
t void       poly z quot rem(PZ, f, g, &q, &p)
t poly       poly z random(PZ, deg, m)
integer big  poly z red discriminant(PZ, f)
integer big  poly z red resultant(PZ, f, g)
t poly       poly z reductum(PZ, f)
integer big  poly z resultant(PZ, f, g)
t int        poly z sign(PZ, f)
integer big  poly z sum norm(PZ, f)
t poly       poly z subtract(PZ, f, g)
t void       poly z write(PZ, f)
t poly       poly zm add(PR, f, g)
integer big  poly zm discriminant(PR, f)
t poly       poly zm div(PR, f, g)
t poly       poly zm eval princvar(PR, f, aint)
t poly       poly zm evaluate(PR, f, numvar, aint)
t poly       poly zm exp(PR, f, iexp)
t poly       poly zm gcd(PR, p1, p2)
t poly       poly zm integer mult(PR, f, aint)
t poly       poly zm ith deriv(PR, f, i)
t void       poly zm quot rem(PR, f, g, &q, &p)
t poly       poly zm random(PR, deg, m)
integer big  poly zm resultant(PR, f, g)
t poly       poly zm scalar add(PR, f, num)
t poly       poly zm scalar div(PR, f, num)
t poly       poly zm subtract(PR, f, g)

It is in addition possible to do computations in factor rings over arbitrary polynomial rings. The names of the functions performing these operations start with principal ideal . See the actual KANT directory for more information.

5.7 Linear Algebra

In this section we summarize the (mostly) generic linear algebra features as provided by the Platform Extension. Note that some of the routines (for example LLL-type functions) do not work for all ring types.

Type  Syntax

t void      lll int d reduce(Z, b, delta, &bh, &trans)
t void      lll real d reduce(R, b, delta, &bh, &trans)
t void      mat ring col add(R, m, a, b, mult, from, to)
t void      mat ring col mult(R, m, a, mult, from, to)
t void      mat ring col swap(R, m, a, b, from, to)
vector      mat ring col to vector(R, m, colno)
matrix      mat ring compwise mult(R, m1, m2)
matrix      mat ring copy(R, m)
matrix      mat ring create id(R, dim)
matrix      mat ring create minus1(R, dim)
matrix      mat ring create zero(R, dim)
t ring elt  mat ring det(R, m)
t void      mat ring echelon(R,a,&d,&rank,&ech,&un,istr,&tr,isi,st)
matrix      mat ring gram(R, m)
matrix      mat ring gram chol(Rg, gram, Rc)
matrix      mat ring hnf col(R, m)
matrix      mat ring hnf col upper(R, m)
matrix      mat ring col hnf mod(R, m, q)
matrix      mat ring hnf mod upper(R, m, q)
matrix      mat ring hnf row(R, m)
matrix      mat ring insert(R, R, msource, mtarget, row, col)
matrix      mat ring inverse(R, m)
t logical   mat ring is one(R, m)
t logical   mat ring is zero(R, m)
matrix      mat ring make square mat(R, m)
t void      mat ring mlll reduce(R, m, eps, &rank, &ml, &trans)
matrix      mat ring mult(R, m1, m2)
matrix      mat ring negate(R, m1)
t void      mat ring row add(R, m, a, b, mult, from, to)
t void      mat ring row mult(R, m, a, mult, from, to)
t void      mat ring row swap(R, m, a, b, from, to)
matrix      mat ring scalar left mult(R, aelt, m)
matrix      mat ring scalar right mult(R, m, aelt)
matrix      mat ring submat(R, m, row, col, nrows, ncols)
matrix      mat ring subtract(R, m1, m2)
t ring elt  mat ring trace(R, m)
matrix      mat ring trans(R, m)
t void      mat ring write(R, m)
t void      ring delete(&R)
t void      ring elt delete(R, &a)
t ring elt  ring elt incref(R, a)

5.8 lattices, lat elts and lat enum envs

This is a survey of all functions and subroutines (and certain macros) referring to lattices. For functions referring to lattices and orders (conversion routines) see Section 5.10, page

KANT-2 – Micropædia 50

5.8.1 lattice macros

We first give a summary of the macros which access the structure elements of a lattice.

macro name  explanation

lat rank(l)  rank

lat basis(l)  basis of lattice
lat basis ring(l)  coefficient ring of basis

lat basis known(l)  basis is known
lat basis is over z(l)  basis is over ZZ
lat gram(l)  Gram matrix

lat gram ring(l)  coefficient ring of Gram matrix
lat gram known(l)  Gram matrix is known
lat gram is over z(l)  Gram matrix is over ZZ
lat chol(l)  Cholesky matrix
lat chol ring(l)  coefficient ring of Cholesky matrix
lat chol known(l)  Cholesky matrix is known
lat chol is over z(l)  Cholesky matrix is over ZZ
lat double chol(l)  Cholesky matrix (as double matrix)
lat disc(l)  lattice discriminant

lat disc ring(l)  ring over which lat disc is given

lat disc known(l)  discriminant is known
lat disc is integer(l)  discriminant is an integer
lat succ min count(l)  number of successive minima known

lat succ min count set(l, len)  setting this number

lat succ min(l,i)  the ith successive minimum

lat succ min vec(l, i)  A lat elt with length lat succ min(l,i)

lat succ min vec count(l)  number of such vectors known

lat succ min vec count set(l, len) setting this number

The following table shows the most important macros manipulating a lat enum env.

macro name  explanation
lat enum ubound(e)  upper bound of Euclidean length
lat enum lbound(e)  lower bound of Euclidean length
lat enum lbound is zero(e)  lower bound is zero (default)

lat enum ref vector(e)  reference vector

lat enum ref vector is zero(e)  no reference vector given (default)
lat enum ref vector coef(e,i)  ith coefficient of reference vector
lat enum request set shortest(e) compute shortest vector (default)
lat enum request set next(e)  compute short vectors, each at a time
lat enum strategy set down(e)  search downwards (0 last) (default)

lat enum strategy set up(e)  search upwards (0 first)
lat enum status set new(e)  reset lat enum

lat enum precision set short(e) do enumeration in double precision (default)
lat enum precision set long(e)  do enumeration in high precision

lat enum act coefs(e)  actual lat elt

macro name  explanation

          lat enum act length(e) length of actual lat elt
          lat enum counter(e)  number of lat elts found up to now

5.8.2 lattice functions

In the sequel we list all functions dealing with lattices. For interface functions to the order package see Section 5.10, page 76.

t void lat chol calc(lattice lat)

Task: Cholesky decomposition of Gram matrix Description: This function assures that the Cholesky type decomposition (which is needed by lat enum) is computed. This function need not be called before lat enum since lat enum does it automatically. For the Cholesky matrix calculation the basis or its Gram matrix must be known. The entries of the Cholesky matrix will be real numbers. If the basis matrix or Gram matrix are given over reals the same precision will be taken for the Cholesky matrix. If both are over ZZ (and lat chol ring(lat) was not set) a default decimal precision of currently 20 digits will be taken.

indexlat create \underline{lattice lat create()}

Task: Creation of an empty lattice Description: This function returns the handle of an “empty” lattice. This function has to be used if the user wants to create a lattice “by hand”, i.e. without using interface routines like order lat or anf ideal lat. A “complete” lattice is given if – after performing lat=lat create() – the structure elements lat rank(lat) and (alternatively)

lat basis(lat) and lat basis ring(lat) or lat gram(lat) and lat gram ring(lat)

are set.

t void lat delete(lattice &lat)

Task: Deletion of a lattice Description: Every lattice has to be deleted when it is not needed anymore. This is done with this function.

t void lat elt delete(lattice lat, lat elt &elt)

Task: Deletes a lattice element Description: Lattice elements (lat elts) have to be deleted with this routine when not needed anymore. Of course this does not apply to lat elts which are contained in the structures of lattices or lat enum envs. They will be deleted automatically when the higher structures are deleted.

t void lat disc calc(lattice &lat)

Task: Computes lattice discriminant Description: Computes the discriminant of a given lattice. The basis or Gram matrix of this lattice must exist. After performing lat disc calc(lat) for a given lattice lat the lattice discriminant can be accessed to via the macro lat disc(lat). Depending on the coefficient ring of the lattice basis or Gram matrix the lat disc is real or integer: This can be seen from the coefficient ring lat disc ring(lat), using a construction like

if (ring type(lat disc ring(lat)) == RING Z) ....

lat elt lat elt move(lattice lat, lat elt elt, matrix trans)

Task: Transformation of lattice elements Description: If the basis of a lattice has been modified (by, for example, performing lat2

= lat lll reduce(lat1, &trans,&invtrans)) it might be necessary to “move” lattice

elements from a representation referring to one basis to another. This is performed by this function. In the above example an element e1 of lat1 can be moved to a representation

referring to lat2 by performing e2=lat elt move(lat1, invtrans).
lat elt lat elt negate(lattice lat, lat elt elt)

Task: Negation of a lat elt Description: Negates all coefficents of elt and returns a new lat elt.

t logical lat enum(lattice lat, lat enum env env)

Task: Enumeration of lattice points of small Euclidean length Description: This is the main enumeration function for finding lattice elements of small Euclidean norm. The technique of communication with lat enum is explained in greater detail in Section 4.1.1, page 20. The main idea is that lat enum returns TRUE as long as it finds another lat elt. The actual lattice element can then be accessed to via lat enum act coefs(env). The main parts of the technique used in this function have been developed by Fincke and Pohst in [13].

lat enum env lat enum create(lattice lat)

Task: Creation of a lat enum env Description: Before using lat enum for a particular lattice the so-called enumeration environment of this lattice has to be initialized. This has to be done (once for a lattice) by calling this function. lat enum create also initializes certain flags to default values, in particular it sets the request to shortest and the strategy to up.

t void lat enum delete(lattice lat, lat enum env &env)

Task: Deletion of a lat enum env Description: After use, every enumeration environment has to be deleted. This has to be done before deleting the lattice it refers to.

t void lat gram calc(lattice lat)

Task: Gram matrix calculation of a lattice Description: Assures that the Gram matrix of a lattice exists. This routine needn’t be called explicitly by the user, since lat enum itself (and lat cholc, too) checks whether the Gram matrix is given and computes it, when necessary. The coefficient ring of the Gram matrix is the same as for the basis. An exception is made for certain number fields: The interface routines order lat and anf ideal lat realize that the Gram matrix for a lattice representing the conjugate lattice of an order or ideal of a totally real number field is integral.

lattice lat lll reduce(lattice lat, matrix &trans, matrix &invtrans)

Task: LLL reduction of lattice basis Description: Performs an LLL reduction on the lattice basis and returns a completely new lattice, the transformation matrix and its inverse. These matrices can be used when transforming basis representations of lattice elements (see lat elt move).

lat elt lat shortest vector(lattice lat, t real &length, t logical prec)

Task: Shortest vector in a lattice Description: Computes a shortest vector in the lattice lat. On exit, the real variable length contains the square length of the lat elt returned. By setting the additional input flag prec the user can decide whether the enumeration should be executed by using

double precision (prec=FALSE) or long arithmetic over t reals (prec=TRUE). The latter

case is more exact but much more time consuming. It should only be used in very bad conditioned lattices.

5.9 orders, anfs etc.

5.9.1 The macros

We start with a summary of the macros accessing anf items.

macro name  explanation

anf abs degree(f)  absolute degree

anf r1(f)  number of real places
anf r2(f)  half number of complex places
anf r(f)  unit rank
anf poly z count(f)  number of minimal polynomials over ZZ

anf poly z count set(f, len)  setting this number

anf poly z poly(f, i)  a particular polynomial over ZZ
anf poly z zeroes(f, i)  the zeroes of this polynomial
anf poly z zeroes reals(f, i)  the field over which the zeroes are given
anf poly z disc(f, i)  the polynomial discriminant

anf poly z disc fac(f, i)  . . . its factorization

anf poly z rdisc(f, i)  the reduced discriminant

anf poly z rdisc fac(f, i)  . . . its factorization
anf poly z zeroes known(f, i)  are the zeroes known?

anf poly z disc known(f, i)  is the discriminant known?
anf poly z disc fac known(f, i) … is its factorization known?
anf poly z rdisc known(f, i)  is the reduced discriminant known?
anf poly z rdisc fac known(f, i) … is its factorization known?

anf poly z zero(f, i, j)  a particular zero

anf poly order count(f)  number of minimal polynomials over orders

anf poly order count set(f, len) setting this number
anf poly order poly(f, i)  a particular polynomial
anf poly order order order(f, i) the suborder

anf order count(f)  number of orders of this field given

anf order count set(f, len)  setting this number

anf order(f, i)  a particular order
anf incref(f)  incrementing the reference count

The next table summarizes all order-related macros:

macro name  explanation

order abs degree(o)  absolute degree

order r1(o)  number of real places
order r2(o)  half number of complex places

order r(o)  unit rank

order anf(o)  quotient field
order is maximal(o)  is the order maximal?

order set is maximal(o)  setting this flag

order isnt maximal(o)  is the order not maximal?

order set isnt maximal(o)  setting this flag

order basis is pure(o)  is the basis a pure power basis?
order pure gen(o)  the generator if it is a pure order
order basis is power(o)  is the basis power basis?

order set basis is power(o)  setting this flag

order poly(o)  minimal polynomial if power basis
order basis is rel(o)  is it given via a transformation matrix?

order set basis is rel(o)  setting this flag

order tran(o)  … the transformation matrix
order tran den(o)  … its denominator
order index(o)  … the index in the suborder
order invtran(o)  … inverse of transformation matrix

order suborder(o)  . . . the suborder

order basis is table(o)  or is it given via a table?

order set basis is table(o)  setting this flag
order basis table anf elt(o, i) . . . the i-th basis element

order basis table order(o, i) … and the order where it’s from
order disc(o)  the order discriminant

order disc known(o)  . . . is it known?

order disc assure(o)  assure it’s existence
order mult table(o)  multiplication table of basis elements
order mult table known(o)  is the multiplication table known?
order coef order(o)  the coefficient order (often ZZ)

order must be over z(o)  . . . it really must be ZZ
order rel degree(o)  the relative degree

order mult known(o)  multiplication is defined in this order
order mult assure(o)  assure that multiplication can be done
order one position(o)  position of the 1 in the basis
order reals(o)  field over which all real values are defined
order real prec(o)  actual precision of reals of order
order sqrt 2(o)                  \sqrt{2} (as real number) in actual precision
order reals known(o)  are the real values of the order known?
order reals assure(o)  assure the existence of real order values
order basis real(o)  conjugate matrix of basis elements

order basis real inv(o)  inverse of this matrix

order basis real known(o)  are these real matrices known?

macro name  explanation
order units count(o)  actual number of independent units known

order units count set(o, count)  setting this number
order units known(o)  is any unit known?
order units are maximal(o)  is the unit system maximal?

order units are fund(o)  is the unit system fundamental?

order set units are fund(o)  setting this flag
order unit(o, i)  the i-th unit

order units logs(o)  logarithm matrix of units
order reg(o)  regulator of unit system
order reg known(o)  is the regulator known?
order units logs known(o)  is the logarithm matrix known?
order units log lat(o)  logarithm lattice of units
order units log lat env(o)  … its enumeration environment
order torsion unit(o)  generator of torsion subgroup
order torsion rank(o)  rank of torsion subgroup
order torsion unit known(o)  is the torsion subgroup known?

order class number(o)  class number
order class number known(o)  is the class number known?
order class group structure known(o)  is the class group structure known?

order class group order(o)  number of cyclic factors of class group

order class group order set(o,count)  setting this number
order class group factor order(o, i)  order of the i-th factor
order class group gen count(o)  number of ideals used for Cl_{F}
order class group gen count set(o, count) setting this number
order class group gen(o, i)  the i-th ideal
order class group factor gen exp(o,i,j)    j-th exponent of i-th generator
order subfield order count(o)  number of subfield orders known
order subfield order count set(o, len)  setting this number
order subfield order(o, i)  a particular subfield order
order subfield order rel degree(o, i)  . . . the relative degree
order subfield order basis elt(o, i, j) . . . the j-th basis element

order subfield order con tran(o, i)  … transformation matrix for conjugates

order subfield order con tran known(o,i) . . . is this matrix known?

order fac basis alloc(o, l)  allocating space for l factor basis el’s

order fac basis prime(o, i)  prime i in the factor basis

order fac basis ideals(o, i)  prime ideals over prime i in factor basis

order fac basis ideals count(o)  number of ideals in factor basis
order fac basis ideals count get(o, c)  dto., different format
order fac basis ideals count set(o, c)  setting this number
order fac basis len(o)  number of primes used
order fac basis len get(o, len)  dto., different format
order fac basis len set(o, len)  setting this number
order fac basis assure space(o, len)  assuring space for factor basis

macro name  explanation

order fac basis assure space size(o,l,e) dto., e= minimal extension

order relation mat(o)  actual relation matrix

order relation number(o, i)              anf elt representing relation i

order relation trans mat(o)  transformation matrix (not used yet)
order relation status(o)  status of Eimer (internal)
order relation count(o)  number of actual relations

order fincke lambda(o)  λ of Fincke
order fincke lambda known(o)  is Fincke’s λ known?

order fincke gamma1(o)  γ/k of Fincke’s norm equation algorithm

order fincke rbound(o, i )  actual r_{i} of Fincke
order fincke rbounds known(o)  are Fincke’s r_{i} known?
order fincke rbounds assure(o)  . . . assure their existence

order incref(o)  incrementing the reference count

We now list macros dealing with anf elts:

macro name  explanation

  anf elt is single(a)  this number is an t int
  anf elt is integer(a)  this number is an integer big
  anf elt handle to big(h) convert a handle to an integer big
  anf elt big to handle(a) convert an integer big to a handle

anf elt alloc(a, d)  allocate space for algebraic number (rel. degree d)
anf elt coef(a, i)         i-th coefficient of number
anf elt den(a)  denominator of algebraic number
anf elt is con(a)  this number is given via conjugates
anf con(a, i)  the i-th conjugate vector element
anf con alloc(a, d)  allocate space for conjugate vector

  anf elt reassign(ord,a,b) set a=b and delete a

anf elt incref(a)  increment reference count of a

  anf elt delete(ord, a)  delete a
  anf elt delref(ord, a)  dto.

The following table deals with macros for anf ideals:

macro name  explanation
anf ideal gen1(id)  first generator in 2-element presentation
anf ideal gen2(id)  second generator in 2-element presentation
anf ideal is 2(id)  the ideal is given in 2-element presentation
anf ideal is 2 normal(id)  … even in normal presentation
anf ideal gen g(id)  g (if ideal in normal presentation)
anf ideal tran(id)  transformation matrix (if ZZ-basis presentation)
anf ideal tran den(id)  denominator of transformation matrix
anf ideal is z(id)  ideal is given in ZZ-basis presentation
anf ideal tran is hnf(id)  transformation matrix is in Hermite form
anf ideal tran is upper hnf(id) transformation matrix is in upper Hermite form

anf ideal tran set upper hnf(id) set this flag

macro name  explanation
anf ideal tran is lower hnf(id) transformation matrix is in lower Hermite form

 anf ideal tran set lower hnf(id) set this flag

anf ideal min(id)  mimimum of positive integers in id

 anf ideal min known(id)  is the minimum known?

anf ideal degree(id)  the degree of inertia (if it is a prime ideal)

 anf ideal degree known(id)  is this degree known?

anf ideal incref(id)  incremenet reference counter

There are only three macros dealing with anf ceilings: They are in particular:

macro name  explanation

          anf ceiling lambda(c, i) accessing a particular λ

anf ceiling rexp(c, i)  accessing a particular exponent r_{i}
anf ceiling incref(c)  incrementing the reference count

5.9.2 The functions

anf ceiling anf ceiling alloc(order ord)

Task: Allocation of a ceiling Description: This function allocates space for the λ and r vector of a ceiling. The r_{i} are set to 1 whereas the λ_{i} are not initialized.

t void anf ceiling delete(order ord, anf ceiling &c)

Task: Deletion of a ceiling Description: The ceiling c referring to the order ord will be deleted.

t void anf ceiling write(order ord, anf ceiling c)

Task: prints a ceiling Description: The λ_{i} and r_{i}, belonging to the ceiling c, are printed.

anf elt anf con elt(order ord, anf elt ac)

Task: Coefficients of algebraic number if conjugates are given Description: ac is the conjugate vector of an algebraic number α, stored according to the convention as outlined in Section 4.1.3, page 24. This function tries to regain the coefficients of α, referring to the actual order basis. This is done by multiplying the conjugate vector by the matrix order basis real inv(ord), the inverse of the conjugate matrix of the order elements. The resulting vector should be integral, however, no check for correct precision is done. So – in case the resulting coefficients being very large – this function might give erroneous results.

anf anf create()

Task: Creation of a number field Description: A number field is created. All its invariants are set to blank. This function is mainly used internally, for example by order equation create.

t void anf delete(anf &f)

Task: Deletion of a number field Description: This function deletes the number field f. In case one uses anfs only internally (for example by order equation create or order read) one does not need to take care of deleting the number field of the actual order. This is done automatically when deleting the order.

t void anf dump(anf f)

Task: Prints a number field in dump mode. Description: A collection of the data of the number field f is printed. This function is mainly used for debugging reasons, it mainly prints handles and reference counts.

vector anf elt abs(order ord, anf elt a)

Task: Absolute values of conjugates of an algebraic number Description: Computes a vector of length r_{1} + r_{2} (where n = r_{1} + 2r_{2} is the signature of the order ord) containing the absolute values of the conjugates of a. The vector entries are given in the actual real precision of ord. The last r_{2} entries are not weighted by \sqrt{2} as for example anf elt con does. So for example the absolute value of the norm of a is computed by multiplying the first r_{1} components by the squares of the last r_{2} components of the abs-vector.

anf elt anf elt add(order ord, anf elt a, anf elt b)

Task: Addition of algebraic numbers Description: The two algebraic numbers a and b are added. This generic function is able to cope with all combinations of representations of algebraic numbers and – if necessary – converts them appropriately. In case of a or b being given via its conjugates the result will also be given in conjugates. Also care for denominators is taken. However, this function does not perform any simplification.

anf elt anf elt add mod(order ord,integer big m, anf elt a, anf elt b

Task: Addition of algebraic numbers modulo m Description: The same as anf elt add. Neither a nor b should be given as a conjugate vector.

anf ceiling anf elt ceiling(ord, a)

Task: Computes the ceiling of an algebraic number Description: Let a_{j} be the absolute value of the j-th conjugate of a. Then the ceiling (λ_{j})_{j∈{1,...,n}} of a is defined via

∀j ∈ \{1,…, j\}: λ_{j} := \frac{a_{j}}{\sqrt[n]{N(a)}}.

The r-vector of the ceiling will be set to 1.

anf elt anf elt con(order ord, anf elt a)

Task: Conjugate vector of an algebraic number Description: Computes the conjugates of a according to the conventions as explained in Section 4.1.3, page 24. This is done by multiplying the matrix order real basis(ord) (the conjugates of the order basis elements) by the coefficient vector of a.

t void anf elt delete(order ord, &a)

Task: Deletion of an algebraic number Description: Deletes the algebraic number a.

anf elt anf elt div(order ord, anf elt a, anf elt b)

Task: Division of algebraic numbers Description: Divides a by b. This is done by computing the nullspace of a suitable chosen integer matrix. The result will be simplified, so if the denominator of the result is 1 the quotient is an algebraic integer. This function can only handle orders which are given over ZZ.

anf elt dump(order ord, anf elt a)

Task: Prints an algebraic number in dump mode. Description: This function, written for debugging reasons, prints the algebraic number a, but also all occuring handles and reference counts.

t logical anf elt embed(order ord1, anf elt a, t poly pol, order ord2, anf elt &b)

Task: Trying to lift an anf elt Description: This function tries to find the algebraic number a of ord1 in the order ord2. If this is possible, it returns TRUE and the number, now presentated via the basis of ord2, in b. This functions uses a method first presented in [24]: It computes the T_{2}-value of a and then enumerates the conjugate lattice given by ord2, searching for elements with the same length (adjusted to the actual signature). These elements are candidates for a. Using the minimal polynomial of the numbers in question it then can be proved whether a has been found.

This function is mainly used as core procedure for establishing a connection between two orders (as done by order find hom). Once the homomorphism is established the function

anf elt order coerce should be used.

If the minimal polynomial of a is known in advance it should be submitted in pol. If not pol should be set to 0 before calling anf elt embed.

t logical anf elt equal(order ord, anf elt a, anf elt b)

Task: Compares algebraic numbers Description: This function checks whether a and b are identical. Before the comparison a simplification is executed, so this function checks for mathematical equality. In case of one or both of the numbers being submitted via conjugates precision errors might lead to wrong results.

t logical anf elt factorize(order ord, anf elt a)

Task: Factorizes a principal ideal over a given factor basis Description: This function tries to factorize the principal ideal given by a into the actual factor basis of ord. If this is possible a is put into the Eimer, see Section 4.2.2, page 27 for details. Note that units factorize in any case. If there is no factor basis yet and if a is no unit the factor basis will be created automatically by this function, currently with an upper norm bound of currently 50. The factorization of a is done in two steps: First it is checked whether the norm decomposes into the primes over which the factor basis ideals lie. If this is possible the exponents are computed by successive inclusion checks of the form a ∈ ℘^{i} (which is equivalent to ℘^{i}|a).

t logical anf elt in ideal(order ord, anf elt a, anf ideal id)

Task: Checks whether a∈id Description: Returns TRUE if a is contained in the ideal id. This function expects (or creates) a ZZ-basis presentation for id, given in upper Hermite form, then tries to solve a system of linear equations, where the “right side” is given by the coefficient vector of a.

anf elt anf elt inverse(order ord, anf elt a)

Task: Inverse of an algebraic number Description: Returns anf elt div(ord, 1, a).

t logical anf elt is integer sub(order ord, anf elt a, integer big &aint)

Task: Checks whether the algebraic number a is an integer Description: Returns TRUE if a∈ ZZ. In this case aint=a. Note the difference between this function and the macro anf elt is integer. The latter one just looks whether a is stored as integer big but not whether it actually is an integer.

t logical anf elt is minus1(order ord, anf elt a)

Task: Checks whether an algebraic number is -1 Description: Returns TRUE if a=-1.

t logical anf elt is one(order ord, anf elt a)

Task: Checks whether an algebraic number is 1 Description: Returns TRUE if a=1.

t logical anf elt is primitive(order ord, anf elt a)

Task: Checks whether a is primitive element of the actual number field Description: Returns TRUE if a is a primitive element of the quotient field of ord. This function simply computes the conjugates of a and looks whether they are distinct. Since real arithmetic is used one should be careful when using this function.

t logical anf elt is zero(order ord, anf elt a)

Task: Checks whether an algebraic number is 0 Description: Returns TRUE if a=0.

t comp anf elt ith con(order ord, anf elt a, t int i)

Task: i-th conjugate of an algebraic number Description: The conjugate vector of algebraic numbers is sorted in a particularly algorithmoriented way, see Section 4.1.3, page 24. This function returns an approximation of the i-th conjugate as a complex number.

t logical anf elt lift down(order ord1, anf elt a, order ord2, anf elt &b)

Task: Trying to lift down an element of ord1 into ord2 Description: This function expects that ord2 has already been identified as a subfield order of ord1 (see order find hom). If that is not the case it will return FALSE. Otherwise it tries to move a into ord2 and – if that was possible – returns the new presentation in b.

anf elt anf elt lift up(order ord1, anf elt a, order ord2)

Task: Lifting an element of ord1 into ord2 Description: This function expects that ord1 has already been identified as a subfield order of ord2 (see order find hom). If that is not the case it will run onto an error. Otherwise it hands back an algebraic number representing a in terms of the presentation of ord2. This function makes use of the homomorphism as installed by order find hom. The user should call anf elt order coerce instead.

vector anf elt logs(order ord, anf elt a)

Task: Logarithm vector of an algebraic number Description: Computes a vector of length r_{1} +r_{2} containing the logarithms of the absolute values of the first r_{1} + r_{2} conjugates of a. The sum of these components (doubling the last r_{2} entries) yields the logarithm of the absolute value of the norm of a.

t void anf elt logs mat(order ord, anf elt a, matrix mat, t int colno)

Task: Logarithm vector of an algebraic number as matrix column Description: Like anf elt logs. The difference is that the logarithm vector is put into column colno of matrix mat. mat must have been allocated before and must have row dimension either r_{1} + r_{2} or r_{1} + r_{2} − 1.

t poly anf elt minpoly(order ord, anf elta)

Task: minimal polynomial of an algebraic number Description: The result of this function is the minimal polynomial of the algebraic integer a. The current method used is still using real arithmetic and Newton’s relations which is extremely time consuming. This function will soon be replaced by a much faster one.

anf elt anf elt move(order ord1, anf elt a, order ord2)

Task: coercing algebraic numbers, easy version Description: This function converts representations of algebraic numbers. It has to be called only when conversion is possible, otherwise it causes an error. Please call the general function anf elt order coerce instead. The following features are implemented in

anf elt move:

– a is an integer.

– The handle of ord1 is equal to the handle of ord2. In this case a will be copied physically.

– ord1 is the coefficient order of ord2.

– ord1 is given via a transition matrix referring to ord2 (lift up).

– ord2 is given via a transition matrix referring to ord1 (lift down).

anf elt anf elt anf elt mult(order ord, anf elt a, anf elt b)

Task: Multiplication of algebraic numbers Description: The two algebraic numbers a and b are multiplied. This generic function is able to cope with all combinations of representations of algebraic numbers and – if necessary – converts them appropriately. In case of a or b being given via its conjugates the result will also be given in conjugates. Also care for denominators is taken. No simplification is performed.

anf elt anf elt mult mod(order ord, integer big modul, anf elt a, anf elt b)

Task: Multiplication of algebraic numbers modulo modul Description: The two algebraic numbers a and b are multiplied modulo modul. The numbers must be given in coefeficients referring to the basis of ord.

anf elt anf elt negate(order ord, anf elt a)

Task: negates an algebraic number Description: returns -a.

t void anf elt norm(order ord, anf elt a, integer big &norm, integer big &den

Task: norm over Q of an algebraic number Description: Computes the norm of an algebraic number. Since a might be not integer a denominator of the norm is returned. If a is given by its coefficients referring to a basis of ord the computed value will be N(a). The norm is computed by calculating the determinant of the representation matrix of a. In case of a being given via its conjugates no check is done whether the precision was sufficient.

t void anf elt norm abs(order ord, anf elt a, integer big &norm, integer big &den

Task: absolute norm over Q of an algebraic number Description: Computes the absolute value of the norm of an algebraic number. Since a might be not integer a denominator of the norm is returned. In case of a being given via its conjugates no check is done whether the precision was sufficient.

t void anf elt norm rel(order ord, anf elt a, anf elt &norm, integer big &den

Task: relative norm of an algebraic number Description: This function computes the norm of a over the actual coefficient order of ord. The norm is computed via calculating the determinant of the representation matrix of a, so the sign might not be correct. Also a denominator of the norm is computed, in case of a being not an algebraic integer. The resulting norm will be given as anf elt referring to the coefficient order of ord.

t logical anf elt order coerce(order ord1, anf elt a, order ord2, anf elt &b)

Task: coercing algebraic numbers, general function Description: This function converts representations of algebraic numbers. It tries to find the best “graph” between ord1 and ord2 and then moves a into b. It returns TRUE if it succeeded. This function first tries to find an “easy” link between ord1 and ord2 and then calls anf elt move. If this is not possible it looks via order find hom tower whether there is a chain of homomorphisms connecting ord1 with ord2 and tries to move a along this chain (using anf elt lift up or down). If it did not find a chain it tries to install a homomorphism between ord1 and ord2 and if that fails it directly looks for a in ord2

using anf elt embed.
anf elt anf elt power mod(order ord, integer big modul, anf elt alpha, integer big expo)

Task: Power of an algebraic number modulo modul Description: Computes the power of the algebraic integer a modulo modula must be given referring to the order basis (no conjugates!).

anf elt anf elt power mod(ord, modul, alpha, expo)

          order ord, integer big modul, anf elt alpha, integer big expo

Task: Power of an algebraic number modulo modul Description: Computes the power of the algebraic integer a modulo modula must be given referring to the order basis (no conjugates!).

anf elt anf elt power product(order ord, vector b, vector e)

Task: Power product of algebraic numbers Description: Computes the power product of the algebraic numbers submitted in the vector b. The exponents are given by e.

anf elt anf elt power product mod(order ord, integer big modul, vector b, vector e)

Task: Power product of algebraic numbers modulo modul Description: Computes the power product modulo modul of the algebraic numbers submitted in the vector b. The exponents are given by e.

anf elt anf elt read(order ord)

Task: Input of an algebraic number Description: Reads an algebraic number from stdin. The coefficients of the number (referring to the order) must be given and the denominator.

anf elt anf elt reduce(order ord, anf elt a)

Task: Better conditioned associate anf elt Description: The idea of this function is, given an algebraic number a, to find a unit ε such that aε is much nicer, i.e. that the absolute values of the conjugates of aε are close to each other. The method used is looking for an element in a certain lattice which lies near to a certain given point. The lattice under consideration is the logarithm lattice of the units and the reference point is the logarithm vector of the number a.

matrix anf elt rep mat(order ord, anf elt a)

Task: Representation matrix Description: This function computes the matrix M which represents the multiplication of number field elements by a as linear map. The i-th column of M is the coefficient vector of ω_{i} · a, referring to the basis ω_{1},…, ω_{n}. Note that no care about any denominator is taken. a should not be given as conjugate vector.

matrix anf elt rep mat mod(order ord, integer big m, anf elt a)

Task: Representation matrix modulo m Description: Computes the representation matrix of a modulo m.

anf elt anf elt simplify(order ord, anf elt a)

Task: Simplification of an anf elt Description: Returns an algebraic number which is – mathematically – equal to a but which may have a different presentation. If a is actually an integer an integer will be returned. If any denominators are involved this functions asserts that only one denominator will be returned (this applies to the case of relative extensions where the coefficients are algebraic numbers as well), and that this denominator is minimal.

anf elt anf elt subtract(order ord, anf elt a, anf elt b)

Task: Subtracts a from b Description: Returns a − b.

anf elt anf elt to princ ideal(order ord, anf elt a)

Task: Computation of a principal ideal Description: Returns the ideal a · ord. The ideal created will be given in @-element presentation, but not normal presentation.

t real anf elt t2(order ord, anf elt a)

Task: T_{2} norm of an algebraic number Description: returns T_{2}(a) = ∑_{j=1}^{n} |a^{(j)}|^{2}. Note that in case of the number field being totally real this is equal to the trace of a^{2}.

t void anf elt to mat order col(order ord, anf elt a, matrix mat, t int cno)

Task: Conversion of coefficient vector Description: Writes the coefficients of a into the cno-th column of mat. No care of denominators is taken. If a is given by conjugates the conjugate vector is copied into the matrix.

integer big anf elt trace(order ord, anf elt a)

Task: Trace of an anf elt Description: Computes the sum of the conjugates of a, using integer arithmetic. The trace of a is equal to the trace of its representation matrix. No care for denominator is taken.

anf elt anf elt trans(order ord, anf elt a, matrix trans, integer big den)

Task: Transformation of anf elt Description: Multiplies the coefficient vector of a by the matrix trans, attached with the denominator den. This is an internal function used by anf elt move.

t void anf elt write(order ord, anf elt a)

Task: Printing of an anf elt Description: Writes the algebraic number on stdout.

t void anf error(char msg)

Task: General error function Description: Prints the error message msg and dies.

t void anf ideal 2 assure(order ord, anf ideal id)

Task: Computing a 2-element presentation of an ideal Description: This function tries to assure a 2-element presentation of id in which the first generator is an integer. If the latter is not the case it takes min(ZZ^{>0} ∩id) as first generator and applies a probabilistic method (see [31]) for the computation of the second. The ideal may be changed in site.

anf ideal anf ideal 2 create(order ord, anf elt a, anf elt b)

Task: Creating an ideal in 2-element presentation Description: This function returns the ideal generated by the two algebraic numbers a and b. It assumes that no particular normal presentation is given.

t void anf ideal 2 normal assure(order ord, anf ideal id)

Task: Computing a 2-element normal presentation of an ideal Description: This function tries to assure a 2-element normal presentation of id where, on entry, id might be given in any presentation. If id is given in a 2-element presentation where the first element is an integer g this function tries to find a P (g)-normal presentation [28, 32]. (In case of g not being prime errors may occur). In the other case it first performs anf ideal 2 assure. The ideal may be changed in site.

t logical anf ideal 2 normal check(order ord, anf ideal id)

Task: Checking whether an ideal is given in 2-element-normal presentation Description: For an ideal id (which must be integral) this function checks whether it is given in a 2-element-P (g)-normal presentation, see [28, 32]. Here g ∈ ZZ is the first generator of the ideal.

anf ideal anf ideal 2 read(order ord)

Task: Reading an ideal in Z-basis presentation Description: Reads an ideal from stdin. It expects that the ideal is given via (currently)

an integer big and an anf elt.
anf ideal 2 z(order ord, anf ideal id)

Task: Conversion of ideal presentations Description: Computes a Z-basis presentation of the ideal id. After calling this function id will also be given in upper Hermite normal form.

anf ideal anf ideal anf elt div(order ord, anf ideal id, anf elt a)

Task: Divide an ideal by an algebraic number Description: Computes the (fractional) ideal given by dividing id by a. If a is a minimum in id, for example computed by the function anf ideal shortest vector, the result will be a reduced ideal in the same class as id (see for example [7]).

t void anf ideal delete(order ord, anf ideal &id)

Task: Delete an ideal Description: Deletes id.

t logical anf ideal different(order ord, anf ideal id1, anf ideal id2)

Task: Compares two ideals Description: Returns TRUE if id1 = id2 and FALSE otherwise.

anf ideal anf ideal invert integral(order ord, anf ideal id)

Task: Inverting an integral ideal Description: The ideal id must be an integral ideal, given in any presentation. This function inverts it (after converting it to a normal presentation) and returns the inverse ideal which will be given in a 2-element-normal presentation as well. The method used is described in [28, 31].

t logical anf ideal is integral(order ord, anf ideal id)

Task: Checks whether an ideal is integral Description: Returns TRUE if id1 is an integral ideal and FALSE otherwise.

t logical anf ideal is prime ideal(order ord, anf ideal id, anf ideal &idnew)

Task: Checks whether an integral ideal is maximal Description: Returns TRUE if id1 is a maximal ideal and FALSE otherwise. If id is not maximal (i. e. not prime in a maximal order) this function returns a strictly larger ideal

in idnew.
t logical anf ideal is principal(order ord, anf ideal id, anf elt &gamma)

Task: Checks whether an ideal is principal Description: Returns TRUE if id1 is a principal ideal and FALSE otherwise. If id is principal a generator will be returned in gamma. This function uses the norm equation method of Fincke (see [29]).

anf ideal anf ideal mult(order ord, anf ideal id1, anf ideal id2)

Task: Multiply two ideals Description: This function returns the product of id1 and id2. If possible, the multiplication is done componentwise using the 2-element presentation. In this case both of the ideals must be given in corresponding P (g)-normal presentation. If this is not the case the multiplication is executed by using the Z-basis presentations.

order anf ideal mult ring(order ord, anf ideal id, integer big m)

Task: Ring of multiplicators of an ideal Description: For a given ideal a = id of an order Λ_{0} = ord of a number field F this function computes the ring of multiplicators

Λ_{1} := [a/a] := {x ∈ F | xa ⊆ a}.

which is an overorder of Λ_{0}. Iterating this process (when starting with the socalled mradical) leads to the m-maximal overorder of Λ_{0}, see [27]. The submitted value m has either to be set to 0 or to the module over which this process is executed. In the latter case all computations are done modulo m.

anf ideal anf ideal neighbor(order ord, anf ideal id, t int dir)

Task: Neighbor of 1 in ideal Description: Computes the neighbor of the 1 in id in the direction of dir. This is explained in detail in [27].

t void anf ideal norm(order ord, anf ideal id, integer big &norm, integer big &den)

Task: Norm of ideal Description: Returns the norm of the (possibly fractional) ideal id. In case id is a prime ideal which was computed by order prime factorize this function hardly does any computations because the norm is stored in the ideal.

t void order norm equation(order ord, integer big K, anf elt &a, dyn arr handle &list, t logical req)

Task: Solving a norm equation in an order Description: This function solves the norm equation N(x) = K in the order ord using the method of Fincke [29]. Depending on whether req is TRUE or FALSE it either returns all non-associate solutions or just (maximal) one. A maximal (not necessarily fundamental) unit system of ord must be known.

On exit, list indicates if there was a solution. If so, list will be nonzero and a solution will be in a. In case of req being TRUE lst will contain all elements found (and a a particular one).

t int anf ideal ram index(order ord, integer big p, anf ideal id, t int &bound)

Task: Ramification index of a prime ideal Description: Conputes the maximal exponent e such that id^{e} divides the principal ideal p · ord. bound is a user provided upper bound for this index (set it to zero if you do not know it).

anf elt anf ideal shortest vector(order ord, anf ideal id, t logical prec, t real &length)

Task: Shortest vector in ideal Description: Returns an algebraic number of id with minimal T_{2}-value. The T_{2}-value will be returned in length. The prec flag indicates the request of the user whether the computation shall be executed using high (=TRUE) or low precision. We think that low precision will be sufficient in virtually all cases.

t void anf ideal simplify(order ord, anf ideal &id)

Task: Simplification of an ideal Description: Tries to simplify the presentations of the ideal id. This function only makes sense for fractional ideals and leaves integral ideals unaltered.

t void anf ideal tran assure hnf lower(order ord, anf ideal id)

Task: Lower Hermite transformation matrix for an ideal Description: Assures that the ideal id is presented by a ZZ-basis whose transformation matrix is given in lower Hermite normal form.

t void anf ideal tran assure hnf upper(order ord, anf ideal id)

Task: Lower Hermite transformation matrix for an ideal Description: Assures that the ideal id is presented by a ZZ-basis whose transformation matrix is given in upper Hermite normal form.

t void anf ideal z assure(order ord, anf ideal id)

Task: Assuring ZZ-basis presentation for an ideal Description: Assures that the ideal id is presented by a ZZ-basis.

anf ideal anf ideal z create(order ord, matrix trans, integer big den)

Task: Creating an ideal in Z-basis presentation Description: Returns the ideal which is defined via the transformation matrix (referring to the order basis elements) and the denominator den.

t void anf order set sig(t handle h, t int r1, t int r2)

Task: Set signature of order or anf Description: The first parameter of this function should either be an order or an anf. This function sets the “signature related values” of all orders and anfs within reach of the handle h, i.e. of all subfield orders, of the quotient field etc. to which a (direct or indirect) reference is found in h.

t void anf poly zeroes(anf field, t handle R, t int ind)

Task: Zeroes of a polynomial of an anf Description: Every anf contains a table of generating polynomials over ZZ. This function computes the zeroes of the ind-th polynomial in this table over the real field R. If the polynomials have been computed before in a smaller precision the old values will be used as starting values for the new iteration. The zeroes are stored as dyn arr within the anf structure, see Section 5.9.1, page 53 how to access them.

t void anf rdisc calc(anf field, t int no)

Task: Reduced discriminant of a polynomial of an anf Description: Computes the reduced discriminant of the minimal polynomial No. no and writes it into the structure of field. It can then be accessed to via anf poly z rdisc(field,

num).
anf elt integer anf elt lift(order ord, integer big a)

Task: Lift an integer to an anf elt Description: This function returns a true anf elt number which is equivalent to the integer a but no immediate integer. Note that an operation like anf elt simplify would destroy this property and return again an integer big.

t logical is index divisor(order ord, integer big p)

Task: Checks whether a prime number is index divisor Description: Returns TRUE when p divides the index of ord in its suborder and FALSE otherwise. This function is only makes sense if ord is given via a transformation matrix referring to a suborder.

t void kant start()

Task: General KANT startup function Description: This function has to be called once in every KANT main program. It initializes MEM, a few buffers of the mp Package and the most commonly used rings of ZZ, Q and the polynomial rings over these structures.

matrix mat anf read(order ord, t int dim)

Task: Read a matrix over an order Description: Reads a quadratic matrix of dimension dim over the order ord which might as well be the ring of integers. This preliminary function expects the matrix entries in a format anf elt read would understand (rowwise).

anf elt mat order col to anf elt(order ord, matrix mat, t int no)

Task: Conversion of matrix column Description: Extracts column number no of the matrix mat and creates an algebraic number of ord whose i-th coefficient is the element (i, no) of mat. The denominator is set to 0.

anf elt mat real col to anf con(order ord, matrix mat, t int colno)

Task: Conversion of matrix column Description: Extracts column number no of the matrix mat and creates an algebraic number of ord – given as conjugate vector – whose i-th component is the element (i, no) of

mat.

order order add(order ord1, order ord2)

Task: Addition of two orders over the same anf Description: This function is mainly used by the maximal order functions order maximal and order mac p. Its task is to add two orders which must be given over the same number field, usually presented by a transformation matrix referring to the same equation order. The addition is performed by the help of the Hermite normal form method. So far this method only works for orders whose coefficient order is ZZ.

integer big order bach bound(order ord)

Task: Bach’s bound Description: Assuming the generalized Riemann hypothesis, this function returns a number such that all prime ideals whose norm do not exceed this number generate the ideal class group of ord (see [1]). If d is the absolute value of the order discriminant, then this bound is 12 ∗ (log d)^{2} (or, in case of an imaginary quadratic order 6 ∗ (log d)^{2}).

anf elt order basis elt(order ord, t int i)

Task: A particular order basis element Description: Returns the i-th basis element of ord as algebraic number (which is – of course – nothing else than an array of zeroes containing a single 1 at position i).

t void order basis real create(order ord)

Task: Create conjugates of order basis Description: This function creates the matrix given by the conjugates of the actual order basis. Here the j-th column of the matrix (which can be accessed to via the macro order basis real(ord)) will contain the conjugate vector (see anf elt con) of basis element number j. Usually this function will be called indirectly via order reals create.

t logical order basis check(order ord, dyn arr handle elts, order ord1)

Task: Check whether a set of anf elts define an order basis Description: The number contained in elts are checked whether they define an order basis. This means that it will be checked whether they are linearly independent and whether they create a domain which is multiplicatively closed. If this is the case a new order will be returned in ord1. So far the new order must have the same degree as ord.

t void order class group calc(order ord)

Task: Computes the class group of ord Description: This function computes the class group of ord, assuming that ord is a maximal order (but not checking this). It uses a probabilistic method as explained in [33] for computing relations over a given factor basis of prime ideals. If relations have been computed by previous calculations (for example by unit calculation functions) it first tries to evaluate these relations.

This function does not yet prove whether the structure which was computed is really the class group structure.

order order create(anf f, order cord, t int deg, t int ppos)

Task: Create an order Description: This internal function creates a new order. Usually it will not be necessary to use this function directly since either order equation create, order create pure or order trans do the job. The user has several possibilities to call this function: f (if not zero) is the quotient field of the new order, cord (which must be set) the coefficient order and deg (if not 0) the degree of the extension. If ppos is set it points to a polynomial in the table of minimal polynomials of f (to number ppos of the integer polynomials if ppos is positive and to number -ppos of the polynomials over orders if ppos is negative). In this case deg is meaningless.

order order create pure(order cord, anf elt a, t int deg)

Task: Create a pure order Description: Creates and returns the order given by adjoining the degth root of a to cord. It is assumed that the new order has power basis.

t void order delete(order &ord)

Task: Delete an order Description: General deletion function for orders. Takes also care of double references of the order in number fields.

t void order disc calc(ord)

Task: Compute the discriminant of an order Description: This function assures that the actual order discriminant is known. In case it was known before it will be deleted and recomputed. This function tries to reduce the discriminant calculation to the calculation of a polynomial discriminant for which the method described in [37] will be used. The discriminant can then be accessed to via

order disc(ord).
t void order dump(ord)

Task: Prints an order in dump mode. Description: Prints data related to the order ord. This function is used for debugging reasons since it mainly prints handles and reference counts related to the order.

order order equation create(order cord, t poly pol)

Task: create an equation order Description: Let ρ be a zero of the polynomial pol over cord, this function creates and returns the order cord[ρ], assuming that it has power basis.

t void order fac basis create(order ord, integer big bound)

Task: Create factor basis Description: Initializes a factor basis for subsequent search for relations in ord. After calling this function the factor basis consists of all prime ideals in ord whose norms do not exceed bound.

t void order fac basis delete(ord)

Task: Delete factor basis Description: Deletes the actual factor basis of ord.

anf ideal order fac basis ideal(ord, t int num)

Task: Access ideal in factor basis Description: Returns the ideal number id of the factor basis.

t void order fac basis print(ord)

Task: Print actual factor basis Description: Prints all ideals in the factor basis of ord.

t logical order find hom(ord1, ord2)

Task: Find homomorphism between orders Description: Tries to identify ord1 as suborder of ord2. If this is possible, TRUE will be returned and the homomorphism installed (as a table of algebraic integers in ord2 representing the basis elements of ord1 and as a real matrix describing how conjugate vectors of ord1 have to be moved into ord2). After calling this function (which is, however, done automatically by anf elt order coerce) subsequent calls of anf elt lift up and down are possible. The main technique of order find hom is trying to move a primitive

element of ord1 into ord2 via anf elt embed.
order order lll reduce(order ord)

Task: LLL reduce real order basis Description: Reduces the basis of the conjugate lattice of the order ord and returns another order describing the same mathematical object but with a usually very good conditioned basis.

order order max p(order ord, integer big p, t int deg)

Task: Compute p-maximal overorder Description: Given ord and a prime p this function computes and returns the p-maximal overorder Λ_{p} of ord which is defined to be:

Λ_{p} = {α ∈ ord | ∃m ∈ ZZ^{>0}: p^{m}α ∈ ord}.

The index of this Λ_{p} in the maximal order of ord is not divisible by p.

The value deg is the maximal index of ord in the new order. If the user does not know any such bound he may submit 0. See [27] for further information.

order order maximal(order ord)

Task: Compute maximal order Description: Starting with the order ord, this function calculates the maximal order. The method currently used is the a refined version of the Round-2 algorithm of Zassenhaus, see [27] for further information or Section 4.2.1, page 26.

integer big order minkowski bound(order ord)

Task: Minkowski bound Description: Returns a number such that all prime ideals whose norm do not exceed this number generate the ideal class group of ord (see [29]). ord should be a maximal order.

For d being the absolute value of the order discriminant this function returns the largest integer smaller than n!/n^{n}(4/π)^{r_{2}} \sqrt{d} where n is the absolute degree and 2r_{2} the number of non-real embeddings of ord.

t void order norm equation(order ord, integer big K, anf elt &a, dyn arr handle &list, t logical req)

Task: Solving a norm equation in an order Description: This function solves the norm equation N(x) = K in the order ord using the method of Fincke [29]. Depending on whether req is TRUE or FALSE it either returns all non-associate solutions or just (maximal) one. A maximal (not necessarily fundamental) unit system of ord must be known.

On exit, list indicates if there was a solution. If so, list will be nonzero and a solution will be in a. In case of req being TRUE lst will contain all elements found (and a a particular one).

anf ideal order p radical(order ord, integer big p)

Task: Compute p-radical of order Description: Given an order ord and a prime number p, this function calculates the pradical:

J_{p}(ord) := {a ∈ ord | ∃ν ∈ ZZ^{>0}: a^{ν} ∈ pord}.

The p-radical is an ideal dividing p · ord and is used for the computation of the maximal order as well as for prime decompositions. See [27, 29] for more information.

t handle order prime factorize(order ord, integer big p)

Task: Factorize p into prime ideals Description: Returns the prime ideal factorization of the principal ideal generated by p. This function uses various methods, depending on the way the order ord is represented, see [32]. The result will be stored as a faclst using the polynomial faclst environment, see the header file poly z faclst.h for details.

anf elt order primitive elt(ord)

Task: Compute any primitive element Description: Returns any primitive element of ord, usually the generator of an equation order related to ord.

t logical order read(order &ord)

Task: General order input function Description: Reads an order and a few order invariants, see Section 4.3.5, page 33 for detailed information on the possible formats. The function returns TRUE if an order could be read and FALSE otherwise (for example when EOF or if the user typed a single e).

t logical order read v1(order &ord)

Task: Order input function, compatible to KANT-1 Description: This function only exists if the Fortran interface of KANT-2 has been set up (this is not the default situation!). The only difference to order read is that order read v1 is able to read “long” units in the old KANT-1-format.

t void order reals create(order ord)

Task: Create real values of order Description: Sets (or resets) the real values related to an order to the actual precision, for example the conjugate matrix of the order basis or the logarithms of the units. The actual precision can be influenced by calling order reals set first. If this has not been done, a default precision of currently 20 is assumed.

order reals set(order ord, t int p)

Task: Set new precision in order Description: For a number p larger than 20 this function sets the precision for future real calculations. After calling this function one has to call order reals create(ord).

t void order reg calc(order ord)

Task: Compute regulator of order Description: This function computes the regulator of the current unit system, provided that the system is maximal. This has to bee guaranteed by the user. Instead of calling one could as well call order unit group calc which will also set the regulator.

t void order relation delete(order ord)

Task: Delete relations found by now Description: Deletes the actual relation matrix of ord and the table of algebraic integers representing relations.

t void order relation eval class group(order ord)

Task: Compute Class group using the relations found Description: Evaluates the relations found until now with the objective of computing the class group. Does not perform any check whether the class group was really computed.

t void order relation eval units(order ord)

Task: Compute Unit group using the relations found Description: Evaluates the relations found until now with the objective of computing the torsion free part of the unit group. Does not perform any check whether the unit group was really computed.

t void order relations find(order ord, integer big t2, t int no)

Task: Looking for relations Description: General relation finding procedure. This function tries to find no relations for each ideal in the actual factor basis using a method for computing elements of small Euclidean norm in a lattice, see [33]. The value t2 can be chosen by the user. If he submits 0 the lattice enumeration will be done in a way that only elements of algebraic norm of not more than n × N_{max}^{4} · N(℘) are considered. Here n is the actual order degree, N the maximum of the norms of the factor basis ideals, and ℘ the actual ideal. In the other case t2 will be taken instead of the number above. However, if not sufficient relations are found, the upper bound for the enumeration will be doubled until we are done.

All the relations are put into the relation matrix which then can be evaluated by thr

order relation eval functions.
anf elt order shortest primitive elt(ord)

Task: Find shortest primitive element Description: Computes a primitive element of ord whose T_{2} value minimizes the T_{2} value of all primitive order elements. The minimal polynomial of this element is supposed to be very well conditioned.

t void order sig assure(ord)

Task: Assuring that signature is known Description: This function assures the signature of ord. If the signature is not yet known the discriminant will be computed since the function order disc calc reveals the signature as well. After calling this function one can be sure that the signature is known for all orders and the anf in the same “system” as ord.

order order simplify trans(order ord)

Task: Simplification of order towers Description: If a sequence of orders is given via transformation matrices to suborders (in the same number field) - this function should be called. It returns another representation of ord, but now given via a transformation matrix referring to an order which is not given via a transformation matrix.

t void order subfield orders find dirty

Task: Find some subfield orders Description: Dumb routine trying to find a few subfield orders of ord. Usually it does not find all subfield orders. This function computes a few alegbraic numbers of small T_{2} value and checks whether they are non primitive. If this is the case, it installs appropriate homomorphisms.

t void order torsion subgroup calc(order ord)

Task: Computes the torsion subgroup of ord Description: The torsion subgroup of ord is computed using a number geometric method as explained in [29]. It computes elements of very small T_{2} value and collects them via anf elt factorize. All torsion units will be among them. After exit of this function, the torsion subgroup invariants are accessible.

matrix order trace mat(order ord)

Task: Trace matrix of order Description: Returns a symmetrical matrix whose entries (i, j) are the trace of ω_{i} × ω_{j}, where ω_{i}, ω_{j} are the basis elements of ord.

order order trans(order ord, matrix trans, integer big den)

Task: Create new order by using a transformation matrix Description: Returns the order given by applying the transformation trans (with integer denominator den) to the order basis of ord. The coefficents of the matrix trans must be from the coefficient order of ord.

t void order unit group calc(order ord)

Task: Compute the unit group Description: Tries to compute the unit group of the actual order. This function is a com-

bination of order torsion subgroup calc and order units calc.
t void order units calc(order ord)

Task: Compute torsion free part of unit group Description: Tries to compute the torsion free part of the unit group of the actual order. The computation is done recursively, i.e. first units for known subfields are computed and lifted and then, if necessary, units are computed in ord itself. The method used depends on the unit rank: In case of it being 1 order units voronoi is employed, otherwise

order units relations.

The resulting unit group might not be fundamental.

t void order units logs calc(order ord)

Task: Compute logarithms if unit group is known Description: Computes the logarithm matrix of the unit system known and the regulator. This function calls anf elt logs mat.

t real order units logs reg calc(order ord, matrix mat)

Task: Compute regulator if logarithms of units are known Description: This function is mainly used by order units logs calc. It computes basically the determinant of the matrix mat (which must have square dimension r_{1} + r_{2})), but multiplies it with 2^{max{0,r_{2}}}.

t void order units relations(order ord)

Task: Compute units by using relation method Description: This is a particular unit computation method, using the relation method as for example explained in [5, 33]. After initializing a factor basis (the size of which depends on the Minkowski bound, it is roughly the fourth root of the absolute value of the order discriminant) it employs order relations find.

t void order units voronoi(order ord)

Task: Compute units by using Voronoi algorithm Description: This is an implementation of Buchmann’s generalization of the Voronoi algorithm for unit rank 1, see [4]. It computes a fundamental unit of ord in a very fast way.

t void order write(order ord)

Task: Print an order Description: This is the actual standard KANT output routine for orders. The syntax is explained in detail in Section 4.3.5, page 34. This function is compatible to order read, and – in case that the occurring numbers are not too large – to order read v1.

t poly poly order read(order ord, t int deg)

Task: Read a polynomial given over an order Description: This auxiliary input function expects deg algebraic numbers of the order ord and creates a monic polynomial over ord of degree deg, where the coefficients are given in decreasing order.

anf elt poly to anf elt(order ord, t poly pol)

Task: Convert polynomial coefficients to anf elt Description: Casts the coefficients of the polynomial into an algebraic integer of ord. The coefficients of the (monic and univariate!) polynomial must be from the coefficient order of ord and the order should be an equation order with power basis.

anf elt vec to anf elt(order ord, vector vec)

Task: Convert vector to anf elt Description: Casts the coefficients of vec into an algebraic integer.

5.10 Interface routines orders ↔ lattices

The interface routines between orders and lattices assume that the orders under consideration are defined over ZZ.

t void anf ideal lat(order ord, anf ideal id, lattice &lat, lat enum env &env)

Task: Computes the lattice belonging to an ideal Description: This routine computes the lattice given by the arrays of all conjugates of the basis elements of the ideal id. In particular, let n = r_{1} + 2r_{2} be the signature of the order ord, α_{1},…, α_{n} a ZZ-Basis of the ideal id and the conjugates of any algebraic number be sorted in the canonical way (see [29]), this routine creates the lattice of dimension n whose i-th lattice basis element is given by

(α_{i}^{(1)},…, α_{i}^{(r_{1})}, \sqrt{2} ℜα_{i}^{(r_{1}+1)},…, \sqrt{2} ℜα_{i}^{(r_{1}+r_{2})}, \sqrt{2} ℑα_{i}^{(r_{1}+1)},…, \sqrt{2} ℑα_{i}^{(r_{1}+r_{2})}) .

The enumeration environment of the lattice is also initialized by this function.

t void order lat(order ord, lattice &lat, lat enum env &env)

Task: Computes the lattice belonging to an order Description: This routine computes the lattice given by the arrays of all conjugates of the order basis elements. In particular, let n = r_{1} + 2r_{2} be the signature of the order ord, ω_{1},…, ω_{n} a ZZ-Basis of ord and the conjugates of any algebraic number be sorted in the canonical way (see [29]), this routine creates the lattice of dimension n whose i-th lattice basis element is given by

(ω_{i}^{(1)},…, ω_{i}^{(r_{1})}, \sqrt{2} ℜω_{i}^{(r_{1}+1)},…, \sqrt{2} ℜω_{i}^{(r_{1}+r_{2})}, \sqrt{2} ℑω_{i}^{(r_{1}+1)},…, \sqrt{2} ℑω_{i}^{(r_{1}+r_{2})}) .

The enumeration environment of the lattice is also initialized by this function.

anf elt lat elt to anf elt(lattice lat, lat elt lelt, order ord)

Task: Converts a lat elt to an anf elt Description: Assuming that lat refers to the canonical lattice of the order ord and elt is an element of lat, this function converts elt to an algebraic number (it basically copies the coefficients to the format as needed by the anf elt-structure).

anf elt lat elt ideal to anf elt(lattice lat, lat elt e, order ord, anf ideal id)

Task: Converts a lat elt to an anf elt Description: Assuming that lat refers to the canonical lattice of the ideal id of the order ord and elt is an element of lat, this function converts elt to an algebraic number.

5.11 Main KANT programs

The package KANT-2 includes a collection of main programs which are simple drivers for the most important features.

5.11.1 Arithmetic with orders, algebraic numbers and ideals

ceiling.x:

Demonstration program for anf ceilings. Reads an order O of absolute degree n over Q and asks for an algebraic number α, then computes and prints the ceiling determined by α, defined by:

∀i ∈ \{1,…, n\}: λ_{j} := \frac{|α^{(j)}|}{\sqrt[n]{|N(α)|}}.

Ceilings have been introduced by Mahler first and then used by Pohst and Fincke for solving norm equations in number fields. See [29, 12] for details.

disc.x:

Asks for an order and computes the order discriminant. If the order is the equation order of a polynomial this program of course computes the polynomial discriminant. The function used is (eventually) ipoly disc which employs a new fast method first described by Schwarz in [37].

ideal1.x:

Demonstration program for ideals. Reads a pure equation order O over ZZ and asks for two algebraic numbers α and β. Creates the ideal a := α · O + β · O, computes a ZZ-Basis presentation and its norm.

ideal2.x:

Demonstration program for prime ideal decomposition. Reads an order O, factorizes its discriminant. Then asks the user for a prime p and computes the prime ideal decomposition of pO.

minpoly.x:

Reads an order and algebraic numbers α. Computes the minimal polynomial of α and prints it.

minpoly shortest.x:

Reads an order O_{0}, computes the maximal order O (starting with O_{0}) and computes a primitive element α such that T_{2}(α) is minimal for all α ∈ O (which are primitive as well). The equation order generated by α is expected to have a comparatively small index in O and the polynomial coefficients of the minimal polynomial of α might be “well” conditioned. See [29] for details on T_{2}. This program prints the minimal polynomial of α and – for further use by KANT – its equation order (see Section 6.3, page 85 for a listing).

order arith.x:

Demonstration program for arithmetic with relative extensions. Asks for a “cascade” of pure extensions and then for pairs of algebraic numbers. Adds and multiplies the numbers. If the ground order is ZZ also the quotient is computed.

order lll.x:

Reads an order and LLL-reduces the basis of the conjugate lattice. The new order basis is usually much better conditioned than before.

order real.x:

Demonstration program for performing real arithmetic in an order. Reads an order and computes the zeroes of the minimal polynomial and the conjugates of the basis. Recalculates everything with higher precision several times.

shovec.x:

Reads an order and a lower and upper bound. Then calculates (up to sign) all non-zero algebraic numbers in the order whose T_{2} values is between these bounds. Prints all those numbers and their norms.

tower.x:

Reads a number of orders and then expects two order indices and an algebraic number of the first order. Tries to coerce the number into the second order.

5.11.2 Enlarging orders

ordmax.x:

Reads an order O and a table of primes with maximal exponents. Computes the maximal order, starting with O. This program assumes that the table of primes/exponents given is sufficient (see Section 6.2, page 84 for a listing).

round2.x:

Reads an order O and computes the maximal order, starting with O. The method used is Ford/Zassenhaus’ Round-2 [27].

5.11.3 Units, class groups and norm equations

classgroup.x:

Reads an order and then computes the class group structure. This is done by creating a factor basis of prime ideals and searching for relations [33].

units.x:

Reads an order and then computes the unit group structure. This is done either by Voronoi’s algorithm [4] (if the unit rank is one) or by the relation method which also can be used for the class group computation.

units classgroup.x:

Reads an order, then computes class group and unit group structure simultaneously. This is done by creating a factor basis and then searching for relations.

units rec1.x:

Reads an order and a table of subfield orders. First computes the unit groups of the subfield orders and “lifts” these units. If the system is still not maximal the same methods as in units.x are employed.

units rec2.x:

Like units rec1.x. The difference is that this program tries to find the subfield orders by itself. Does not work very well yet since it just looks for non-primitive elements of small T_{2}-value.

units t2.x:

Like units.x with the difference that the user can decide the size of the factor basis and which T_{2} bound has to be taken.

neq.x:

Solves a norm equation in a given order. The unit group in the order (or a subgroup of finite index) must be done before. After reading an order this program expects the right side of the norm equation and then either 1 or 0, depending on whether the user wants to have all non-associate solutions or just (maximal) one.

5.11.4 etc

v1 to v2.x:

Reads an order in KANT-1 format and prints it in KANT-2 format. This program only works if the Fortran interface of KANT-2 has been installed. It makes sense if one wants to convert long KANT-1 units into KANT-2 format. In all the other cases the KANT-2 input routine order read is compatible to the output function CMOUT2 of KANT-1.

5.12 Debugging functions

In the sequel we summarize a few of the MEM debugging features. We are grateful to Allan K. Steel who gave us a MEM-documentation [38] from which we cite here.

t void mem set showmem(t int val)

Task: set verbose messages Description: Sets whether various verbose messages are to be printed by MEM. A zero value for val means that the feature is to be disabled; otherwise the feature is enabled. This feature also is only enabled if the -DVERBOSE flag is specified when MEM is compiled. When enabled, MEM prints out a message when it has to call sbrk() for more process memory and when it coalesces all the free blocks in the workspace to get larger free blocks.

t void mem set mark(t int val)

Task: set a mark Description: Sets a new mark - if val is non zero then mem show active() (explained below) will only print blocks which have been allocated since the last mark was set. If val is zero then the mark is disabled. In either case, the statistics are all reset.

t void mem show stats()

Task: print MEM statistics Description: Prints out various statistics about the use of MEM. These statistics are only accounted if the option -DSTATS is specified when MEM is compiled. The output is as follows:

title explanation
total memory: total process memory used by MEM
total allocs: total number of calls to mem alloc … ()
total deletes: total number of calls to mem delete … ()
discrepancy: (total allocs) - (total deletes)
accesses: total number of calls to mem access()
get block: total number of calls to MEM internal get block()
small get blocks: number of blocks which have been on a small free list
small hit rate: (small get blocks) / (get block)
byte allocs: total number of calls to mem alloc …
word allocs: total number of calls to mem alloc words … ()
total extends: total number of calls to any mem extend … function
total reduces: total number of calls to any mem reduce … function

title explanation
reduce extra: total number of mem reduces which left a new block
total mallocs: total number of calls to mem malloc() and malloc()
total frees: total number of calls to free()
total reallocs: total number of calls to reallocs()
memory limit: current memory limit
extension size: current extension size
meta discrepancy: difference between current and last discrepancy

t void mem reset stats()

Task: Reset of statistics Description: Resets all statistical counters to 0.

t void mem show blocks()

Task: Prints workspace Description: Prints out the current workspace listing each block and its attributes. A list of the sizes of the various free lists is also printed. In the development version (see Section 7, page 88, the place in the source code where each active block has been allocated is also printed.

t void mem show active()

Task: Prints active bloks of workspace Description: Prints out a list of the current active blocks like in mem show blocks().

t int mem check workspace()

Task: Checks workspace Description: Checks the workspace for consistency. Returns 1 on success and dies upon failure.

t int mem valid handle(t handle h)

Task: Checks handle Description: Returns whether the handle h is valid, i.e. refers to an existing block.

t void mem check handle(t handle h)

Task: Checks handle and possibly dies Description: Checks whether the handle h is valid, i.e. refers to an existing block and dies upon failure. In the non-develop case, does nothing.

t void mem set trace handle(t handle h, t int val)

Task: Sets trace for a handle Description: If val is non-zero, marks the handle h to be traced. Otherwise, the handle h is unmarked for tracing. Again, only works in the development version. When a handle is traced, then when any reference to it (allocation, deletion, etc.) takes place, MEM prints a line telling the programmer that the handle has been referenced and where from.

t void mem set trace size(t int n, t int val)

Task: Sets trace for all handles pointing to blocks of a particular size Description: If val is non-zero, marks the size n to be traced. Otherwise, the size n is unmarked for tracing. Again, only works in the development version. When a size is traced, then when any reference to any block of that size takes place, MEM prints a line telling the programmer that the handle of the specific size has been referenced and where from.

Sample program listings

6.1 Elements of small T_{2}-value

Let O be an order and a an ideal of O. Then the following program computes (up to sign) all α ∈ a \ {0} subject to

T_{2}(α) := ∑_{j=1}^{n} |α^{(j)}|^{2} ≤ 100,

prints their coefficients referring to the order basis and their algebraic norm. In the sample input file we have O = ZZ[ ^{4} \sqrt{−5}] and a = 7 · O + (2 + ^{4} \sqrt{−5}) · O.

Source code:

#include "kant.h"
main()
/***************************************************************
t2.c  (Elements of small T2-value in a given ideal)
****************************************************************/
{
block_declarations;
order           ord;
anf_ideal       id;
lattice         lat;
lat_elt         vec;
lat_enum_env    env;
anf_elt         alpha;
integer_big     norm, den;
kant_start();
order_read(&ord);
order_reals_assure(ord);

        id = anf_ideal_2_read(ord);
        anf_ideal_lat(ord, id, &lat, &env);
        lat_chol_calc(lat);
        lat_enum_request_set_next(env);
        lat_enum_ubound(env) = conv_int_to_real(lat_chol_ring(lat), 100);
        while (lat_enum(lat, env))
        {
                vec   = lat_enum_act_coefs(env);
                alpha = lat_elt_ideal_to_anf_elt(lat, vec, ord, id);
                anf_elt_norm(ord, alpha, &norm, &den);
                printf("Norm of "); anf_elt_write(ord, alpha);
                printf(" is "); integer_write(norm); puts("");
                anf_elt_delete(ord, &alpha);
                integer_delref(norm);
                integer_delref(den);
        }
        lat_enum_delete(lat, &env);
        lat_delete(&lat);
        anf_ideal_delete(ord, &id);
        ring_delete(&ord);
}

Sample Input file:

(F=)
0, 0, 0, 5
(END=)
7 2 1 0 0 1

Sample Output file:

Norm of ( 1, -1, -1, -1 ) is 56
Norm of ( -2, 1, -1, -1 ) is 441
Norm of ( 2, -2, 0, -1 ) is 581
Norm of ( -3, -1, 0, -1 ) is 441
Norm of ( -1, 0, 0, -1 ) is 126
Norm of ( 1, 1, 0, -1 ) is 161
Norm of ( 0, -1, 1, -1 ) is 105
Norm of ( 2, 0, 1, -1 ) is 406
Norm of ( -1, -1, -2, 0 ) is 406
Norm of ( 1, 0, -2, 0 ) is 441
Norm of ( 0, -2, -1, 0 ) is 105

Norm of ( 2, -1, -1, 0 ) is 126
Norm of ( -3, 0, -1, 0 ) is 196
Norm of ( 4, 0, -1, 0 ) is 441
Norm of ( -1, 1, -1, 0 ) is 21
Norm of ( 1, 2, -1, 0 ) is 196
Norm of ( 1, -3, 0, 0 ) is 406
Norm of ( -4, -2, 0, 0 ) is 336
Norm of ( 3, -2, 0, 0 ) is 161
Norm of ( -2, -1, 0, 0 ) is 21

6.2 p-maximal overorders

For a given order O and a table of primes p_{i} with maximal exponents e_{i} this program computes the ∏ p_{i}-maximal overorder of O and prints it.

Source code:

#include "kant.h"
main(
)
/***************************************************************
ordmax.c (P-maximal overorders)
****************************************************************/
{
        block_declarations;
        order           ord, ordp;
        integer_big     p;
        t_int           maxex, i, ex;
        char            str[200];
        kant_start();
        while(order_read(&ord))
        {
                scanf("%d", &maxex); gets(str);
                for (i=maxex; i; i--)
                {
                        gets(str); p = integer_read(str);
                        scanf("%d", &ex); gets(str);
                        order_mult_assure(ord);
                        ordp   = order_max_p(ord, p, ex);
                        order_write(ordp);

                        order_delete(&ord);
                        integer_delref(p);
                        ord = ordp;
                }
                order_delete(&ordp);
        }
}

Sample Input file:

(TSTFLG=)
1
(FLD=)   6,  1,  0,  0,  0,  0,  0,  0,  0,  0,  6, *
 -2 -105 142 3402 -2248 -33727
1
1063
2

Sample Output file:

Calculation of p-maximal overorder...
Prime: 1063   maximal exponent: 2
(FLD=)   6, -2,  0,  0,  0,  0,  0,  0,  0,  0,  6, *
-2 -105 142 3402 -2248 -33727
1063 0 0 0 0 0 1063
0 1063 0 0 0 0 1063
0 0 1063 0 0 0 1063
0 0 0 1063 0 0 1063
0 0 0 0 1063 0 1063
-650 -908 -1050 -246 -170 1 1063

6.3 Nice primitive elements

Let F = Q(ρ) be a number field given via the minimal polynomial (over ZZ) of ρ. The following program computes an “optimal” generating element of F in the following sense: For all primitive algebraic integers of F it looks for a number α such that

T_{2}(α) = ∑_{j=1}^{n} |α^{(j)}|^{2}

is minimal. The minimal polynomial of α has usually very small coefficients and its index in the maximal order can be expected to be comparatively small. A similar method is proposed in [9].

Source code:

#include "kant.h"
main()
/**************************************************************
minpoly_shortest.c
****************************************************************/
{
block_declarations;
order           ord, ordmax, ordl, ordeq, Z;
anf_elt         alphal, alpha;
t_poly          pol;
kant_start();
Z = structure_z;
while(order_read(&ord))
{
order_disc_assure(ord);
cay_print("Discriminant of input order: %d\n",
            order_disc(ord));
ordmax = order_maximal(ord);
puts("Maximal order:"); order_write(ordmax);
ordl    = order_lll_reduce(ordmax);
alphal = order_shortest_primitive_elt(ordl);
alpha  = anf_elt_move(ordl, alphal, ordmax);
puts("Algebraic number (referring to basis
                        of maximal order): ");
anf_elt_write(ordmax, alpha); puts("");
pol   = anf_elt_minpoly(ordmax, alpha);
printf("Minimal polynomial: ");
poly_z_write(structure_pring_z, pol); puts("");
ordeq = order_equation_create(Z, pol);
order_disc_assure(ordeq);
puts("... and written as equation order:");
order_write(ordeq);
m_poly_z_delref(structure_pring_z, pol);
anf_elt_delete(ordmax,  &alpha);
anf_elt_delete(ordl, &alphal);

                order_delete(&ordl);
                order_delete(&ord);
                order_delete(&ordmax);
                order_delete(&ordeq);
        }
}

Sample Input file:

(F=)
0,-16,0,224,0,-320,0,6400
(END=)

Sample Output file:

Discriminant of input order: 29464083769154777791856640000000000
Maximal order:
(FLD=)   8,  2,  0,  0,  0,  0,  0,  0,  0,  0,  0, * 42575625
0 -16 0 224 0 -320 0 6400
44800 0 0 0 0 0 0 0 44800
0 22400 0 0 0 0 0 0 44800
0 0 11200 0 0 0 0 0 44800
0 0 0 5600 0 0 0 0 44800
22400 11200 0 0 1400 0 0 0 44800
0 11200 5600 0 0 700 0 0 44800
38400 0 3040 2800 640 0 10 0 44800
22400 15040 0 4784 0 624 0 1 44800
Algebraic number (referring to basis of maximal order):
( -8, 0, 4, -11, -3, -9, 5, 10 )
Minimal polynomial:
1 +  y + 4 * y^2 + - y^3 + 9 * y^4 +  y^5 + 4 * y^6 + - y^7 +  y^8
... and written as equation order:
(FLD=)   8, -1,  0,  0,  0,  0,  0,  0,  0,  0,  0, * 665244140625
-1 4 1 9 -1 4 1 1

Installation of KANT-2

KANT-2 is written in Standard-C, so it should run on every machine which has a Ccompiler. Probably even no 32-bit architecture is needed. A restriction might be given by the maximal memory of a computer: We guess that 2 MB is minimum for most of the KANT programs. On a machine with small memory one should resize the workspace in the main programs. Another problem might be the maximal allowed length of parameter names.

7.1 Installing KANT-2 on Unix machines

KANT-2 usually comes in a tared and compressed Unix file with a size of 1-2 MB. uncompressing and untaring should create a directory called V2 (or similar) containing the following subdirectories:

MEM:

Contains the memory management package of Allan Steel [38]. MEM is independent from the rest of the Platform or KANT.

Platform:

Contains all source files (currently around 600) of the Platform of the Cayley Group as announced in [2]. In addition, extended features for computations with polynomials or matrices or arbitrary rings are also in this directory.

Anf:

Here you find all sources of the number field package, currently roughly 250.

include:

All header files as used by the Platform and KANT. The number theoretic header files are:

header file  contents
kant.h  Meta header file for KANT programs
lattice.h Definition of the lattice package
anf.h  Main header, type declarations
anf anf.h  Macros for number fields
anf order.h Macros for orders

header file  contents
anf elt.h  Macros for algebraic numbers
anf ideal.h  Macros for ideals
anf ceiling.h Macros for ceilings

doc:

Here you find some documentation on KANT-2, especially the LaTEX sources of this manual.

lib:

Here will the KANT library libKant2.a be installed.

mains:

Sample main programs performing the most important features of KANT. These programs are explained in further detail in Section 5.11, page 76, the I/O format in Section 4.3.5, page 33. There are also sample input files in this directory (suffix .in) and reference output files of the Apollo workstations of the KANT Group (suffix .out.ref). The Shell script check runs a few of the main programs and compares the output files with the reference files (using diff to stdout).

f:

Collection of Fortran subroutines from KANT-1 which are needed if one wants to use the interface program v1 to v2.x. In the default installation procedure these objects will not be created.

Installing KANT-2: Firstly you have to decide if you want to run the develop or export version of KANT. The latter one will be several times faster whereas the first one does quite a few checks more. You simply have to edit the file Makefile.inc in the main KANT directory and change the lines indicated by the comments Develop version and Export version appropriately.

Now perform a make in the main KANT directory. This should do everything for you, in particular compile all sources, put the objects into the library V2/lib/libKant2.a and link the programs in V2/mains.

7.2 Installing KANT-2 on non-Unix machines

We have no idea how that works out (and never checked it yet) – but we think it should not be very much of a problem.

However, since MEM uses the Unix library function sbrk() it might be necessary to do a few changes in the function MEM/mem.c.

7.3 How to get KANT

You can get KANT-2 in a tared and compressed file via anonymous ftp from the node

                    ftp.math.uni-sb.de (=134.96.32.23)

in the directory /pub/kant.

KANT-2 – Installation Hints 90

If you want to use the KANT features via dialog, you have to do this through Cayley V4 – e-mail to John Cannon (john@maths.su.oz.au) for further information.

Bibliography

[1] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355–380.

[2] M. Bofinger, W. Bosma, J. Cannon, B. Cox, G. Matthews, J. Richardson and A. Steel, A platform for implementing algebraic software, Manuscript, Sydney 1991.

[3] R. P. Brent, MP, A FORTRAN multiple precision arithmetic package, Math. Software 4 (1978), 71–81.

[4] J. Buchmann, A generalization of Voronoi’s unit algorithm I, II, J. Number Theory 20 (1985), 177–209.

[5] J. Buchmann and S. Düllmann, A probabilistic class group and regulator algorithm and its implementation, in: A. Pethö, M. E. Pohst, H. C. Williams, H. G. Zimmer (eds.), “Computational Number Theory”, Walter de Gruyter 1991, 53–72.

[6] J. Buchmann and A. Pethö, On the computation of independent units in number fields by Dirichlet’s method, Math. Comp. 52 (1989), 149–159.

[7] J. Buchmann und H.C. Williams, On principal ideal testing in algebraic number fields, J. Symbolic Computation, J. Symbolic Computation 4 (1987), 11–19.

[8] J. J. Cannon, An introduction to the group theory language Cayley, in: “Computational group theory” (Proc. IMS Symp. on Computational Group Theory, Durham 1982), M. D. Atkinson (ed.), Academic Press, London 1984, 143–182.

[9] H. Cohen and F. Diaz y Diaz, A polynomial reduction algorithm, S’eminaire de Th’eorie des Nombres de Bordeaux 3 (1991), 351–360.

[10] H. Cohen, “A course in computational algebraic number theory”, Springer, to appear.

[11] M. Daberkow, “Bestimmung relativer Ganzheitsbasen in relativquadratischen Zahlkörpern mit beliebiger Klassenzahl”, Diplomarbeit, Düsseldorf 1993.

[12] U. Fincke, “Ein Ellipsoidverfahren zur Lösung von Normgleichungen”, Dissertation, Düsseldorf 1984.

[13] U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), 463–471.

[14] J. L. Hafner and K. S. McCurley, A rigorous subexponential algorithm for computation of class groups, IBM research report 1989.

[15] E. Hecke, Vorlesungen über die Theorie der algebraischen Zahlen, 2nd ed., Chelsea, New York, 1970.

[16] M. Holzberg, “Zur Berechnung der Einheitengruppe der Galoisschen Hüllen von Zahlkörpern vierten Grades”, Diplomarbeit, Düsseldorf 1991.

[17] D. E. Knuth, “The art of computer programming”, Vol. 2: Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass. 1981.

[18] T. Kubota, Über den bizyklischen biquadratischen Zahlkörper, Nagoya Math. J. 10 (1956), 65–85.

[19] E. Landau, “Einführung in die elementare und analytische Theorie der algebraischen Zahlen und der Ideale”, 2nd ed., Chelsea, New York 1949.

[20] A. K. Lenstra, H. W. Lenstra Jr. and L. Lovasz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.

[21] K. Mahler, Inequalities for ideal bases in algebraic number fields, J. Austral. Math. Soc. 4 (1964), 425–427.

[22] H. Marschang, “Über die Berechnung von Ganzheitsbasen algebraischer Zahlkörper”, Diplomarbeit, Düsseldorf 1990.

[23] W. Narkiewicz, “Elementary and analytic theory of algebraic numbers”, 2nd ed., Springer 1990.

[24] M. Pohst, On computing isomorphisms of equation orders, Math. Comp. 48 (1987), 309–314.

[25] M. Pohst, A modification of the LLL–algorithm, J. Symbolic Computation, 4 (1987), 123–128.

[26] M. Pohst, On computing fundamental units, submitted to Math. Comp.

[27] M. E. Pohst, “Computational algebraic number theory”, Birkhäuser, to appear 1993.

[28] M. Pohst and H. Zassenhaus, Über die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlkörper, J. Reine Angew. Math. 361 (1985), 50–72.

[29] M. Pohst and H. Zassenhaus, “Algorithmic Algebraic Number Theory”, Cambridge University Press 1989.

[30] Jim Richardson, The Blockhandler and the Bitfield Package, Research Report 89-1, Department of Pure Mathematics, University of Sydney 1989.

[31] J. Graf v. Schmettow, “Über die Berechnung von Klassengruppen algebraischer Zahlkörper”, Diplomarbeit, Düsseldorf 1987.

[32] J. Graf v. Schmettow, KANT – a tool for computations in algebraic number fields, in: A. Pethö, M. E. Pohst, H. C. Williams, H. G. Zimmer (eds.), “Computational Number Theory”, Walter de Gruyter 1991, 321–330.

[33] J. Graf v. Schmettow, “Beiträge zur Klassengruppenberechnung”, Dissertation, Düsseldorf 1991.

[34] J. Graf v. Schmettow, A new principal ideal test for algebraic number fields, submitted to J. Number Theory.

[35] M. Schönert et al., “GAP – Groups, Algorithms and Programming”, User Manual, RWTH Aachen 1992.

[36] C. P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, in: Proc. of the FCT 1991, Springer Lecture Notes in Comp. Sci., to appear.

[37] A. Schwarz, M. Pohst and F. Diaz y Diaz, A table of quintics, Manuscript, Düsseldorf 1992.

[38] A. K. Steel, “MEM– the Cayley V4 memory manager”, Manual, Sydney 1992.

[39] H. Zassenhaus, On the second round of the maximal order program, in: “Applications of Number Theory to Numerical Analysis”, 398–431, Academic Press, New York 1972.

[40] R. Zimmert, Ideale kleiner Norm in Idealklassen und eine Regulatorabschätzung, Invent. math. 62 (1981), 367–380.