### Functions related to general number fields

#### Number field structures

Let K = Q[X] / (T) a number field, Z_K its ring of integers, T belongs to Z[X] is monic. Three basic number field structures can be associated to K in GP:

* nf denotes a number field, i.e.a data structure output by `nfinit`. This contains the basic arithmetic data associated to the number field: signature, maximal order (given by a basis `nf.zk`), discriminant, defining polynomial T, etc.

* bnf denotes a "Buchmann's number field", i.e.a data structure output by `bnfinit`. This contains nf and the deeper invariants of the field: units U(K), class group Cl(K), as well as technical data required to solve the two associated discrete logarithm problems.

* bnr denotes a "ray number field", i.e.a data structure output by `bnrinit`, corresponding to the ray class group structure of the field, for some modulus f. It contains a bnf, the modulus f, the ray class group Cl_f(K) and data associated to the discrete logarithm problem therein.

#### Algebraic numbers and ideals

An algebraic number belonging to K = Q[X]/(T) is given as

* a `t_INT`, `t_FRAC` or `t_POL` (implicitly modulo T), or

* a `t_POLMOD` (modulo T), or

* a `t_COL` `v` of dimension N = [K:Q], representing the element in terms of the computed integral basis, as `sum(i = 1, N,v[i] * nf.zk[i])`. Note that a `t_VEC` will not be recognized.

An ideal is given in any of the following ways:

* an algebraic number in one of the above forms, defining a principal ideal.

* a prime ideal, i.e.a 5-component vector in the format output by `idealprimedec`.

* a `t_MAT`, square and in Hermite Normal Form (or at least upper triangular with non-negative coefficients), whose columns represent a basis of the ideal.

One may use `idealhnf` to convert an ideal to the last (preferred) format.

Note. Some routines accept non-square matrices, but using this format is strongly discouraged. Nevertheless, their behaviour is as follows: If strictly less than N = [K:Q] generators are given, it is assumed they form a Z_K-basis. If N or more are given, a Z-basis is assumed. If exactly N are given, it is further assumed the matrix is in HNF. If any of these assumptions is not correct the behaviour of the routine is undefined.

* an idele is a 2-component vector, the first being an ideal as above, the second being a R_1+R_2-component row vector giving Archimedean information, as complex numbers.

#### Finite abelian groups

A finite abelian group G in user-readable format is given by its Smith Normal Form as a pair [h,d] or triple [h,d,g]. Here h is the cardinality of G, (d_i) is the vector of elementary divisors, and (g_i) is a vector of generators. In short, G = oplus_{i `<=` n} (Z/d_iZ) g_i, with d_n | ... | d_2 | d_1 and prod d_i = h. This information can also be retrieved as G.`no`, G.`cyc` and G.`gen`.

* a character on the abelian group oplus (Z/d_iZ) g_i is given by a row vector chi = [a_1,...,a_n] such that chi(prod g_i^{n_i}) = exp(2iPi sum a_i n_i / d_i).

* given such a structure, a subgroup H is input as a square matrix, whose column express generators of H on the given generators g_i. Note that the absolute value of the determinant of that matrix is equal to the index (G:H).

#### Relative extensions

When defining a relative extension, the base field nf must be defined by a variable having a lower priority (see Section [Label: se:priority]) than the variable defining the extension. For example, you may use the variable name y to define the base field, and x to define the relative extension.

* rnf denotes a relative number field, i.e.a data structure output by `rnfinit`.

* A relative matrix is a matrix whose entries are elements of a (fixed) number field nf, always expressed as column vectors on the integral basis `nf.zk`. Hence it is a matrix of vectors.

* An ideal list is a row vector of (fractional) ideals of the number field nf.

* A pseudo-matrix is a pair (A,I) where A is a relative matrix and I an ideal list whose length is the same as the number of columns of A. This pair is represented by a 2-component row vector.

* The projective module generated by a pseudo-matrix (A,I) is the sum sum_i {a}_j A_j where the {a}_j are the ideals of I and A_j is the j-th column of A.

* A pseudo-matrix (A,I) is a pseudo-basis of the module it generates if A is a square matrix with non-zero determinant and all the ideals of I are non-zero. We say that it is in Hermite Normal Form (HNF) if it is upper triangular and all the elements of the diagonal are equal to 1.

* The determinant of a pseudo-basis (A,I) is the ideal equal to the product of the determinant of A by all the ideals of I. The determinant of a pseudo-matrix is the determinant of any pseudo-basis of the module it generates.

#### Class field theory

A modulus, in the sense of class field theory, is a divisor supported on the non-complex places of K. In PARI terms, this means either an ordinary ideal I as above (no archimedean component), or a pair [I,a], where a is a vector with r_1 {0,1}-components, corresponding to the infinite part of the divisor. More precisely, the i-th component of a corresponds to the real embedding associated to the i-th real root of `K.roots`. (That ordering is not canonical, but well defined once a defining polynomial for K is chosen.) For instance, `[1, [1,1]]` is a modulus for a real quadratic field, allowing ramification at any of the two places at infinity.

A bid or "big ideal" is a structure output by `idealstar` needed to compute in (Z_K/I)^*, where I is a modulus in the above sense. If is a finite abelian group as described above, supplemented by technical data needed to solve discrete log problems.

Finally we explain how to input ray number fields (or bnr), using class field theory. These are defined by a triple a1, a2, a3, where the defining set [a1,a2,a3] can have any of the following forms: [bnr], [bnr,subgroup], [bnf,module], [bnf,module,subgroup].

* bnf is as output by `bnfinit`, where units are mandatory unless the modulus is trivial; bnr is as output by `bnrinit`. This is the ground field K.

* module is a modulus f, as described above.

* subgroup a subgroup of the ray class group modulo f of K. As described above, this is input as a square matrix expressing generators of a subgroup of the ray class group `bnr.clgp` on the given generators.

The corresponding bnr is the subfield of the ray class field of K modulo f, fixed by the given subgroup.

#### General use

All the functions which are specific to relative extensions, number fields, Buchmann's number fields, Buchmann's number rays, share the prefix `rnf`, `nf`, `bnf`, `bnr` respectively. They take as first argument a number field of that precise type, respectively output by `rnfinit`, `nfinit`, `bnfinit`, and `bnrinit`.

However, and even though it may not be specified in the descriptions of the functions below, it is permissible, if the function expects a nf, to use a bnf instead, which contains much more information. On the other hand, if the function requires a `bnf`, it will not launch `bnfinit` for you, which is a costly operation. Instead, it will give you a specific error message. In short, the types `nf` `<=` `bnf` `<=` `bnr` are ordered, each function requires a minimal type to work properly, but you may always substitute a larger type.

The data types corresponding to the structures described above are rather complicated. Thus, as we already have seen it with elliptic curves, GP provides "member functions" to retrieve data from these structures (once they have been initialized of course). The relevant types of number fields are indicated between parentheses:

`bid` (bnr, ) : bid ideal structure.

`bnf` (bnr, bnf ) : Buchmann's number field.

`clgp` (bnr, bnf ) : classgroup. This one admits the following three subclasses:

`cyc` : cyclic decomposition (SNF).

`gen` : generators.

`no` : number of elements.

`diff` (bnr, bnf, nf ) : the different ideal.

`codiff` (bnr, bnf, nf ) : the codifferent (inverse of the different in the ideal group).

`disc` (bnr, bnf, nf ) : discriminant.

`fu` (bnr, bnf, nf ) : fundamental units.

`index` (bnr, bnf, nf ) : index of the power order in the ring of integers.

`nf` (bnr, bnf, nf ) : number field.

`r1` (bnr, bnf, nf ) : the number of real embeddings.

`r2` (bnr, bnf, nf ) : the number of pairs of complex embeddings.

`reg` (bnr, bnf, ) : regulator.

`roots` (bnr, bnf, nf ) : roots of the polynomial generating the field.

`t2` (bnr, bnf, nf ) : the T2 matrix (see `nfinit`).

`tu` (bnr, bnf, ) : a generator for the torsion units.

`tufu` (bnr, bnf, ) : [w,u_1,...,u_r], (u_i) is a vector of fundamental units, w generates the torsion units.

`zk` (bnr, bnf, nf ) : integral basis, i.e.a Z-basis of the maximal order.

For instance, assume that bnf = `bnfinit`(pol), for some polynomial. Then `bnf.clgp` retrieves the class group, and `bnf.clgp.no` the class number. If we had set bnf = `nfinit`(pol), both would have output an error message. All these functions are completely recursive, thus for instance `bnr.bnf.nf.zk` will yield the maximal order of bnr, which you could get directly with a simple `bnr.zk`.

#### Class group, units, and the GRH

Some of the functions starting with `bnf` are implementations of the sub-exponential algorithms for finding class and unit groups under GRH, due to Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier. The general call to the functions concerning class groups of general number fields (i.e.excluding `quadclassunit`) involves a polynomial P and a technical vector tech = [c, c2, nrpid ], where the parameters are to be understood as follows:

P is the defining polynomial for the number field, which must be in Z[X], irreducible and monic. In fact, if you supply a non-monic polynomial at this point, `gp` issues a warning, then transforms your polynomial so that it becomes monic. The `nfinit` routine will return a different result in this case: instead of `res`, you get a vector `[res,Mod(a,Q)]`, where `Mod(a,Q) = Mod(X,P)` gives the change of variables. In all other routines, the variable change is simply lost.

The numbers c `<=` c_2 are positive real numbers which control the execution time and the stack size. For a given c, set c_2 = c to get maximum speed. To get a rigorous result under GRH you must take c2 `>=` 12 (or c2 `>=` 6 in P is quadratic). Reasonable values for c are between 0.1 and 2. The default is c = c_2 = 0.3.

nrpid is the maximal number of small norm relations associated to each ideal in the factor base. Set it to 0 to disable the search for small norm relations. Otherwise, reasonable values are between 4 and 20. The default is 4.

Warning. Make sure you understand the above! By default, most of the `bnf` routines depend on the correctness of a heuristic assumption which is stronger than the GRH. In particular, any of the class number, class group structure, class group generators, regulator and fundamental units may be wrong, independently of each other. Any result computed from such a `bnf` may be wrong. The only guarantee is that the units given generate a subgroup of finite index in the full unit group. In practice, very few counter-examples are known, requiring unlucky random seeds. No counter-example has been reported for c_2 = 0.5 (which should be almost as fast as c_2 = 0.3, and shall very probably become the default). If you use c_2 = 12, then everything is correct assuming the GRH holds. You can use `bnfcertify` to certify the computations unconditionally.

Remarks.

Apart from the polynomial P, you do not need to supply the technical parameters (under the library you still need to send at least an empty vector, coded as `NULL`). However, should you choose to set some of them, they must be given in the requested order. For example, if you want to specify a given value of nrpid, you must give some values as well for c and c_2, and provide a vector [c,c_2,nrpid].

Note also that you can use an nf instead of P, which avoids recomputing the integral basis and analogous quantities.

#### bnfcertify(bnf)

bnf being as output by `bnfinit`, checks whether the result is correct, i.e.whether it is possible to remove the assumption of the Generalized Riemann Hypothesis. It is correct if and only if the answer is 1. If it is incorrect, the program may output some error message, or loop indefinitely. You can check its progress by increasing the debug level.

The library syntax is certifybuchall(bnf), and the result is a C long.

#### bnfclassunit(P,{flag = 0},{tech = []})

this function is DEPRECATED, use `bnfinit`.

Buchmann's sub-exponential algorithm for computing the class group, the regulator and a system of fundamental units of the general algebraic number field K defined by the irreducible polynomial P with integer coefficients.

The result of this function is a vector v with many components, which for ease of presentation is in fact output as a one column matrix. It is not a bnf, you need `bnfinit` for that. First we describe the default behaviour (flag = 0):

v[1] is equal to the polynomial P.

v[2] is the 2-component vector [r1,r2], where r1 and r2 are as usual the number of real and half the number of complex embeddings of the number field K.

v[3] is the 2-component vector containing the field discriminant and the index.

v[4] is an integral basis in Hermite normal form.

v[5] (`v.clgp`) is a 3-component vector containing the class number (`v.clgp.no`), the structure of the class group as a product of cyclic groups of order n_i (`v.clgp.cyc`), and the corresponding generators of the class group of respective orders n_i (`v.clgp.gen`).

v[6] (`v.reg`) is the regulator computed to an accuracy which is the maximum of an internally determined accuracy and of the default.

v[7] is deprecated, maintained for backward compatibility and always equal to 1.

v[8] (`v.tu`) a vector with 2 components, the first being the number w of roots of unity in K and the second a primitive w-th root of unity expressed as a polynomial.

v[9] (`v.fu`) is a system of fundamental units also expressed as polynomials.

If flag = 1, and the precision happens to be insufficient for obtaining the fundamental units, the internal precision is doubled and the computation redone, until the exact results are obtained. Be warned that this can take a very long time when the coefficients of the fundamental units on the integral basis are very large, for example in large real quadratic fields. For this case, there are alternate compact representations for algebraic numbers, implemented in PARI but currently not available in GP.

If flag = 2, the fundamental units and roots of unity are not computed. Hence the result has only 7 components, the first seven ones.

The library syntax is bnfclassunit0(P,flag,tech,prec).

#### bnfclgp(P,{tech = []})

as `bnfinit`, but only outputs `bnf.clgp`, i.e.the class group.

The library syntax is classgrouponly(P,tech,prec), where tech is as described under `bnfinit`.

#### bnfdecodemodule(nf,m)

if m is a module as output in the first component of an extension given by `bnrdisclist`, outputs the true module.

The library syntax is decodemodule(nf,m).

#### bnfinit(P,{flag = 0},{tech = []})

initializes a bnf structure. Used in programs such as `bnfisprincipal`, `bnfisunit` or `bnfnarrow`. By default, the results are conditional on a heuristic strengthening of the GRH, see [Label: se:GRHbnf]. The result is a 10-component vector bnf.

This implements Buchmann's sub-exponential algorithm for computing the class group, the regulator and a system of fundamental units of the general algebraic number field K defined by the irreducible polynomial P with integer coefficients.

If the precision becomes insufficient, `gp` outputs a warning (`fundamental units too large, not given`) and does not strive to compute the units by default (flag = 0).

When flag = 1, we insist on finding the fundamental units exactly. Be warned that this can take a very long time when the coefficients of the fundamental units on the integral basis are very large. If the fundamental units are simply too large to be represented in this form, an error message is issued. They could be obtained using the so-called compact representation of algebraic numbers as a formal product of algebraic integers. The latter is implemented internally but not publicly accessible yet.

When flag = 2, on the contrary, it is initially agreed that units are not computed. Note that the resulting bnf will not be suitable for `bnrinit`, and that this flag provides negligible time savings compared to the default. In short, it is deprecated.

When flag = 3, computes a very small version of `bnfinit`, a "small Buchmann's number field" (or sbnf for short) which contains enough information to recover the full bnf vector very rapidly, but which is much smaller and hence easy to store and print. It is supposed to be used in conjunction with `bnfmake`.

tech is a technical vector (empty by default, see [Label: se:GRHbnf]). Careful use of this parameter may speed up your computations considerably.

The components of a bnf or sbnf are technical and never used by the casual user. In fact: never access a component directly, always use a proper member function. However, for the sake of completeness and internal documentation, their description is as follows. We use the notations explained in the book by H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Maths 138, Springer-Verlag, 1993, Section 6.5, and subsection 6.5.5 in particular.

bnf[1] contains the matrix W, i.e.the matrix in Hermite normal form giving relations for the class group on prime ideal generators (wp_i)_{1 `<=` i `<=` r}.

bnf[2] contains the matrix B, i.e.the matrix containing the expressions of the prime ideal factorbase in terms of the wp_i. It is an r x c matrix.

bnf[3] contains the complex logarithmic embeddings of the system of fundamental units which has been found. It is an (r_1+r_2) x (r_1+r_2-1) matrix.

bnf[4] contains the matrix M"_C of Archimedean components of the relations of the matrix (W|B).

bnf[5] contains the prime factor base, i.e.the list of prime ideals used in finding the relations.

bnf[6] used to contain a permutation of the prime factor base, but has been obsoleted. It contains a dummy 0.

bnf[7] or `bnf.nf` is equal to the number field data nf as would be given by `nfinit`.

bnf[8] is a vector containing the classgroup `bnf.clgp` as a finite abelian group, the regulator `bnf.reg`, a 1 (used to contain an obsolete "check number"), the number of roots of unity and a generator `bnf.tu`, the fundamental units `bnf.fu`.

bnf[9] is a 3-element row vector used in `bnfisprincipal` only and obtained as follows. Let D = U W V obtained by applying the Smith normal form algorithm to the matrix W ( = bnf[1]) and let U_r be the reduction of U modulo D. The first elements of the factorbase are given (in terms of `bnf.gen`) by the columns of U_r, with Archimedean component g_a; let also GD_a be the Archimedean components of the generators of the (principal) ideals defined by the `bnf.gen[i]^bnf.cyc[i]`. Then bnf[9] = [U_r, g_a, GD_a].

bnf[10] is by default unused and set equal to 0. This field is used to store further information about the field as it becomes available, which is rarely needed, hence would be too expensive to compute during the initial `bnfinit` call. For instance, the generators of the principal ideals `bnf.gen[i]^bnf.cyc[i]` (during a call to `bnrisprincipal`), or those corresponding to the relations in W and B (when the `bnf` internal precision needs to be increased).

An sbnf is a 12 component vector v, as follows. Let bnf be the result of a full `bnfinit`, complete with units. Then v[1] is the polynomial P, v[2] is the number of real embeddings r_1, v[3] is the field discriminant, v[4] is the integral basis, v[5] is the list of roots as in the sixth component of `nfinit`, v[6] is the matrix MD of `nfinit` giving a Z-basis of the different, v[7] is the matrix `W` = bnf[1], v[8] is the matrix `matalpha` = bnf[2], v[9] is the prime ideal factor base bnf[5] coded in a compact way, and ordered according to the permutation bnf[6], v[10] is the 2-component vector giving the number of roots of unity and a generator, expressed on the integral basis, v[11] is the list of fundamental units, expressed on the integral basis, v[12] is a vector containing the algebraic numbers alpha corresponding to the columns of the matrix `matalpha`, expressed on the integral basis.

Note that all the components are exact (integral or rational), except for the roots in v[5]. Note also that member functions will not work on sbnf, you have to use `bnfmake` explicitly first.

The library syntax is bnfinit0(P,flag,tech,prec).

#### bnfisintnorm(bnf,x)

computes a complete system of solutions (modulo units of positive norm) of the absolute norm equation \Norm(a) = x, where a is an integer in bnf. If bnf has not been certified, the correctness of the result depends on the validity of GRH.

See also `bnfisnorm`.

The library syntax is bnfisintnorm(bnf,x).

#### bnfisnorm(bnf,x,{flag = 1})

tries to tell whether the rational number x is the norm of some element y in bnf. Returns a vector [a,b] where x = Norm(a)*b. Looks for a solution which is an S-unit, with S a certain set of prime ideals containing (among others) all primes dividing x. If bnf is known to be Galois, set flag = 0 (in this case, x is a norm iff b = 1). If flag is non zero the program adds to S the following prime ideals, depending on the sign of flag. If flag > 0, the ideals of norm less than flag. And if flag < 0 the ideals dividing flag.

Assuming GRH, the answer is guaranteed (i.e.x is a norm iff b = 1), if S contains all primes less than 12log(\disc(Bnf))^2, where Bnf is the Galois closure of bnf.

See also `bnfisintnorm`.

The library syntax is bnfisnorm(bnf,x,flag,prec), where flag and prec are `long`s.

#### bnfissunit(bnf,sfu,x)

bnf being output by `bnfinit`, sfu by `bnfsunit`, gives the column vector of exponents of x on the fundamental S-units and the roots of unity. If x is not a unit, outputs an empty vector.

The library syntax is bnfissunit(bnf,sfu,x).

#### bnfisprincipal(bnf,x,{flag = 1})

bnf being the number field data output by `bnfinit`, and x being either a Z-basis of an ideal in the number field (not necessarily in HNF) or a prime ideal in the format output by the function `idealprimedec`, this function tests whether the ideal is principal or not. The result is more complete than a simple true/false answer: it gives a row vector [v_1,v_2], where

v_1 is the vector of components c_i of the class of the ideal x in the class group, expressed on the generators g_i given by `bnfinit` (specifically `bnf.gen`). The c_i are chosen so that 0 `<=` c_i < n_i where n_i is the order of g_i (the vector of n_i being `bnf.cyc`).

v_2 gives on the integral basis the components of alpha such that x = alpha prod_ig_i^{c_i}. In particular, x is principal if and only if v_1 is equal to the zero vector. In the latter case, x = alpha Z_K where alpha is given by v_2. Note that if alpha is too large to be given, a warning message will be printed and v_2 will be set equal to the empty vector.

If flag = 0, outputs only v_1, which is much easier to compute.

If flag = 2, does as if flag were 0, but doubles the precision until a result is obtained.

If flag = 3, as in the default behaviour (flag = 1), but doubles the precision until a result is obtained.

The user is warned that these two last setting may induce very lengthy computations.

The library syntax is isprincipalall(bnf,x,flag).

#### bnfisunit(bnf,x)

bnf being the number field data output by `bnfinit` and x being an algebraic number (type integer, rational or polmod), this outputs the decomposition of x on the fundamental units and the roots of unity if x is a unit, the empty vector otherwise. More precisely, if u_1,...,u_r are the fundamental units, and zeta is the generator of the group of roots of unity (`bnf.tu`), the output is a vector [x_1,...,x_r,x_{r+1}] such that x = u_1^{x_1}... u_r^{x_r}.zeta^{x_{r+1}}. The x_i are integers for i `<=` r and is an integer modulo the order of zeta for i = r+1.

The library syntax is isunit(bnf,x).

#### bnfmake(sbnf)

sbnf being a "small bnf" as output by `bnfinit`(x,3), computes the complete `bnfinit` information. The result is not identical to what `bnfinit` would yield, but is functionally identical. The execution time is very small compared to a complete `bnfinit`. Note that if the default precision in `gp` (or prec in library mode) is greater than the precision of the roots sbnf[5], these are recomputed so as to get a result with greater accuracy.

Note that the member functions are not available for sbnf, you have to use `bnfmake` explicitly first.

The library syntax is makebigbnf(sbnf,prec), where prec is a C long integer.

#### bnfnarrow(bnf)

bnf being as output by `bnfinit`, computes the narrow class group of bnf. The output is a 3-component row vector v analogous to the corresponding class group component `bnf.clgp` (`bnf[8][1]`): the first component is the narrow class number `v.no`, the second component is a vector containing the SNF cyclic components `v.cyc` of the narrow class group, and the third is a vector giving the generators of the corresponding `v.gen` cyclic groups. Note that this function is a special case of `bnrinit`.

The library syntax is buchnarrow(bnf).

#### bnfsignunit(bnf)

bnf being as output by `bnfinit`, this computes an r_1 x (r_1+r_2-1) matrix having ±1 components, giving the signs of the real embeddings of the fundamental units. The following functions compute generators for the totally positive units:

    /* exponents of totally positive units generators on bnf.tufu */
     tpuexpo(bnf)=
     { local(S,d,K);

       S = bnfsignunit(bnf); d = matsize(S);
       S = matrix(d[1],d[2], i,j, if (S[i,j] < 0, 1,0));
       S = concat(vectorv(d[1],i,1), S);   \\ add sign(-1)
       K = lift(matker(S * Mod(1,2)));
       if (K, mathnfmodid(K, 2), 2*matid(d[1]))
     }

     /* totally positive units */
     tpu(bnf)=
     { local(vu = bnf.tufu, ex = tpuexpo(bnf));

       vector(#ex-1, i, factorback(vu, ex[,i+1]))  \\ ex[,1] is 1
     }

The library syntax is signunits(bnf).

#### bnfreg(bnf)

bnf being as output by `bnfinit`, computes its regulator.

The library syntax is regulator(bnf,tech,prec), where tech is as in `bnfinit`.

#### bnfsunit(bnf,S)

computes the fundamental S-units of the number field bnf (output by `bnfinit`), where S is a list of prime ideals (output by `idealprimedec`). The output is a vector v with 6 components.

v[1] gives a minimal system of (integral) generators of the S-unit group modulo the unit group.

v[2] contains technical data needed by `bnfissunit`.

v[3] is an empty vector (used to give the logarithmic embeddings of the generators in v[1] in version 2.0.16).

v[4] is the S-regulator (this is the product of the regulator, the determinant of v[2] and the natural logarithms of the norms of the ideals in S).

v[5] gives the S-class group structure, in the usual format (a row vector whose three components give in order the S-class number, the cyclic components and the generators).

v[6] is a copy of S.

The library syntax is bnfsunit(bnf,S,prec).

#### bnfunit(bnf)

bnf being as output by `bnfinit`, outputs the vector of fundamental units of the number field.

This function is mostly useless, since it will only succeed if bnf contains the units, in which case `bnf.fu` is recommanded instead, or bnf was produced with `bnfinit(,,2)`, which is itself deprecated.

The library syntax is buchfu(bnf).

#### bnrL1(bnr,{subgroup},{flag = 0})

bnr being the number field data which is output by `bnrinit(,,1)` and subgroup being a square matrix defining a congruence subgroup of the ray class group corresponding to bnr (the trivial congruence subgroup if omitted), returns for each character chi of the ray class group which is trivial on this subgroup, the value at s = 1 (or s = 0) of the abelian L-function associated to chi. For the value at s = 0, the function returns in fact for each character chi a vector [r_chi , c_chi] where r_chi is the order of L(s, chi) at s = 0 and c_chi the first non-zero term in the expansion of L(s, chi) at s = 0; in other words

L(s, chi) = c_chi.s^{r_chi} + O(s^{r_chi + 1})

near 0. flag is optional, default value is 0; its binary digits mean 1: compute at s = 1 if set to 1 or s = 0 if set to 0, 2: compute the primitive L-functions associated to chi if set to 0 or the L-function with Euler factors at prime ideals dividing the modulus of bnr removed if set to 1 (this is the so-called L_S(s, chi) function where S is the set of infinite places of the number field together with the finite prime ideals dividing the modulus of bnr, see the example below), 3: returns also the character. Example:

    bnf = bnfinit(x^2 - 229);
     bnr = bnrinit(bnf,1,1);
     bnrL1(bnr)

returns the order and the first non-zero term of the abelian L-functions L(s, chi) at s = 0 where chi runs through the characters of the class group of Q(sqrt{229}). Then

    bnr2 = bnrinit(bnf,2,1);
     bnrL1(bnr2,,2)

returns the order and the first non-zero terms of the abelian L-functions L_S(s, chi) at s = 0 where chi runs through the characters of the class group of Q(sqrt{229}) and S is the set of infinite places of Q(sqrt{229}) together with the finite prime 2. Note that the ray class group modulo 2 is in fact the class group, so `bnrL1(bnr2,0)` returns exactly the same answer as `bnrL1(bnr,0)`.

The library syntax is bnrL1(bnr,subgroup,flag,prec), where an omitted subgroup is coded as `NULL`.

#### bnrclass(bnf,ideal,{flag = 0})

this function is DEPRECATED, use `bnrinit`.

bnf being as output by `bnfinit` (the units are mandatory unless the ideal is trivial), and ideal being a modulus, computes the ray class group of the number field for the modulus ideal, as a finite abelian group.

The library syntax is bnrclass0(bnf,ideal,flag).

#### bnrclassno(bnf,I)

bnf being as output by `bnfinit` (units are mandatory unless the ideal is trivial), and I being a modulus, computes the ray class number of the number field for the modulus I. This is faster than `bnrinit` and should be used if only the ray class number is desired. See `bnrclassnolist` if you need ray class numbers for all moduli less than some bound.

The library syntax is bnrclassno(bnf,I).

#### bnrclassnolist(bnf,list)

bnf being as output by `bnfinit`, and list being a list of moduli (with units) as output by `ideallist` or `ideallistarch`, outputs the list of the class numbers of the corresponding ray class groups. To compute a single class number, `bnrclassno` is more efficient.

    ? bnf = bnfinit(x^2 - 2);
     ? L = ideallist(bnf, 100, 2);
     ? H = bnrclassnolist(bnf, L);
     ? H[98]
     %4 = [1, 3, 1]
     ? l = L[1][98]; ids = vector(#l, i, l[i].mod[1])
     %5 = [[98, 88; 0, 1], [14, 0; 0, 7], [98, 10; 0, 1]]

The weird `l[i].mod[1]`, is the first component of `l[i].mod`, i.e. the finite part of the conductor. (This is cosmetic: since by construction the archimedean part is trivial, I do not want to see it). This tells us that the ray class groups modulo the ideals of norm 98 (printed as `%5`) have respectively order 1, 3 and 1. Indeed, we may check directly :

    ? bnrclassno(bnf, ids[2])
     %6 = 3

The library syntax is bnrclassnolist(bnf,list).

#### bnrconductor(a_1,{a_2},{a_3}, {flag = 0})

conductor f of the subfield of a ray class field as defined by [a_1,a_2,a_3] (see `bnr` at the beginning of this section).

If flag = 0, returns f.

If flag = 1, returns [f, Cl_f, H], where Cl_f is the ray class group modulo f, as a finite abelian group; finally H is the subgroup of Cl_f defining the extension.

If flag = 2, returns [f, bnr(f), H], as above except Cl_f is replaced by a `bnr` structure, as output by `bnrinit`(,f,1).

The library syntax is conductor(bnr, subgroup, flag), where an omitted subgroup (trivial subgroup, i.e.ray class field) is input as `NULL`, and flag is a C long.

#### bnrconductorofchar(bnr,chi)

bnr being a big ray number field as output by `bnrinit`, and chi being a row vector representing a character as expressed on the generators of the ray class group, gives the conductor of this character as a modulus.

The library syntax is bnrconductorofchar(bnr,chi).

#### bnrdisc(a1,{a2},{a3},{flag = 0})

a1, a2, a3 defining a big ray number field L over a ground field K (see `bnr` at the beginning of this section for the meaning of a1, a2, a3), outputs a 3-component row vector [N,R_1,D], where N is the (absolute) degree of L, R_1 the number of real places of L, and D the discriminant of L/Q, including sign (if flag = 0).

If flag = 1, as above but outputs relative data. N is now the degree of L/K, R_1 is the number of real places of K unramified in L (so that the number of real places of L is equal to R_1 times the relative degree N), and D is the relative discriminant ideal of L/K.

If flag = 2, as the default case, except that if the modulus is not the exact conductor corresponding to the L, no data is computed and the result is 0.

If flag = 3, as case 2, but output relative data.

The library syntax is bnrdisc0(a1,a2,a3,flag).

#### bnrdisclist(bnf,bound,{arch})

bnf being as output by `bnfinit` (with units), computes a list of discriminants of Abelian extensions of the number field by increasing modulus norm up to bound bound. The ramified Archimedean places are given by arch; all possible values are taken if arch is omitted.

The alternative syntax `bnrdisclist`(bnf,list) is supported, where list is as output by `ideallist` or `ideallistarch` (with units), in which case arch is disregarded.

The output v is a vector of vectors, where v[i][j] is understood to be in fact V[2^{15}(i-1)+j] of a unique big vector V. (This akward scheme allows for larger vectors than could be otherwise represented.)

V[k] is itself a vector W, whose length is the number of ideals of norm k. We consider first the case where arch was specified. Each component of W corresponds to an ideal m of norm k, and gives invariants associated to the ray class field L of bnf of conductor [m, arch]. Namely, each contains a vector [m,d,r,D] with the following meaning: m is the prime ideal factorization of the modulus, d = [L:Q] is the absolute degree of L, r is the number of real places of L, and D is the factorization of its absolute discriminant. We set d = r = D = 0 if m is not the finite part of a conductor.

If arch was omitted, all t = 2^{r_1} possible values are taken and a component of W has the form [m, [[d_1,r_1,D_1],..., [d_t,r_t,D_t]]], where m is the finite part of the conductor as above, and [d_i,r_i,D_i] are the invariants of the ray class field of conductor [m,v_i], where v_i is the i-th archimedean component, ordered by inverse lexicographic order; so v_1 = [0,...,0], v_2 = [1,0...,0], etc. Again, we set d_i = r_i = D_i = 0 if [m,v_i] is not a conductor.

Finally, each prime ideal pr = [p,alpha,e,f,beta] in the prime factorization m is coded as the integer p.n^2+(f-1).n+(j-1), where n is the degree of the base field and j is such that

`pr = idealprimedec(nf,p)[j]`.

m can be decoded using `bnfdecodemodule`.

Note that to compute such data for a single field, either `bnrclassno` or `bnrdisc` is more efficient.

The library syntax is bnrdisclist0(bnf,bound,arch).

#### bnrinit(bnf,f,{flag = 0})

bnf is as output by `bnfinit`, f is a modulus, initializes data linked to the ray class group structure corresponding to this module, a so-called bnr structure. The following member functions are available on the result: `.bnf` is the underlying bnf, `.mod` the modulus, `.bid` the bid structure associated to the modulus; finally, `.clgp`, `.no`, `.cyc`, `clgp` refer to the ray class group (as a finite abelian group), its cardinality, its elementary divisors, its generators.

The last group of functions are different from the members of the underlying bnf, which refer to the class group; use `bnr.bnf.xxx` to access these, e.g.`bnr.bnf.cyc` to get the cyclic decomposition of the class group.

They are also different from the members of the underlying bid, which refer to (\O_K/f)^*; use `bnr.bid.xxx` to access these, e.g.`bnr.bid.no` to get phi(f).

If flag = 0 (default), the generators of the ray class group are not computed, which saves time. Hence `bnr.gen` would produce an error.

If flag = 1, as the default, except that generators are computed.

The library syntax is bnrinit0(bnf,f,flag).

#### bnrisconductor(a1,{a2},{a3})

a1, a2, a3 represent an extension of the base field, given by class field theory for some modulus encoded in the parameters. Outputs 1 if this modulus is the conductor, and 0 otherwise. This is slightly faster than `bnrconductor`.

The library syntax is bnrisconductor(a1,a2,a3) and the result is a `long`.

#### bnrisprincipal(bnr,x,{flag = 1})

bnr being the number field data which is output by `bnrinit`(,,1) and x being an ideal in any form, outputs the components of x on the ray class group generators in a way similar to `bnfisprincipal`. That is a 2-component vector v where v[1] is the vector of components of x on the ray class group generators, v[2] gives on the integral basis an element alpha such that x = alpha prod_ig_i^{x_i}.

If flag = 0, outputs only v_1. In that case, bnr need not contain the ray class group generators, i.e.it may be created with `bnrinit`(,,0)

The library syntax is bnrisprincipal(bnr,x,flag).

#### bnrrootnumber(bnr,chi,{flag = 0})

if chi = chi is a (not necessarily primitive) character over bnr, let L(s,chi) = sum_{id} chi(id) N(id)^{-s} be the associated Artin L-function. Returns the so-called Artin root number, i.e.the complex number W(chi) of modulus 1 such that

Lambda(1-s,chi) = W(chi) Lambda(s,\overline{chi})

where Lambda(s,chi) = A(chi)^{s/2}gamma_chi(s) L(s,chi) is the enlarged L-function associated to L.

The generators of the ray class group are needed, and you can set flag = 1 if the character is known to be primitive. Example:

    bnf = bnfinit(x^2 - 145);
     bnr = bnrinit(bnf,7,1);
     bnrrootnumber(bnr, [5])

returns the root number of the character chi of Cl_7(Q(sqrt{145})) such that chi(g) = zeta^5, where g is the generator of the ray-class field and zeta = e^{2iPi/N} where N is the order of g (N = 12 as `bnr.cyc` readily tells us).

The library syntax is bnrrootnumber(bnf,chi,flag)

#### bnrstark{(bnr,{subgroup})}

bnr being as output by `bnrinit(,,1)`, finds a relative equation for the class field corresponding to the modulus in bnr and the given congruence subgroup (as usual, omit subgroup if you want the whole ray class group).

The routine uses Stark units and needs to find a suitable auxilliary conductor, which may not exist when the class field is not cyclic over the base. In this case `bnrstark` is allowed to return a vector of polynomials defining independent relative extensions, whose compositum is the requested class field. It was decided that it was more useful to keep the extra information thus made available, hence the user has to take the compositum herself.

The main variable of bnr must not be x, and the ground field and the class field must be totally real. When the base field is Q, the vastly simpler `galoissubcyclo` is used instead. Here is an example:

    bnf = bnfinit(y^2 - 3);
     bnr = bnrinit(bnf, 5, 1);
     pol = bnrstark(bnr)

returns the ray class field of Q(sqrt{3}) modulo 5. Usually, one wants to apply to the result one of

    rnfpolredabs(bnf, pol, 16)     \\ compute a reduced relative polynomial
     rnfpolredabs(bnf, pol, 16 + 2) \\ compute a reduced absolute polynomial

The library syntax is bnrstark(bnr,subgroup), where an omitted subgroup is coded by `NULL`.

#### dirzetak(nf,b)

gives as a vector the first b coefficients of the Dedekind zeta function of the number field nf considered as a Dirichlet series.

The library syntax is dirzetak(nf,b).

#### factornf(x,t)

factorization of the univariate polynomial x over the number field defined by the (univariate) polynomial t. x may have coefficients in Q or in the number field. The algorithm reduces to factorization over Q (Trager's trick). The direct approach of `nffactor`, which uses van Hoeij's method in a relative setting, is in general faster.

The main variable of t must be of lower priority than that of x (see Section [Label: se:priority]). However if non-rational number field elements occur (as polmods or polynomials) as coefficients of x, the variable of these polmods must be the same as the main variable of t. For example

    ? factornf(x^2 + Mod(y, y^2+1), y^2+1);
     ? factornf(x^2 + y, y^2+1); \\ these two are OK
     ? factornf(x^2 + Mod(z,z^2+1), y^2+1)
       *** factornf: inconsistent data in rnf function.
     ? factornf(x^2 + z, y^2+1)
       *** factornf: incorrect variable in rnf function.

The library syntax is polfnf(x,t).

#### galoisexport(gal,{flag = 0})

gal being be a Galois field as output by `galoisinit`, export the underlying permutation group as a string suitable for (no flags or flag = 0) GAP or (flag = 1) Magma. The following example compute the index of the underlying abstract group in the GAP library:

    ? G = galoisinit(x^6+108);
     ? s = galoisexport(G)
     %2 = "Group((1, 2, 3)(4, 5, 6), (1, 4)(2, 6)(3, 5))"
     ? extern("echo \"IdGroup("s");\" | gap -q")
     %3 = [6, 1]
     ? galoisidentify(G)
     %4 = [6, 1]

This command also accepts subgroups returned by `galoissubgroups`.

The library syntax is galoisexport(gal,flag).

#### galoisfixedfield(gal,perm,{flag = 0},{v = y}))

gal being be a Galois field as output by `galoisinit` and perm an element of gal.group or a vector of such elements, computes the fixed field of gal by the automorphism defined by the permutations perm of the roots gal.roots. P is guaranteed to be squarefree modulo gal.p.

If no flags or flag = 0, output format is the same as for `nfsubfield`, returning [P,x] such that P is a polynomial defining the fixed field, and x is a root of P expressed as a polmod in gal.pol.

If flag = 1 return only the polynomial P.

If flag = 2 return [P,x,F] where P and x are as above and F is the factorization of gal.pol over the field defined by P, where variable v (y by default) stands for a root of P. The priority of v must be less than the priority of the variable of gal.pol (see Section [Label: se:priority]). Example:

    ? G = galoisinit(x^4+1);
     ? galoisfixedfield(G,G.group[2],2)
     %2 = [x^2 + 2, Mod(x^3 + x, x^4 + 1), [x^2 - y*x - 1, x^2 + y*x - 1]]

computes the factorization x^4+1 = (x^2-sqrt{-2}x-1)(x^2+sqrt{-2}x-1)

The library syntax is galoisfixedfield(gal,perm,flag,v), where v is a variable number, an omitted v being coded by -1.

#### galoisidentify(gal)

gal being be a Galois field as output by `galoisinit`, output the isomorphism class of the underlying abstract group as a two-components vector [o,i], where o is the group order, and i is the group index in the GAP4 Small Group library, by Hans Ulrich Besche, Bettina Eick and Eamonn O'Brien.

This command also accepts subgroups returned by `galoissubgroups`.

The current implementation is limited to degree less or equal to 127. Some larger "easy" orders are also supported.

The output is similar to the output of the function `IdGroup` in GAP4. Note that GAP4 `IdGroup` handles all groups of order less than 2000 except 1024, so you can use `galoisexport` and GAP4 to identify large Galois groups.

The library syntax is galoisidentify(gal).

#### galoisinit(pol,{den})

computes the Galois group and all necessary information for computing the fixed fields of the Galois extension K/Q where K is the number field defined by pol (monic irreducible polynomial in Z[X] or a number field as output by `nfinit`). The extension K/Q must be Galois with Galois group "weakly" super-solvable (see `nfgaloisconj`)

This is a prerequisite for most of the `galois`xxx routines. For instance:

      P = x^6 + 108;
       G = galoisinit(P);
       L = galoissubgroups(G);
       vector(#L, i, galoisisabelian(L[i],1))
       vector(#L, i, galoisidentify(L[i]))

The output is an 8-component vector gal.

gal[1] contains the polynomial pol (`gal.pol`).

gal[2] is a three-components vector [p,e,q] where p is a prime number (`gal.p`) such that pol totally split modulo p , e is an integer and q = p^e (`gal.mod`) is the modulus of the roots in `gal.roots`.

gal[3] is a vector L containing the p-adic roots of pol as integers implicitly modulo `gal.mod`. (`gal.roots`).

gal[4] is the inverse of the Van der Monde matrix of the p-adic roots of pol, multiplied by gal[5].

gal[5] is a multiple of the least common denominator of the automorphisms expressed as polynomial in a root of pol.

gal[6] is the Galois group G expressed as a vector of permutations of L (`gal.group`).

gal[7] is a generating subset S = [s_1,...,s_g] of G expressed as a vector of permutations of L (`gal.gen`).

gal[8] contains the relative orders [o_1,...,o_g] of the generators of S (`gal.orders`).

Let H be the maximal normal supersolvable subgroup of G, we have the following properties:

* if G/H ~ A_4 then [o_1,...,o_g] ends by [2,2,3].

* if G/H ~ S_4 then [o_1,...,o_g] ends by [2,2,3,2].

* else G is super-solvable.

* for 1 `<=` i `<=` g the subgroup of G generated by [s_1,...,s_g] is normal, with the exception of i = g-2 in the second case and of i = g-3 in the third.

* the relative order o_i of s_i is its order in the quotient group G/`<`s_1,...,s_{i-1}`>`, with the same exceptions.

* for any x belongs to G there exists a unique family [e_1,...,e_g] such that (no exceptions):

-- for 1 `<=` i `<=` g we have 0 `<=` e_i < o_i

-- x = g_1^{e_1}g_2^{e_2}...g_n^{e_n}

If present den must be a suitable value for gal[5].

The library syntax is galoisinit(gal,den).

#### galoisisabelian(gal,{fl = 0})

gal being as output by `galoisinit`, return 0 if gal is not an abelian group, and the HNF matrix of gal over `gal.gen` if fl = 0, 1 if fl = 1.

This command also accepts subgroups returned by `galoissubgroups`.

The library syntax is galoisisabelian(gal,fl) where fl is a C long integer.

#### galoispermtopol(gal,perm)

gal being a Galois field as output by `galoisinit` and perm a element of gal.group, return the polynomial defining the Galois automorphism, as output by `nfgaloisconj`, associated with the permutation perm of the roots gal.roots. perm can also be a vector or matrix, in this case, `galoispermtopol` is applied to all components recursively.

Note that

    G = galoisinit(pol);
     galoispermtopol(G, G[6])~

is equivalent to `nfgaloisconj(pol)`, if degree of pol is greater or equal to 2.

The library syntax is galoispermtopol(gal,perm).

#### galoissubcyclo(N,H,{fl = 0},{v})

computes the subextension of Q(zeta_n) fixed by the subgroup H \subset (Z/nZ)^*. By the Kronecker-Weber theorem, all abelian number fields can be generated in this way (uniquely if n is taken to be minimal).

The pair (n, H) is deduced from the parameters (N, H) as follows

* N an integer: then n = N; H is a generator, i.e. an integer or an integer modulo n; or a vector of generators.

* N the output of `znstar(n)`. H as in the first case above, or a matrix, taken to be a HNF left divisor of the SNF for (Z/nZ)^* (of type `N.cyc`), giving the generators of H in terms of `N.gen`.

* N the output of `bnrinit(bnfinit(y), m, 1)` where m is a module. H as in the first case, or a matrix taken to be a HNF left divisor of the SNF for the ray class group modulo m (of type `N.cyc`), giving the generators of H in terms of `N.gen`.

In this last case, beware that H is understood relatively to N; in particular, if the infinite place does not divide the module, e.g if m is an integer, then it is not a subgroup of (Z/nZ)^*, but of its quotient by {± 1}.

If fl = 0, compute a polynomial (in the variable v) defining the the subfield of Q(zeta_n) fixed by the subgroup H of (Z/nZ)^*.

If fl = 1, compute only the conductor of the abelian extension, as a module.

If fl = 2, output [pol, N], where pol is the polynomial as output when fl = 0 and N the conductor as output when fl = 1.

The following function can be used to compute all subfields of Q(zeta_n) (of exact degree `d`, if `d` is set):

    subcyclo(n, d = -1)=
     {
       local(bnr,L,IndexBound);
       IndexBound = if (d < 0, n, [d]);
       bnr = bnrinit(bnfinit(y), [n,[1]], 1);
       L = subgrouplist(bnr, IndexBound, 1);
       vector(#L,i, galoissubcyclo(bnr,L[i]));
     }

Setting `L = subgrouplist(bnr, IndexBound)` would produce subfields of exact conductor n oo .

The library syntax is galoissubcyclo(N,H,fl,v) where fl is a C long integer, and v a variable number.

#### galoissubfields(G,{fl = 0},{v})

Output all the subfields of the Galois group G, as a vector. This works by applying `galoisfixedfield` to all subgroups. The meaning of the flag fl is the same as for `galoisfixedfield`.

The library syntax is galoissubfields(G,fl,v), where fl is a long and v a variable number.

#### galoissubgroups(gal)

Output all the subgroups of the Galois group `gal`. A subgroup is a vector [gen, orders], with the same meaning as for gal.gen and gal.orders. Hence gen is a vector of permutations generating the subgroup, and orders is the relatives orders of the generators. The cardinal of a subgroup is the product of the relative orders. Such subgroup can be used instead of a Galois group in the following command: `galoisisabelian`, `galoissubgroups`, `galoisexport` and `galoisidentify`.

To get the subfield fixed by a subgroup sub of gal, use

    galoisfixedfield(gal,sub[1])

The library syntax is galoissubgroups(gal).

#### idealadd(nf,x,y)

sum of the two ideals x and y in the number field nf. When x and y are given by Z-bases, this does not depend on nf and can be used to compute the sum of any two Z-modules. The result is given in HNF.

The library syntax is idealadd(nf,x,y).

#### idealaddtoone(nf,x,{y})

x and y being two co-prime integral ideals (given in any form), this gives a two-component row vector [a,b] such that a belongs to x, b belongs to y and a+b = 1.

The alternative syntax `idealaddtoone`(nf,v), is supported, where v is a k-component vector of ideals (given in any form) which sum to Z_K. This outputs a k-component vector e such that e[i] belongs to x[i] for 1 `<=` i `<=` k and sum_{1 `<=` i `<=` k}e[i] = 1.

The library syntax is idealaddtoone0(nf,x,y), where an omitted y is coded as `NULL`.

#### idealappr(nf,x,{flag = 0})

if x is a fractional ideal (given in any form), gives an element alpha in nf such that for all prime ideals wp such that the valuation of x at wp is non-zero, we have v_{wp}(alpha) = v_{wp}(x), and. v_{wp}(alpha) `>=` 0 for all other {wp}.

If flag is non-zero, x must be given as a prime ideal factorization, as output by `idealfactor`, but possibly with zero or negative exponents. This yields an element alpha such that for all prime ideals wp occurring in x, v_{wp}(alpha) is equal to the exponent of wp in x, and for all other prime ideals, v_{wp}(alpha) `>=` 0. This generalizes `idealappr`(nf,x,0) since zero exponents are allowed. Note that the algorithm used is slightly different, so that `idealappr(nf,idealfactor(nf,x))` may not be the same as `idealappr(nf,x,1)`.

The library syntax is idealappr0(nf,x,flag).

#### idealchinese(nf,x,y)

x being a prime ideal factorization (i.e.a 2 by 2 matrix whose first column contain prime ideals, and the second column integral exponents), y a vector of elements in nf indexed by the ideals in x, computes an element b such that

v_wp(b - y_wp) `>=` v_wp(x) for all prime ideals in x and v_wp(b) `>=` 0 for all other wp.

The library syntax is idealchinese(nf,x,y).

#### idealcoprime(nf,x,y)

given two integral ideals x and y in the number field nf, finds a beta in the field, expressed on the integral basis nf[7], such that beta.x is an integral ideal coprime to y.

The library syntax is idealcoprime(nf,x,y).

#### idealdiv(nf,x,y,{flag = 0})

quotient x.y^{-1} of the two ideals x and y in the number field nf. The result is given in HNF.

If flag is non-zero, the quotient x.y^{-1} is assumed to be an integral ideal. This can be much faster when the norm of the quotient is small even though the norms of x and y are large.

The library syntax is idealdiv0(nf,x,y,flag). Also available are `idealdiv(nf,x,y)` (flag = 0) and `idealdivexact(nf,x,y)` (flag = 1).

#### idealfactor(nf,x)

factors into prime ideal powers the ideal x in the number field nf. The output format is similar to the `factor` function, and the prime ideals are represented in the form output by the `idealprimedec` function, i.e.as 5-element vectors.

The library syntax is idealfactor(nf,x).

#### idealhnf(nf,a,{b})

gives the Hermite normal form matrix of the ideal a. The ideal can be given in any form whatsoever (typically by an algebraic number if it is principal, by a Z_K-system of generators, as a prime ideal as given by `idealprimedec`, or by a Z-basis).

If b is not omitted, assume the ideal given was aZ_K+bZ_K, where a and b are elements of K given either as vectors on the integral basis nf[7] or as algebraic numbers.

The library syntax is idealhnf0(nf,a,b) where an omitted b is coded as `NULL`. Also available is `idealhermite(nf,a)` (b omitted).

#### idealintersect(nf,A,B)

intersection of the two ideals A and B in the number field nf. The result is given in HNF.

        ? nf = nfinit(x^2+1);
         ? idealintersect(nf, 2, x+1)
         %2 =
         [2 0]

         [0 2]

This function does not apply to general Z-modules, e.g.orders, since its arguments are replaced by the ideals they generate. The following script intersects Z-modules A and B given by matrices of compatible dimensions with integer coefficients:

        ZM_intersect(A,B) =
         { local(Ker);
             Ker = matkerint(concat(A,B));
             Ker = vecextract(Ker, Str(1, "..", #A), "..");
             mathnf(Ker * A)
         }

The library syntax is idealintersect(nf,A,B).

#### idealinv(nf,x)

inverse of the ideal x in the number field nf. The result is the Hermite normal form of the inverse of the ideal, together with the opposite of the Archimedean information if it is given.

The library syntax is idealinv(nf,x).

#### ideallist(nf,bound,{flag = 4})

computes the list of all ideals of norm less or equal to bound in the number field nf. The result is a row vector with exactly bound components. Each component is itself a row vector containing the information about ideals of a given norm, in no specific order, depending on the value of flag:

The possible values of flag are:

0: give the bid associated to the ideals, without generators.

1: as 0, but include the generators in the bid.

2: in this case, nf must be a bnf with units. Each component is of the form [bid,U], where bid is as case 0 and U is a vector of discrete logarithms of the units. More precisely, it gives the `ideallog`s with respect to bid of `bnf.tufu`. This structure is technical, and only meant to be used in conjunction with `bnrclassnolist` or `bnrdisclist`.

3: as 2, but include the generators in the bid.

4: give only the HNF of the ideal.

    ? nf = nfinit(x^2+1);
     ? L = ideallist(nf, 100);
     ? L[1]
     %3 = [[1, 0; 0, 1]]  \\ A single ideal of norm 1
     ? #L[65]
     %4 = 4               \\ There are 4 ideals of norm 4 in Z[i]

If one wants more information, one could do instead:

    ? nf = nfinit(x^2+1);
     ? L = ideallist(nf, 100, 0);
     ? l = L[25]; vector(#l, i, l[i].clgp)
     %3 = [[20, [20]], [16, [4, 4]], [20, [20]]]
     ? l[1].mod
     %4 = [[25, 18; 0, 1], []]
     ? l[2].mod
     %5 = [[5, 0; 0, 5], []]
     ? l[3].mod
     %6 = [[25, 7; 0, 1], []]

where we ask for the structures of the (Z[i]/I)^* for all three ideals of norm 25. In fact, for all moduli with finite part of norm 25 and trivial archimedean part, as the last 3 commands show. See `ideallistarch` to treat general moduli.

The library syntax is ideallist0(nf,bound,flag), where bound must be a C long integer. Also available is `ideallist(nf,bound)`, corresponding to the case flag = 4.

#### ideallistarch(nf,list,arch)

list is a vector of vectors of bid's, as output by `ideallist` with flag 0 to 3. Return a vector of vectors with the same number of components as the original list. The leaves give information about moduli whose finite part is as in original list, in the same order, and archimedean part is now arch (it was originally trivial). The information contained is of the same kind as was present in the input; see `ideallist`, in particular the meaning of flag.

    ? bnf = bnfinit(x^2-2);
     ? bnf.sign
     %2 = [2, 0]                         \\ two places at infinity
     ? L = ideallist(bnf, 100, 0);
     ? l = L[98]; vector(#l, i, l[i].clgp)
     %4 = [[42, [42]], [36, [6, 6]], [42, [42]]]
     ? La = ideallistarch(bnf, L, [1,1]); \\ add them to the modulus
     ? l = La[98]; vector(#l, i, l[i].clgp)
     %6 = [[168, [42, 2, 2]], [144, [6, 6, 2, 2]], [168, [42, 2, 2]]]

Of course, the results above are obvious: adding t places at infinity will add t copies of Z/2Z to the ray class group. The following application is more typical:

    ? L = ideallist(bnf, 100, 2);        \\ units are required now
     ? La = ideallistarch(bnf, L, [1,1]);
     ? H = bnrclassnolist(bnf, La);
     ? H[98];
     %6 = [2, 12, 2]

The library syntax is ideallistarch(nf,list,arch).

#### ideallog(nf,x,bid)

nf is a number field, bid a "big ideal" as output by `idealstar` and x a non-necessarily integral element of nf which must have valuation equal to 0 at all prime ideals dividing I = bid[1]. This function computes the "discrete logarithm" of x on the generators given in bid[2]. In other words, if g_i are these generators, of orders d_i respectively, the result is a column vector of integers (x_i) such that 0 `<=` x_i < d_i and x = prod_ig_i^{x_i} (mod ^*I) . Note that when I is a module, this implies also sign conditions on the embeddings.

The library syntax is zideallog(nf,x,bid).

#### idealmin(nf,x,{vdir})

computes a minimum of the ideal x in the direction vdir in the number field nf.

The library syntax is minideal(nf,x,vdir,prec), where an omitted vdir is coded as `NULL`.

#### idealmul(nf,x,y,{flag = 0})

ideal multiplication of the ideals x and y in the number field nf. The result is a generating set for the ideal product with at most n elements, and is in Hermite normal form if either x or y is in HNF or is a prime ideal as output by `idealprimedec`, and this is given together with the sum of the Archimedean information in x and y if both are given.

If flag is non-zero, reduce the result using `idealred`.

The library syntax is idealmul(nf,x,y) (flag = 0) or `idealmulred(nf,x,y,prec)` (flag != 0), where as usual, prec is a C long integer representing the precision.

#### idealnorm(nf,x)

computes the norm of the idealx in the number fieldnf.

The library syntax is idealnorm(nf, x).

#### idealpow(nf,x,k,{flag = 0})

computes the k-th power of the ideal x in the number field nf. k can be positive, negative or zero. The result is NOT reduced, it is really the k-th ideal power, and is given in HNF.

If flag is non-zero, reduce the result using `idealred`. Note however that this is NOT the same as as `idealpow`(nf,x,k) followed by reduction, since the reduction is performed throughout the powering process.

The library syntax corresponding to flag = 0 is `idealpow(nf,x,k)`. If k is a `long`, you can use `idealpows(nf,x,k)`. Corresponding to flag = 1 is `idealpowred(nf,vp,k,prec)`, where prec is a `long`.

#### idealprimedec(nf,p)

computes the prime ideal decomposition of the prime number p in the number field nf. p must be a (positive) prime number. Note that the fact that p is prime is not checked, so if a non-prime p is given the result is undefined.

The result is a vector of pr structures, each representing one of the prime ideals above p in the number field nf. The representation P = [p,a,e,f,b] of a prime ideal means the following. The prime ideal is equal to pZ_K+alpha Z_K where Z_K is the ring of integers of the field and alpha = sum_i a_iomega_i where the omega_i form the integral basis `nf.zk`, e is the ramification index, f is the residual index, and b represents a beta belongs to Z_K such that P^{-1} = Z_K+beta/pZ_K which will be useful for computing valuations, but which the user can ignore. The number alpha is guaranteed to have a valuation equal to 1 at the prime ideal (this is automatic if e > 1).

The components of `P` should be accessed by member functions: `P.p`, `P.e`, `P.f`, and `P.gen` (returns the vector [p,a]).

The library syntax is primedec(nf,p).

#### idealprincipal(nf,x)

creates the principal ideal generated by the algebraic number x (which must be of type integer, rational or polmod) in the number field nf. The result is a one-column matrix.

The library syntax is principalideal(nf,x).

#### idealred(nf,I,{vdir = 0})

LLL reduction of the ideal I in the number field nf, along the direction vdir. If vdir is present, it must be an r1+r2-component vector (r1 and r2 number of real and complex places of nf as usual).

This function finds a "small" a in I (it is an LLL pseudo-minimum along direction vdir). The result is the Hermite normal form of the LLL-reduced ideal r I/a, where r is a rational number such that the resulting ideal is integral and primitive. This is often, but not always, a reduced ideal in the sense of Buchmann. If I is an idele, the logarithmic embeddings of a are subtracted to the Archimedean part.

More often than not, a principal ideal will yield the identity matrix. This is a quick and dirty way to check if ideals are principal without computing a full `bnf` structure, but it's not a necessary condition; hence, a non-trivial result doesn't prove the ideal is non-trivial in the class group.

Note that this is not the same as the LLL reduction of the lattice I since ideal operations are involved.

The library syntax is ideallllred(nf,x,vdir,prec), where an omitted vdir is coded as `NULL`.

#### idealstar(nf,I,{flag = 1})

outputs a bid structure, necessary for computing in the finite abelian group G = (Z_K/I)^*. Here, nf is a number field and I is a modulus: either an ideal in any form, or a row vector whose first component is an ideal and whose second component is a row vector of r_1 0 or 1.

This bid is used in `ideallog` to compute discrete logarithms. It also contains useful information which can be conveniently retrieved as `bid.mod` (the modulus), `bid.clgp` (G as a finite abelian group), `bid.no` (the cardinality of G), `bid.cyc` (elementary divisors) and `bid.gen` (generators).

If flag = 1 (default), the result is a bid structure without generators.

If flag = 2, as flag = 1, but including generators, which wastes some time.

If flag = 0, deprecated. Only outputs (Z_K/I)^* as an abelian group, i.e as a 3-component vector [h,d,g]: h is the order, d is the vector of SNF cyclic components and g the corresponding generators. This flag is deprecated: it is in fact slightly faster to compute a true bid structure, which contains much more information.

The library syntax is idealstar0(nf,I,flag).

#### idealtwoelt(nf,x,{a})

computes a two-element representation of the ideal x in the number field nf, using a straightforward (exponential time) search. x can be an ideal in any form, (including perhaps an Archimedean part, which is ignored) and the result is a row vector [a,alpha] with two components such that x = aZ_K+alpha Z_K and a belongs to Z, where a is the one passed as argument if any. If x is given by at least two generators, a is chosen to be the positive generator of xcapZ.

Note that when an explicit a is given, we use an asymptotically faster method, however in practice it is usually slower.

The library syntax is ideal_two_elt0(nf,x,a), where an omitted a is entered as `NULL`.

#### idealval(nf,x,vp)

gives the valuation of the ideal x at the prime ideal vp in the number field nf, where vp must be a 5-component vector as given by `idealprimedec`.

The library syntax is idealval(nf,x,vp), and the result is a `long` integer.

#### ideleprincipal(nf,x)

creates the principal idele generated by the algebraic number x (which must be of type integer, rational or polmod) in the number field nf. The result is a two-component vector, the first being a one-column matrix representing the corresponding principal ideal, and the second being the vector with r_1+r_2 components giving the complex logarithmic embedding of x.

The library syntax is principalidele(nf,x).

#### matalgtobasis(nf,x)

nf being a number field in `nfinit` format, and x a matrix whose coefficients are expressed as polmods in nf, transforms this matrix into a matrix whose coefficients are expressed on the integral basis of nf. This is the same as applying `nfalgtobasis` to each entry, but it would be dangerous to use the same name.

The library syntax is matalgtobasis(nf,x).

#### matbasistoalg(nf,x)

nf being a number field in `nfinit` format, and x a matrix whose coefficients are expressed as column vectors on the integral basis of nf, transforms this matrix into a matrix whose coefficients are algebraic numbers expressed as polmods. This is the same as applying `nfbasistoalg` to each entry, but it would be dangerous to use the same name.

The library syntax is matbasistoalg(nf,x).

#### modreverse(a)

a being a polmod A(X) modulo T(X), finds the "reverse polmod" B(X) modulo Q(X), where Q is the minimal polynomial of a, which must be equal to the degree of T, and such that if theta is a root of T then theta = B(alpha) for a certain root alpha of Q.

This is very useful when one changes the generating element in algebraic extensions.

The library syntax is polmodrecip(x).

#### newtonpoly(x,p)

gives the vector of the slopes of the Newton polygon of the polynomial x with respect to the prime number p. The n components of the vector are in decreasing order, where n is equal to the degree of x. Vertical slopes occur iff the constant coefficient of x is zero and are denoted by `VERYBIGINT`, the biggest single precision integer representable on the machine (2^{31}-1 (resp.2^{63}-1) on 32-bit (resp.64-bit) machines), see Section [Label: se:valuation].

The library syntax is newtonpoly(x,p).

#### nfalgtobasis(nf,x)

this is the inverse function of `nfbasistoalg`. Given an object x whose entries are expressed as algebraic numbers in the number field nf, transforms it so that the entries are expressed as a column vector on the integral basis `nf.zk`.

The library syntax is algtobasis(nf,x).

#### nfbasis(x,{flag = 0},{fa})

integral basis of the number field defined by the irreducible, preferably monic, polynomial x, using a modified version of the round 4 algorithm by default, due to David Ford, Sebastian Pauli and Xavier Roblot. The binary digits of flag have the following meaning:

1: assume that no square of a prime greater than the default `primelimit` divides the discriminant of x, i.e.that the index of x has only small prime divisors.

2: use round 2 algorithm. For small degrees and coefficient size, this is sometimes a little faster. (This program is the translation into C of a program written by David Ford in Algeb.)

Thus for instance, if flag = 3, this uses the round 2 algorithm and outputs an order which will be maximal at all the small primes.

If fa is present, we assume (without checking!) that it is the two-column matrix of the factorization of the discriminant of the polynomial x. Note that it does not have to be a complete factorization. This is especially useful if only a local integral basis for some small set of places is desired: only factors with exponents greater or equal to 2 will be considered.

The library syntax is nfbasis0(x,flag,fa). An extended version is `nfbasis(x,&d,flag,fa)`, where d receives the discriminant of the number field (not of the polynomial x), and an omitted fa is input as `NULL`. Also available are `base(x,&d)` (flag = 0), `base2(x,&d)` (flag = 2) and `factoredbase(x,fa,&d)`.

#### nfbasistoalg(nf,x)

this is the inverse function of `nfalgtobasis`. Given an object x whose entries are expressed on the integral basis `nf.zk`, transforms it into an object whose entries are algebraic numbers (i.e.polmods).

The library syntax is basistoalg(nf,x).

#### nfdetint(nf,x)

given a pseudo-matrix x, computes a non-zero ideal contained in (i.e.multiple of) the determinant of x. This is particularly useful in conjunction with `nfhnfmod`.

The library syntax is nfdetint(nf,x).

#### nfdisc(x,{flag = 0},{fa})

field discriminant of the number field defined by the integral, preferably monic, irreducible polynomial x. flag and fa are exactly as in `nfbasis`. That is, fa provides the matrix of a partial factorization of the discriminant of x, and binary digits of flag are as follows:

1: assume that no square of a prime greater than `primelimit` divides the discriminant.

2: use the round 2 algorithm, instead of the default round 4. This should be slower except maybe for polynomials of small degree and coefficients.

The library syntax is nfdiscf0(x,flag,fa) where an omitted fa is input as `NULL`. You can also use `discf(x)` (flag = 0).

#### nfeltdiv(nf,x,y)

given two elements x and y in nf, computes their quotient x/y in the number field nf.

The library syntax is element_div(nf,x,y).

#### nfeltdiveuc(nf,x,y)

given two elements x and y in nf, computes an algebraic integer q in the number field nf such that the components of x-qy are reasonably small. In fact, this is functionally identical to `round(nfeltdiv(nf,x,y))`.

The library syntax is nfdiveuc(nf,x,y).

#### nfeltdivmodpr(nf,x,y,pr)

given two elements x and y in nf and pr a prime ideal in `modpr` format (see `nfmodprinit`), computes their quotient x / y modulo the prime ideal pr.

The library syntax is element_divmodpr(nf,x,y,pr).

#### nfeltdivrem(nf,x,y)

given two elements x and y in nf, gives a two-element row vector [q,r] such that x = qy+r, q is an algebraic integer in nf, and the components of r are reasonably small.

The library syntax is nfdivrem(nf,x,y).

#### nfeltmod(nf,x,y)

given two elements x and y in nf, computes an element r of nf of the form r = x-qy with q and algebraic integer, and such that r is small. This is functionally identical to `x - nfeltmul(nf,round(nfeltdiv(nf,x,y)),y)`.

The library syntax is nfmod(nf,x,y).

#### nfeltmul(nf,x,y)

given two elements x and y in nf, computes their product x*y in the number field nf.

The library syntax is element_mul(nf,x,y).

#### nfeltmulmodpr(nf,x,y,pr)

given two elements x and y in nf and pr a prime ideal in `modpr` format (see `nfmodprinit`), computes their product x*y modulo the prime ideal pr.

The library syntax is element_mulmodpr(nf,x,y,pr).

#### nfeltpow(nf,x,k)

given an element x in nf, and a positive or negative integer k, computes x^k in the number field nf.

The library syntax is element_pow(nf,x,k).

#### nfeltpowmodpr(nf,x,k,pr)

given an element x in nf, an integer k and a prime ideal pr in `modpr` format (see `nfmodprinit`), computes x^k modulo the prime ideal pr.

The library syntax is element_powmodpr(nf,x,k,pr).

#### nfeltreduce(nf,x,ideal)

given an ideal in Hermite normal form and an element x of the number field nf, finds an element r in nf such that x-r belongs to the ideal and r is small.

The library syntax is element_reduce(nf,x,ideal).

#### nfeltreducemodpr(nf,x,pr)

given an element x of the number field nf and a prime ideal pr in `modpr` format compute a canonical representative for the class of x modulo pr.

The library syntax is nfreducemodpr(nf,x,pr).

#### nfeltval(nf,x,pr)

given an element x in nf and a prime ideal pr in the format output by `idealprimedec`, computes their the valuation at pr of the element x. The same result could be obtained using `idealval(nf,x,pr)` (since x would then be converted to a principal ideal), but it would be less efficient.

The library syntax is element_val(nf,x,pr), and the result is a `long`.

#### nffactor(nf,x)

factorization of the univariate polynomial x over the number field nf given by `nfinit`. x has coefficients in nf (i.e.either scalar, polmod, polynomial or column vector). The main variable of nf must be of lower priority than that of x (see Section [Label: se:priority]). However if the polynomial defining the number field occurs explicitly in the coefficients of x (as modulus of a `t_POLMOD`), its main variable must be the same as the main variable of x. For example,

    ? nf = nfinit(y^2 + 1);
     ? nffactor(nf, x^2 + y); \\ OK
     ? nffactor(nf, x^2 + Mod(y, y^2+1)); \\  OK
     ? nffactor(nf, x^2 + Mod(z, z^2+1)); \\  WRONG

The library syntax is nffactor(nf,x).

#### nffactormod(nf,x,pr)

factorization of the univariate polynomial x modulo the prime ideal pr in the number field nf. x can have coefficients in the number field (scalar, polmod, polynomial, column vector) or modulo the prime ideal (intmod modulo the rational prime under pr, polmod or polynomial with intmod coefficients, column vector of intmod). The prime ideal pr must be in the format output by `idealprimedec`. The main variable of nf must be of lower priority than that of x (see Section [Label: se:priority]). However if the coefficients of the number field occur explicitly (as polmods) as coefficients of x, the variable of these polmods must be the same as the main variable of t (see `nffactor`).

The library syntax is nffactormod(nf,x,pr).

#### nfgaloisapply(nf,aut,x)

nf being a number field as output by `nfinit`, and aut being a Galois automorphism of nf expressed either as a polynomial or a polmod (such automorphisms being found using for example one of the variants of `nfgaloisconj`), computes the action of the automorphism aut on the object x in the number field. x can be an element (scalar, polmod, polynomial or column vector) of the number field, an ideal (either given by Z_K-generators or by a Z-basis), a prime ideal (given as a 5-element row vector) or an idele (given as a 2-element row vector). Because of possible confusion with elements and ideals, other vector or matrix arguments are forbidden.

The library syntax is galoisapply(nf,aut,x).

#### nfgaloisconj(nf,{flag = 0},{d})

nf being a number field as output by `nfinit`, computes the conjugates of a root r of the non-constant polynomial x = nf[1] expressed as polynomials in r. This can be used even if the number field nf is not Galois since some conjugates may lie in the field.

nf can simply be a polynomial if flag != 1.

If no flags or flag = 0, if nf is a number field use a combination of flag 4 and 1 and the result is always complete, else use a combination of flag 4 and 2 and the result is subject to the restriction of flag = 2, but a warning is issued when it is not proven complete.

If flag = 1, use `nfroots` (require a number field).

If flag = 2, use complex approximations to the roots and an integral LLL. The result is not guaranteed to be complete: some conjugates may be missing (no warning issued), especially so if the corresponding polynomial has a huge index. In that case, increasing the default precision may help.

If flag = 4, use Allombert's algorithm and permutation testing. If the field is Galois with "weakly" super solvable Galois group, return the complete list of automorphisms, else only the identity element. If present, d is assumed to be a multiple of the least common denominator of the conjugates expressed as polynomial in a root of pol.

A group G is "weakly" super solvable (WKSS) if it contains a super solvable normal subgroup H such that G = H , or G/H ~ A_4 , or G/H ~ S_4. Abelian and nilpotent groups are WKSS. In practice, almost all groups of small order are WKSS, the exceptions having order 36(1 exception), 48(2), 56(1), 60(1), 72(5), 75(1), 80(1), 96(10) and `>=` 108.

Hence flag = 4 permits to quickly check whether a polynomial of order strictly less than 36 is Galois or not. This method is much faster than `nfroots` and can be applied to polynomials of degree larger than 50.

This routine can only compute Q-automorphisms, but it may be used to get K-automorphism for any base field K as follows:

      rnfgaloisconj(nfK, R) = \\ K-automorphisms of L = K[X] / (R)
       { local(polabs, N, H);
         R *= Mod(1, nfK.pol);             \\ convert coeffs to polmod elts of K
         polabs = rnfequation(nfK, R);
         N = nfgaloisconj(polabs) % R;     \\ Q-automorphisms of L
         H = [];
         for(i=1, #N,                      \\ select the ones that fix K
           if (subst(R, variable(R), Mod(N[i],R)) == 0,
             H = concat(H,N[i])
           )
         ); H
       }
       K  = nfinit(y^2 + 7);
       polL = x^4 - y*x^3 - 3*x^2 + y*x + 1;
       rnfgaloisconj(K, polL)             \\ K-automorphisms of L

The library syntax is galoisconj0(nf,flag,d,prec). Also available are `galoisconj(nf)` for flag = 0, `galoisconj2(nf,n,prec)` for flag = 2 where n is a bound on the number of conjugates, and `galoisconj4(nf,d)` corresponding to flag = 4.

#### nfhilbert(nf,a,b,{pr})

if pr is omitted, compute the global Hilbert symbol (a,b) in nf, that is 1 if x^2 - a y^2 - b z^2 has a non trivial solution (x,y,z) in nf, and -1 otherwise. Otherwise compute the local symbol modulo the prime ideal pr (as output by `idealprimedec`).

The library syntax is nfhilbert(nf,a,b,pr), where an omitted pr is coded as `NULL`.

#### nfhnf(nf,x)

given a pseudo-matrix (A,I), finds a pseudo-basis in Hermite normal form of the module it generates.

The library syntax is nfhermite(nf,x).

#### nfhnfmod(nf,x,detx)

given a pseudo-matrix (A,I) and an ideal detx which is contained in (read integral multiple of) the determinant of (A,I), finds a pseudo-basis in Hermite normal form of the module generated by (A,I). This avoids coefficient explosion. detx can be computed using the function `nfdetint`.

The library syntax is nfhermitemod(nf,x,detx).

#### nfinit(pol,{flag = 0})

pol being a non-constant, preferably monic, irreducible polynomial in Z[X], initializes a number field structure (`nf`) associated to the field K defined by pol. As such, it's a technical object passed as the first argument to most `nf` xxx functions, but it contains some information which may be directly useful. Access to this information via member functions is preferred since the specific data organization specified below may change in the future. Currently, `nf` is a row vector with 9 components:

nf[1] contains the polynomial pol (`nf.pol`).

nf[2] contains [r1,r2] (`nf.sign`, `nf.r1`, `nf.r2`), the number of real and complex places of K.

nf[3] contains the discriminant d(K) (`nf.disc`) of K.

nf[4] contains the index of nf[1] (`nf.index`), i.e.[Z_K : Z[theta]], where theta is any root of nf[1].

nf[5] is a vector containing 7 matrices M, G, T2, T, MD, TI, MDI useful for certain computations in the number field K.

* M is the (r1+r2) x n matrix whose columns represent the numerical values of the conjugates of the elements of the integral basis.

* G is such that T2 = ^t G G, where T2 is the quadratic form T_2(x) = sum |sigma(x)|^2, sigma running over the embeddings of K into C.

* The T2 component is deprecated and currently unused.

* T is the n x n matrix whose coefficients are {Tr}(omega_iomega_j) where the omega_i are the elements of the integral basis. Note also that det(T) is equal to the discriminant of the field K.

* The columns of MD (`nf.diff`) express a Z-basis of the different of K on the integral basis.

* TI is equal to d(K)T^{-1}, which has integral coefficients. Note that, understood as as ideal, the matrix T^{-1} generates the codifferent ideal.

* Finally, MDI is a two-element representation (for faster ideal product) of d(K) times the codifferent ideal (`nf.disc*nf.codiff`, which is an integral ideal). MDI is only used in `idealinv`.

nf[6] is the vector containing the r1+r2 roots (`nf.roots`) of nf[1] corresponding to the r1+r2 embeddings of the number field into C (the first r1 components are real, the next r2 have positive imaginary part).

nf[7] is an integral basis for Z_K (`nf.zk`) expressed on the powers oftheta. Its first element is guaranteed to be 1. This basis is LLL-reduced with respect to T_2 (strictly speaking, it is a permutation of such a basis, due to the condition that the first element be 1).

nf[8] is the n x n integral matrix expressing the power basis in terms of the integral basis, and finally

nf[9] is the n x n^2 matrix giving the multiplication table of the integral basis.

If a non monic polynomial is input, `nfinit` will transform it into a monic one, then reduce it (see flag = 3). It is allowed, though not very useful given the existence of `nfnewprec`, to input a `nf` or a `bnf` instead of a polynomial.

      ? nf = nfinit(x^3 - 12); \\ initialize number field Q[X] / (X^3 - 12)
       ? nf.pol   \\ defining polynomial
       %2 = x^3 - 12
       ? nf.disc  \\ field discriminant
       %3 = -972
       ? nf.index \\ index of power basis order in maximal order
       %4 = 2
       ? nf.zk    \\ integer basis, lifted to Q[X]
       %5 = [1, x, 1/2*x^2]
       ? nf.sign  \\ signature
       %6 = [1, 1]
       ? factor(abs(nf.disc ))  \\ determines ramified primes
       %7 =
       [2 2]

       [3 5]
       ? idealfactor(nf, 2)
       %8 =
       [[2, [0, 0, -1]~, 3, 1, [0, 1, 0]~] 3]  \\  P_2^3

In case pol has a huge discriminant which is difficult to factor, the special input format [pol,B] is also accepted where pol is a polynomial as above and B is the integer basis, as would be computed by `nfbasis`. This is useful if the integer basis is known in advance, or was computed conditionnally.

      ? pol = polcompositum(x^5 - 101, polcyclo(7))[1];
       ? B = nfbasis(pol, 1);   \\ faster than nfbasis(pol), but conditional
       ? nf = nfinit( [pol, B] );
       ? factor( abs(nf.disc) )
       [5 18]

       [7 25]

       [101 24]

`B` is conditional when its discriminant, which is `nf.disc`, can't be factored. In this example, the above factorization proves the correctness of the computation.

If flag = 2: pol is changed into another polynomial P defining the same number field, which is as simple as can easily be found using the `polred` algorithm, and all the subsequent computations are done using this new polynomial. In particular, the first component of the result is the modified polynomial.

If flag = 3, does a `polred` as in case 2, but outputs [nf,`Mod`(a,P)], where nf is as before and `Mod`(a,P) = `Mod`(x,pol) gives the change of variables. This is implicit when pol is not monic: first a linear change of variables is performed, to get a monic polynomial, then a `polred` reduction.

If flag = 4, as 2 but uses a partial `polred`.

If flag = 5, as 3 using a partial `polred`.

The library syntax is nfinit0(x,flag,prec).

#### nfisideal(nf,x)

returns 1 if x is an ideal in the number field nf, 0 otherwise.

The library syntax is isideal(x).

#### nfisincl(x,y)

tests whether the number field K defined by the polynomial x is conjugate to a subfield of the field L defined by y (where x and y must be in Q[X]). If they are not, the output is the number 0. If they are, the output is a vector of polynomials, each polynomial a representing an embedding of K into L, i.e.being such that y | x o a.

If y is a number field (nf), a much faster algorithm is used (factoring x over y using `nffactor`). Before version 2.0.14, this wasn't guaranteed to return all the embeddings, hence was triggered by a special flag. This is no more the case.

The library syntax is nfisincl(x,y,flag).

#### nfisisom(x,y)

as `nfisincl`, but tests for isomorphism. If either x or y is a number field, a much faster algorithm will be used.

The library syntax is nfisisom(x,y,flag).

#### nfnewprec(nf)

transforms the number field nf into the corresponding data using current (usually larger) precision. This function works as expected if nf is in fact a bnf (update bnf to current precision) but may be quite slow (many generators of principal ideals have to be computed).

The library syntax is nfnewprec(nf,prec).

#### nfkermodpr(nf,a,pr)

kernel of the matrix a in Z_K/pr, where pr is in modpr format (see `nfmodprinit`).

The library syntax is nfkermodpr(nf,a,pr).

#### nfmodprinit(nf,pr)

transforms the prime ideal pr into `modpr` format necessary for all operations modulo pr in the number field nf.

The library syntax is nfmodprinit(nf,pr).

#### nfsubfields(pol,{d = 0})

finds all subfields of degree d of the number field defined by the (monic, integral) polynomial pol (all subfields if d is null or omitted). The result is a vector of subfields, each being given by [g,h], where g is an absolute equation and h expresses one of the roots of g in terms of the root x of the polynomial defining nf. This routine uses J.Klüners's algorithm in the general case, and B.Allombert's `galoissubfields` when nf is Galois (with weakly supersolvable Galois group).

The library syntax is subfields(nf,d).

#### nfroots({nf},x)

roots of the polynomial x in the number field nf given by `nfinit` without multiplicity (in Q if nf is omitted). x has coefficients in the number field (scalar, polmod, polynomial, column vector). The main variable of nf must be of lower priority than that of x (see Section [Label: se:priority]). However if the coefficients of the number field occur explicitly (as polmods) as coefficients of x, the variable of these polmods must be the same as the main variable of t (see `nffactor`).

The library syntax is nfroots(nf,x).

#### nfrootsof1(nf)

computes the number of roots of unity w and a primitive w-th root of unity (expressed on the integral basis) belonging to the number field nf. The result is a two-component vector [w,z] where z is a column vector expressing a primitive w-th root of unity on the integral basis `nf.zk`.

The library syntax is rootsof1(nf).

#### nfsnf(nf,x)

given a torsion module x as a 3-component row vector [A,I,J] where A is a square invertible n x n matrix, I and J are two ideal lists, outputs an ideal list d_1,...,d_n which is the Smith normal form of x. In other words, x is isomorphic to Z_K/d_1oplus...oplusZ_K/d_n and d_i divides d_{i-1} for i `>=` 2. The link between x and [A,I,J] is as follows: if e_i is the canonical basis of K^n, I = [b_1,...,b_n] and J = [a_1,...,a_n], then x is isomorphic to (b_1e_1oplus...oplus b_ne_n) / (a_1A_1oplus...oplus a_nA_n) , where the A_j are the columns of the matrix A. Note that every finitely generated torsion module can be given in this way, and even with b_i = Z_K for all i.

The library syntax is nfsmith(nf,x).

#### nfsolvemodpr(nf,a,b,pr)

solution of a.x = b in Z_K/pr, where a is a matrix and b a column vector, and where pr is in modpr format (see `nfmodprinit`).

The library syntax is nfsolvemodpr(nf,a,b,pr).

#### polcompositum(P,Q,{flag = 0})

P and Q being squarefree polynomials in Z[X] in the same variable, outputs the simple factors of the étale Q-algebra A = Q(X, Y) / (P(X), Q(Y)). The factors are given by a list of polynomials R in Z[X], associated to the number field Q(X)/ (R), and sorted by increasing degree (with respect to lexicographic ordering for factors of equal degrees). Returns an error if one of the polynomials is not squarefree.

Note that it is more efficient to reduce to the case where P and Q are irreducible first. The routine will not perform this for you, since it may be expensive, and the inputs are irreducible in most applications anyway. Assuming P is irreducible (of smaller degree than Q for efficiency), it is in general much faster to proceed as follows

       nf = nfinit(P); L = nffactor(nf, Q)[,1];
        vector(#L, i, rnfequation(nf, L[i]))

to obtain the same result. If you are only interested in the degrees of the simple factors, the `rnfequation` instruction can be replaced by a trivial `poldegree(P) * poldegree(L[i])`.

If flag = 1, outputs a vector of 4-component vectors [R,a,b,k], where R ranges through the list of all possible compositums as above, and a (resp. b) expresses the root of P (resp. Q) as an element of Q(X)/(R). Finally, k is a small integer such that b + ka = X modulo R.

A compositum is quite often defined by a complicated polynomial, which it is advisable to reduce before further work. Here is a simple example involving the field Q(zeta_5, 5^{1/5}):

    ? z = polcompositum(x^5 - 5, polcyclo(5), 1)[1];
     ? pol = z[1]                 \\
    pol defines the compositum
     %2 = x^20 + 5*x^19 + 15*x^18 + 35*x^17 + 70*x^16 + 141*x^15 + 260*x^14 \
       + 355*x^13 + 95*x^12 - 1460*x^11 - 3279*x^10 - 3660*x^9 - 2005*x^8    \
       + 705*x^7 + 9210*x^6 + 13506*x^5 + 7145*x^4 - 2740*x^3 + 1040*x^2     \
       - 320*x + 256
     ? a = z[2]; a^5 - 5          \\
    a is a fifth root of 5
     %3 = 0
     ? z = polredabs(pol, 1);     \\ look for a simpler polynomial
     ? pol = z[1]
     %5 = x^20 + 25*x^10 + 5
     ? a = subst(a.pol, x, z[2])  \\
    a in the new coordinates
     %6 = Mod(-5/22*x^19 + 1/22*x^14 - 123/22*x^9 + 9/11*x^4, x^20 + 25*x^10 + 5)

The library syntax is polcompositum0(P,Q,flag).

#### polgalois(x)

Galois group of the non-constant polynomial x belongs to Q[X]. In the present version 2.2.13, x must be irreducible and the degree of x must be less than or equal to 7. On certain versions for which the data file of Galois resolvents has been installed (available in the Unix distribution as a separate package), degrees 8, 9, 10 and 11 are also implemented.

The output is a 4-component vector [n,s,k,name] with the following meaning: n is the cardinality of the group, s is its signature (s = 1 if the group is a subgroup of the alternating group A_n, s = -1 otherwise) and name is a character string containing name of the transitive group according to the GAP 4 transitive groups library by Alexander Hulpke.

k is more arbitrary and the choice made up to version2.2.3 of PARI is rather unfortunate: for n > 7, k is the numbering of the group among all transitive subgroups of S_n, as given in "The transitive groups of degree up to eleven", G.Butler and J.McKay, Communications in Algebra, vol.11, 1983, pp.863--911 (group k is denoted T_k there). And for n `<=` 7, it was ad hoc, so as to ensure that a given triple would design a unique group. Specifically, for polynomials of degree `<=` 7, the groups are coded as follows, using standard notations

In degree 1: S_1 = [1,1,1].

In degree 2: S_2 = [2,-1,1].

In degree 3: A_3 = C_3 = [3,1,1], S_3 = [6,-1,1].

In degree 4: C_4 = [4,-1,1], V_4 = [4,1,1], D_4 = [8,-1,1], A_4 = [12,1,1], S_4 = [24,-1,1].

In degree 5: C_5 = [5,1,1], D_5 = [10,1,1], M_{20} = [20,-1,1], A_5 = [60,1,1], S_5 = [120,-1,1].

In degree 6: C_6 = [6,-1,1], S_3 = [6,-1,2], D_6 = [12,-1,1], A_4 = [12,1,1], G_{18} = [18,-1,1], S_4^ -= [24,-1,1], A_4 x C_2 = [24,-1,2], S_4^ += [24,1,1], G_{36}^ -= [36,-1,1], G_{36}^ += [36,1,1], S_4 x C_2 = [48,-1,1], A_5 = PSL_2(5) = [60,1,1], G_{72} = [72,-1,1], S_5 = PGL_2(5) = [120,-1,1], A_6 = [360,1,1], S_6 = [720,-1,1].

In degree 7: C_7 = [7,1,1], D_7 = [14,-1,1], M_{21} = [21,1,1], M_{42} = [42,-1,1], PSL_2(7) = PSL_3(2) = [168,1,1], A_7 = [2520,1,1], S_7 = [5040,-1,1].

This is deprecated and obsolete, but for reasons of backward compatibility, we cannot change this behaviour yet. So you can use the default `new_galois_format` to switch to a consistent naming scheme, namely k is always the standard numbering of the group among all transitive subgroups of S_n. If this default is in effect, the above groups will be coded as:

In degree 1: S_1 = [1,1,1].

In degree 2: S_2 = [2,-1,1].

In degree 3: A_3 = C_3 = [3,1,1], S_3 = [6,-1,2].

In degree 4: C_4 = [4,-1,1], V_4 = [4,1,2], D_4 = [8,-1,3], A_4 = [12,1,4], S_4 = [24,-1,5].

In degree 5: C_5 = [5,1,1], D_5 = [10,1,2], M_{20} = [20,-1,3], A_5 = [60,1,4], S_5 = [120,-1,5].

In degree 6: C_6 = [6,-1,1], S_3 = [6,-1,2], D_6 = [12,-1,3], A_4 = [12,1,4], G_{18} = [18,-1,5], A_4 x C_2 = [24,-1,6], S_4^ += [24,1,7], S_4^ -= [24,-1,8], G_{36}^ -= [36,-1,9], G_{36}^ += [36,1,10], S_4 x C_2 = [48,-1,11], A_5 = PSL_2(5) = [60,1,12], G_{72} = [72,-1,13], S_5 = PGL_2(5) = [120,-1,14], A_6 = [360,1,15], S_6 = [720,-1,16].

In degree 7: C_7 = [7,1,1], D_7 = [14,-1,2], M_{21} = [21,1,3], M_{42} = [42,-1,4], PSL_2(7) = PSL_3(2) = [168,1,5], A_7 = [2520,1,6], S_7 = [5040,-1,7].

Warning: The method used is that of resolvent polynomials and is sensitive to the current precision. The precision is updated internally but, in very rare cases, a wrong result may be returned if the initial precision was not sufficient.

The library syntax is polgalois(x,prec). To enable the new format in library mode, set the global variable `new_galois_format` to 1.

#### polred(x,{flag = 0},{fa})

finds polynomials with reasonably small coefficients defining subfields of the number field defined by x. One of the polynomials always defines Q (hence is equal to x-1), and another always defines the same number field as x if x is irreducible. All x accepted by `nfinit` are also allowed here (e.g. non-monic polynomials, `nf`, `bnf`, `[x,Z_K_basis]`).

The following binary digits of flag are significant:

1: possibly use a suborder of the maximal order. The primes dividing the index of the order chosen are larger than `primelimit` or divide integers stored in the `addprimes` table.

2: gives also elements. The result is a two-column matrix, the first column giving the elements defining these subfields, the second giving the corresponding minimal polynomials.

If fa is given, it is assumed that it is the two-column matrix of the factorization of the discriminant of the polynomial x.

The library syntax is polred0(x,flag,fa), where an omitted fa is coded by `NULL`. Also available are `polred(x)` and `factoredpolred(x,fa)`, both corresponding to flag = 0.

#### polredabs(x,{flag = 0})

finds one of the polynomial defining the same number field as the one defined by x, and such that the sum of the squares of the modulus of the roots (i.e.the T_2-norm) is minimal. All x accepted by `nfinit` are also allowed here (e.g. non-monic polynomials, `nf`, `bnf`, `[x,Z_K_basis]`).

Warning: this routine uses an exponential-time algorithm to enumerate all potential generators, and may be exceedingly slow when the number field has many subfields, hence a lot of elements of small T_2-norm. E.g. do not try it on the compositum of many quadratic fields, use `polred` instead.

The binary digits of flag mean

1: outputs a two-component row vector [P,a], where P is the default output and a is an element expressed on a root of the polynomial P, whose minimal polynomial is equal to x.

4: gives all polynomials of minimal T_2 norm (of the two polynomials P(x) and P(-x), only one is given).

16: possibly use a suborder of the maximal order. The primes dividing the index of the order chosen are larger than `primelimit` or divide integers stored in the `addprimes` table. In that case it may happen that the output polynomial does not have minimal T_2 norm.

The library syntax is polredabs0(x,flag).

#### polredord(x)

finds polynomials with reasonably small coefficients and of the same degree as that of x defining suborders of the order defined by x. One of the polynomials always defines Q (hence is equal to (x-1)^n, where n is the degree), and another always defines the same order as x if x is irreducible.

The library syntax is ordred(x).

#### poltschirnhaus(x)

applies a random Tschirnhausen transformation to the polynomial x, which is assumed to be non-constant and separable, so as to obtain a new equation for the étale algebra defined by x. This is for instance useful when computing resolvents, hence is used by the `polgalois` function.

The library syntax is tschirnhaus(x).

#### rnfalgtobasis(rnf,x)

expresses x on the relative integral basis. Here, rnf is a relative number field extension L/K as output by `rnfinit`, and x an element of L in absolute form, i.e. expressed as a polynomial or polmod with polmod coefficients, not on the relative integral basis.

The library syntax is rnfalgtobasis(rnf,x).

#### rnfbasis(bnf, M)

let K the field represented by bnf, as output by `bnfinit`. M is a projective Z_K-module given by a pseudo-basis, as output by `rnfhnfbasis`. The routine returns either a true Z_K-basis of M if it exists, or an n+1-element generating set of M if not, where n is the rank of M over K. (Note that n is the size of the pseudo-basis.)

It is allowed to use a polynomial P with coefficients in K instead of M, in which case, M is defined as the ring of integers of K[X]/(P) (P is assumed irreducible over K), viewed as a Z_K-module.

The library syntax is rnfbasis(bnf,x).

#### rnfbasistoalg(rnf,x)

computes the representation of x as a polmod with polmods coefficients. Here, rnf is a relative number field extension L/K as output by `rnfinit`, and x an element of L expressed on the relative integral basis.

The library syntax is rnfbasistoalg(rnf,x).

#### rnfcharpoly(nf,T,a,{v = x})

characteristic polynomial of a over nf, where a belongs to the algebra defined by T over nf, i.e.nf[X]/(T). Returns a polynomial in variable v (x by default).

The library syntax is rnfcharpoly(nf,T,a,v), where v is a variable number.

#### rnfconductor(bnf,pol,{flag = 0})

given bnf as output by `bnfinit`, and pol a relative polynomial defining an Abelian extension, computes the class field theory conductor of this Abelian extension. The result is a 3-component vector [conductor,rayclgp,subgroup], where conductor is the conductor of the extension given as a 2-component row vector [f_0,f_ oo ], rayclgp is the full ray class group corresponding to the conductor given as a 3-component vector [h,cyc,gen] as usual for a group, and subgroup is a matrix in HNF defining the subgroup of the ray class group on the given generators gen. If flag is non-zero, check that pol indeed defines an Abelian extension, return 0 if it does not.

The library syntax is rnfconductor(rnf,pol,flag).

#### rnfdedekind(nf,pol,pr)

given a number field nf as output by `nfinit` and a polynomial pol with coefficients in nf defining a relative extension L of nf, evaluates the relative Dedekind criterion over the order defined by a root of pol for the prime ideal pr and outputs a 3-component vector as the result. The first component is a flag equal to 1 if the enlarged order could be proven to be pr-maximal and to 0 otherwise (it may be maximal in the latter case if pr is ramified in L), the second component is a pseudo-basis of the enlarged order and the third component is the valuation at pr of the order discriminant.

The library syntax is rnfdedekind(nf,pol,pr).

#### rnfdet(nf,M)

given a pseudo-matrix M over the maximal order of nf, computes its determinant.

The library syntax is rnfdet(nf,M).

#### rnfdisc(nf,pol)

given a number field nf as output by `nfinit` and a polynomial pol with coefficients in nf defining a relative extension L of nf, computes the relative discriminant of L. This is a two-element row vector [D,d], where D is the relative ideal discriminant and d is the relative discriminant considered as an element of nf^*/{nf^*}^2. The main variable of nf must be of lower priority than that of pol, see Section [Label: se:priority].

The library syntax is rnfdiscf(bnf,pol).

#### rnfeltabstorel(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being an element of L expressed as a polynomial modulo the absolute equation `rnf.pol`, computes x as an element of the relative extension L/K as a polmod with polmod coefficients.

The library syntax is rnfelementabstorel(rnf,x).

#### rnfeltdown(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being an element of L expressed as a polynomial or polmod with polmod coefficients, computes x as an element of K as a polmod, assuming x is in K (otherwise an error will occur). If x is given on the relative integral basis, apply `rnfbasistoalg` first, otherwise PARI will believe you are dealing with a vector.

The library syntax is rnfelementdown(rnf,x).

#### rnfeltreltoabs(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being an element of L expressed as a polynomial or polmod with polmod coefficients, computes x as an element of the absolute extension L/Q as a polynomial modulo the absolute equation `rnf.pol`. If x is given on the relative integral basis, apply `rnfbasistoalg` first, otherwise PARI will believe you are dealing with a vector.

The library syntax is rnfelementreltoabs(rnf,x).

#### rnfeltup(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being an element of K expressed as a polynomial or polmod, computes x as an element of the absolute extension L/Q as a polynomial modulo the absolute equation `rnf.pol`. If x is given on the integral basis of K, apply `nfbasistoalg` first, otherwise PARI will believe you are dealing with a vector.

The library syntax is rnfelementup(rnf,x).

#### rnfequation(nf,pol,{flag = 0})

given a number field nf as output by `nfinit` (or simply a polynomial) and a polynomial pol with coefficients in nf defining a relative extension L of nf, computes the absolute equation of L over Q.

If flag is non-zero, outputs a 3-component row vector [z,a,k], where z is the absolute equation of L over Q, as in the default behaviour, a expresses as an element of L a root alpha of the polynomial defining the base field nf, and k is a small integer such that theta = beta+kalpha where theta is a root of z and beta a root of pol.

The main variable of nf must be of lower priority than that of pol (see Section [Label: se:priority]). Note that for efficiency, this does not check whether the relative equation is irreducible over nf, but only if it is squarefree. If it is reducible but squarefree, the result will be the absolute equation of the étale algebra defined by pol. If pol is not squarefree, an error message will be issued.

The library syntax is rnfequation0(nf,pol,flag).

#### rnfhnfbasis(bnf,x)

given bnf as output by `bnfinit`, and either a polynomial x with coefficients in bnf defining a relative extension L of bnf, or a pseudo-basis x of such an extension, gives either a true bnf-basis of L in upper triangular Hermite normal form, if it exists, and returns 0 otherwise.

The library syntax is rnfhnfbasis(nf,x).

#### rnfidealabstorel(rnf,x)

let rnf be a relative number field extension L/K as output by `rnfinit`, and x an ideal of the absolute extension L/Q given by a Z-basis of elements of L. Returns the relative pseudo-matrix in HNF giving the ideal x considered as an ideal of the relative extension L/K.

If x is an ideal in HNF form, associated to an nf structure, for instance as output by `idealhnf`(nf,...), use `rnfidealabstorel(rnf, nf.zk * x)` to convert it to a relative ideal.

The library syntax is rnfidealabstorel(rnf,x).

#### rnfidealdown(rnf,x)

let rnf be a relative number field extension L/K as output by `rnfinit`, and x an ideal of L, given either in relative form or by a Z-basis of elements of L (see Section [Label: se:rnfidealabstorel]), returns the ideal of K below x, i.e.the intersection of x with K.

The library syntax is rnfidealdown(rnf,x).

#### rnfidealhnf(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being a relative ideal (which can be, as in the absolute case, of many different types, including of course elements), computes the HNF pseudo-matrix associated to x, viewed as a Z_K-module.

The library syntax is rnfidealhermite(rnf,x).

#### rnfidealmul(rnf,x,y)

rnf being a relative number field extension L/K as output by `rnfinit` and x and y being ideals of the relative extension L/K given by pseudo-matrices, outputs the ideal product, again as a relative ideal.

The library syntax is rnfidealmul(rnf,x,y).

#### rnfidealnormabs(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being a relative ideal (which can be, as in the absolute case, of many different types, including of course elements), computes the norm of the ideal x considered as an ideal of the absolute extension L/Q. This is identical to `idealnorm(rnfidealnormrel(rnf,x))`, but faster.

The library syntax is rnfidealnormabs(rnf,x).

#### rnfidealnormrel(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being a relative ideal (which can be, as in the absolute case, of many different types, including of course elements), computes the relative norm of x as a ideal of K in HNF.

The library syntax is rnfidealnormrel(rnf,x).

#### rnfidealreltoabs(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being a relative ideal, gives the ideal xZ_L as an absolute ideal of L/Q, in the form of a Z-basis, given by a vector of polynomials (modulo `rnf.pol`). The following routine might be useful:

        \\ return y = rnfidealreltoabs(rnf,...) as an ideal in HNF form
         \\ associated to nf = nfinit( rnf.pol );
         idealgentoHNF(nf, y) = mathnf( Mat( nfalgtobasis(nf, y) ) );

The library syntax is rnfidealreltoabs(rnf,x).

#### rnfidealtwoelt(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being an ideal of the relative extension L/K given by a pseudo-matrix, gives a vector of two generators of x over Z_L expressed as polmods with polmod coefficients.

The library syntax is rnfidealtwoelement(rnf,x).

#### rnfidealup(rnf,x)

rnf being a relative number field extension L/K as output by `rnfinit` and x being an ideal of K, gives the ideal xZ_L as an absolute ideal of L/Q, in the form of a Z-basis, given by a vector of polynomials (modulo `rnf.pol`). The following routine might be useful:

        \\ return y = rnfidealup(rnf,...) as an ideal in HNF form
         \\ associated to nf = nfinit( rnf.pol );
         idealgentoHNF(nf, y) = mathnf( Mat( nfalgtobasis(nf, y) ) );

The library syntax is rnfidealup(rnf,x).

#### rnfinit(nf,pol)

nf being a number field in `nfinit` format considered as base field, and pol a polynomial defining a relative extension over nf, this computes all the necessary data to work in the relative extension. The main variable of pol must be of higher priority (see Section [Label: se:priority]) than that of nf, and the coefficients of pol must be in nf.

The result is a row vector, whose components are technical. In the following description, we let K be the base field defined by nf, m the degree of the base field, n the relative degree, L the large field (of relative degree n or absolute degree nm), r_1 and r_2 the number of real and complex places of K.

rnf[1] contains the relative polynomial pol.

rnf[2] is currently unused.

rnf[3] is a two-component row vector [d(L/K),s] where d(L/K) is the relative ideal discriminant of L/K and s is the discriminant of L/K viewed as an element of K^*/(K^*)^2, in other words it is the output of `rnfdisc`.

rnf[4] is the ideal index f, i.e.such that d(pol)Z_K = f^2d(L/K).

rnf[5] is currently unused.

rnf[6] is currently unused.

rnf[7] is a two-component row vector, where the first component is the relative integral pseudo basis expressed as polynomials (in the variable of pol) with polmod coefficients in nf, and the second component is the ideal list of the pseudobasis in HNF.

rnf[8] is the inverse matrix of the integral basis matrix, with coefficients polmods in nf.

rnf[9] is currently unused.

rnf[10] is nf.

rnf[11] is the output of `rnfequation(nf, pol, 1)`. Namely, a vector vabs with 3 entries describing the absolute extension L/Q. vabs[1] is an absolute equation, more conveniently obtained as `rnf.pol`. vabs[2] expresses the generator alpha of the number field nf as a polynomial modulo the absolute equation vabs[1]. vabs[3] is a small integer k such that, if beta is an abstract root of pol and alpha the generator of nf, the generator whose root is vabs will be beta + k alpha. Note that one must be very careful if k != 0 when dealing simultaneously with absolute and relative quantities since the generator chosen for the absolute extension is not the same as for the relative one. If this happens, one can of course go on working, but we strongly advise to change the relative polynomial so that its root will be beta + k alpha. Typically, the GP instruction would be

`pol = subst(pol, x, x - k*Mod(y,nf.pol))`

rnf[12] is by default unused and set equal to 0. This field is used to store further information about the field as it becomes available (which is rarely needed, hence would be too expensive to compute during the initial `rnfinit` call).

The library syntax is rnfinitalg(nf,pol,prec).

#### rnfisfree(bnf,x)

given bnf as output by `bnfinit`, and either a polynomial x with coefficients in bnf defining a relative extension L of bnf, or a pseudo-basis x of such an extension, returns true (1) if L/bnf is free, false (0) if not.

The library syntax is rnfisfree(bnf,x), and the result is a `long`.

#### rnfisnorm(T,a,{flag = 0})

similar to `bnfisnorm` but in the relative case. T is as output by `rnfisnorminit` applied to the extension L/K. This tries to decide whether the element a in K is the norm of some x in the extension L/K.

The output is a vector [x,q], where a = \Norm(x)*q. The algorithm looks for a solution x which is an S-integer, with S a list of places of K containing at least the ramified primes, the generators of the class group of L, as well as those primes dividing a. If L/K is Galois, then this is enough; otherwise, flag is used to add more primes to S: all the places above the primes p `<=` flag (resp.p|flag) if flag > 0 (resp.flag < 0).

The answer is guaranteed (i.e.a is a norm iff q = 1) if the field is Galois, or, under GRH, if S contains all primes less than 12log^2|\disc(M)|, where M is the normal closure of L/K.

If `rnfisnorminit` has determined (or was told) that L/K is Galois, and flag != 0, a Warning is issued (so that you can set flag = 1 to check whether L/K is known to be Galois, according to T). Example:

    bnf = bnfinit(y^3 + y^2 - 2*y - 1);
     p = x^2 + Mod(y^2 + 2*y + 1, bnf.pol);
     T = rnfisnorminit(bnf, p);
     rnfisnorm(T, 17)

checks whether 17 is a norm in the Galois extension Q(beta) / Q(alpha), where alpha^3 + alpha^2 - 2alpha - 1 = 0 and beta^2 + alpha^2 + 2alpha + 1 = 0 (it is).

The library syntax is rnfisnorm(T,x,flag).

#### rnfisnorminit(pol,polrel,{flag = 2})

let K be defined by a root of pol, and L/K the extension defined by the polynomial polrel. As usual, pol can in fact be an nf, or bnf, etc; if pol has degree 1 (the base field is Q), polrel is also allowed to be an nf, etc. Computes technical data needed by `rnfisnorm` to solve norm equations Nx = a, for x in L, and a in K.

If flag = 0, do not care whether L/K is Galois or not.

If flag = 1, L/K is assumed to be Galois (unchecked), which speeds up `rnfisnorm`.

If flag = 2, let the routine determine whether L/K is Galois.

The library syntax is rnfisnorminit(pol,polrel,flag).

#### rnfkummer(bnr,{subgroup},{deg = 0})

bnr being as output by `bnrinit`, finds a relative equation for the class field corresponding to the module in bnr and the given congruence subgroup (the full ray class field if subgroup is omitted). If deg is positive, outputs the list of all relative equations of degree deg contained in the ray class field defined by bnr, with the same conductor as (bnr, subgroup).

Warning: this routine only works for subgroups of prime index. It uses Kummer theory, adjoining necessary roots of unity (it needs to compute a tough `bnfinit` here), and finds a generator via Hecke's characterization of ramification in Kummer extensions of prime degree. If your extension does not have prime degree, for the time being, you have to split it by hand as a tower / compositum of such extensions.

The library syntax is rnfkummer(bnr,subgroup,deg,prec), where deg is a `long` and an omitted subgroup is coded as `NULL`

#### rnflllgram(nf,pol,order)

given a polynomial pol with coefficients in nf defining a relative extension L and a suborder order of L (of maximal rank), as output by `rnfpseudobasis`(nf,pol) or similar, gives [[neworder],U], where neworder is a reduced order and U is the unimodular transformation matrix.

The library syntax is rnflllgram(nf,pol,order,prec).

#### rnfnormgroup(bnr,pol)

bnr being a big ray class field as output by `bnrinit` and pol a relative polynomial defining an Abelian extension, computes the norm group (alias Artin or Takagi group) corresponding to the Abelian extension of bnf = bnr[1] defined by pol, where the module corresponding to bnr is assumed to be a multiple of the conductor (i.e.pol defines a subextension of bnr). The result is the HNF defining the norm group on the given generators of bnr[5][3]. Note that neither the fact that pol defines an Abelian extension nor the fact that the module is a multiple of the conductor is checked. The result is undefined if the assumption is not correct.

The library syntax is rnfnormgroup(bnr,pol).

#### rnfpolred(nf,pol)

relative version of `polred`. Given a monic polynomial pol with coefficients in nf, finds a list of relative polynomials defining some subfields, hopefully simpler and containing the original field. In the present version 2.2.13, this is slower and less efficient than `rnfpolredabs`.

The library syntax is rnfpolred(nf,pol,prec).

#### rnfpolredabs(nf,pol,{flag = 0})

relative version of `polredabs`. Given a monic polynomial pol with coefficients in nf, finds a simpler relative polynomial defining the same field. The binary digits of flag mean

1: returns [P,a] where P is the default output and a is an element expressed on a root of P whose characteristic polynomial is pol

2: returns an absolute polynomial (same as rnfequation(nf,rnfpolredabs(nf,pol)) but faster).

16: possibly use a suborder of the maximal order. This is slower than the default when the relative discriminant is smooth, and much faster otherwise. See Section [Label: se:polredabs].

Remark. In the present implementation, this is both faster and much more efficient than `rnfpolred`, the difference being more dramatic than in the absolute case. This is because the implementation of `rnfpolred` is based on (a partial implementation of) an incomplete reduction theory of lattices over number fields, the function `rnflllgram`, which deserves to be improved.

The library syntax is rnfpolredabs(nf,pol,flag,prec).

#### rnfpseudobasis(nf,pol)

given a number field nf as output by `nfinit` and a polynomial pol with coefficients in nf defining a relative extension L of nf, computes a pseudo-basis (A,I) for the maximal order Z_L viewed as a Z_K-module, and the relative discriminant of L. This is output as a four-element row vector [A,I,D,d], where D is the relative ideal discriminant and d is the relative discriminant considered as an element of nf^*/{nf^*}^2.

The library syntax is rnfpseudobasis(nf,pol).

#### rnfsteinitz(nf,x)

given a number field nf as output by `nfinit` and either a polynomial x with coefficients in nf defining a relative extension L of nf, or a pseudo-basis x of such an extension as output for example by `rnfpseudobasis`, computes another pseudo-basis (A,I) (not in HNF in general) such that all the ideals of I except perhaps the last one are equal to the ring of integers of nf, and outputs the four-component row vector [A,I,D,d] as in `rnfpseudobasis`. The name of this function comes from the fact that the ideal class of the last ideal of I, which is well defined, is the Steinitz class of the Z_K-module Z_L (its image in SK_0(Z_K)).

The library syntax is rnfsteinitz(nf,x).

#### subgrouplist(bnr,{bound},{flag = 0})

bnr being as output by `bnrinit` or a list of cyclic components of a finite Abelian group G, outputs the list of subgroups of G. Subgroups are given as HNF left divisors of the SNF matrix corresponding to G.

Warning: the present implementation cannot treat a group G where any cyclic factor has more than 2^{31}, resp.2^{63} elements on a 32-bit, resp.64-bit architecture. `forsubgroup` is a bit more general and can handle G if all p-Sylow subgroups of G satisfy the condition above.

If flag = 0 (default) and bnr is as output by `bnrinit`, gives only the subgroups whose modulus is the conductor. Otherwise, the modulus is not taken into account.

If bound is present, and is a positive integer, restrict the output to subgroups of index less than bound. If bound is a vector containing a single positive integer B, then only subgroups of index exactly equal to B are computed. For instance

    ? subgrouplist([6,2])
     %1 = [[6, 0; 0, 2], [2, 0; 0, 2], [6, 3; 0, 1], [2, 1; 0, 1], [3, 0; 0, 2],
           [1, 0; 0, 2], [6, 0; 0, 1], [2, 0; 0, 1], [3, 0; 0, 1], [1, 0; 0, 1]]
     ? subgrouplist([6,2],3)    \\ index less than 3
     %2 = [[2, 1; 0, 1], [1, 0; 0, 2], [2, 0; 0, 1], [3, 0; 0, 1], [1, 0; 0, 1]]
     ? subgrouplist([6,2],[3])  \\ index 3
     %3 = [[3, 0; 0, 1]]
     ? bnr = bnrinit(bnfinit(x), [120,[1]], 1);
     ? L = subgrouplist(bnr, [8]);

In the last example, L corresponds to the 24 subfields of Q(zeta_{120}), of degree 8 and conductor 120 oo (by setting flag, we see there are a total of 43 subgroups of degree 8).

    ? vector(#L, i, galoissubcyclo(bnr, L[i]))

will produce their equations. (For a general base field, you would have to rely on `bnrstark`, or `rnfkummer`.)

The library syntax is subgrouplist0(bnr,bound,flag), where flag is a long integer, and an omitted bound is coded by `NULL`.

#### zetak(znf,x,{flag = 0})

znf being a number field initialized by `zetakinit` (not by `nfinit`), computes the value of the Dedekind zeta function of the number field at the complex number x. If flag = 1 computes Dedekind Lambda function instead (i.e.the product of the Dedekind zeta function by its gamma and exponential factors).

CAVEAT. This implementation is not satisfactory and must be rewritten. In particular

* The accuracy of the result depends in an essential way on the accuracy of both the `zetakinit` program and the current accuracy. Be wary in particular that x of large imaginary part or, on the contrary, very close to an ordinary integer will suffer from precision loss, yielding fewer significant digits than expected. Computing with 28 eight digits of relative accuracy, we have

    ? zeta(3)
         %1 = 1.202056903159594285399738161
         ? zeta(3-1e-20)
         %2 = 1.202056903159594285401719424
         ? zetak(zetakinit(x), 3-1e-20)
         %3 = 1.2020569031595952919  \\ 5 digits are wrong
         ? zetak(zetakinit(x), 3-1e-28)
         %4 = -25.33411749           \\ junk

* As the precision increases, results become unexpectedly completely wrong:

        ? \p100
         ? zetak(zetakinit(x^2-5), -1) - 1/30
         %1 = 7.26691813 E-108    \\ perfect
         ? \p150
         ? zetak(zetakinit(x^2-5), -1) - 1/30
         %2 = -2.486113578 E-156  \\ perfect
         ? \p200
         ? zetak(zetakinit(x^2-5), -1) - 1/30
         %3 = 4.47... E-75        \\ more than half of the digits are wrong
         ? \p250
         ? zetak(zetakinit(x^2-5), -1) - 1/30
         %4 = 1.6 E43             \\ junk

The library syntax is glambdak(znf,x,prec) or `gzetak(znf,x,prec)`.

#### zetakinit(x)

computes a number of initialization data concerning the number field defined by the polynomial x so as to be able to compute the Dedekind zeta and lambda functions (respectively `zetak`(x) and `zetak`(x,1)). This function calls in particular the `bnfinit` program. The result is a 9-component vector v whose components are very technical and cannot really be used by the user except through the `zetak` function. The only component which can be used if it has not been computed already is v[1][4] which is the result of the `bnfinit` call.

This function is very inefficient and should be rewritten. It needs to computes millions of coefficients of the corresponding Dirichlet series if the precision is big. Unless the discriminant is small it will not be able to handle more than 9 digits of relative precision. For instance, `zetakinit(x^8 - 2)` needs 440MB of memory at default precision.

The library syntax is initzeta(x).