Let K = ℚ[X] / (T) be a number field, where T ∈ ℤ[X] is monic, and let ℤ_K be its ring of integers. Three basic number field structures can be attached to K in GP:

* nf denotes a number field, i.e. a data structure output by nfinit. This contains the basic arithmetic data attached 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: its units U(K) and class group Cl(K), as abstract abelian groups and in terms of generators and relations). As well as technical data allowing to solve discrete logarithm problems in these two groups (write elements as products of fixed generators).

* 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 attached to the discrete logarithm problem therein.

Functions related to these structures, share the prefix nf, bnf, bnr respectively. They take as first argument a number field structure of that type, respectively output by 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. 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 bnfinit function implements the sub-exponential algorithms for finding class and unit groups under GRH, due to Hafner-McCurley, Buchmann and Cohen-Diaz-Olivier. If GRH is false, then the bnf may be incorrect and all routines requiring a bnf argument may then return wrong results, in particular bnrinit.

Important warning. Any of the class number, class group structure, class group generators, regulator and fundamental units may be wrong, independently of each other. And the same holds for ray class groups and S-units. The only guarantee is that the units given generate a subgroup of finite index in the full unit group. You must use bnfcertify to certify the computations unconditionally.

Since this requires exponential time, we recomend to compute as far as possible with provisional data then come back to certify what is really needed. A good example is the bnrclassfield function: once a class field is computed it is easy to check it has the expected Galois group and ramification without certifying any bnf used in the process.

GP provides "member functions" to retrieve data from structures (once they have been initialized of course). The relevant types of number fields are indicated between parentheses:

 bid (bnr ) : bid ideal structure for (ℤ_K/f)^*.

 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 ( bnf ) : fundamental units.

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

 mod (bnr ) : modulus.

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

 pol (bnr, bnf, nf ) : defining polynomial.

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

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

 reg ( bnf ) : regulator.

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

 sign (bnr, bnf, nf ) : signature [r1,r2].

 t2 (bnr, bnf, nf ) : the T₂ matrix (see nfinit).

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

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

 zkst (bnr ) : structure of (ℤ_K/m)^*.

The member functions .codiff, .t2 and .zk perform a computation and are relatively expensive in large degree: move them out of tight loops and store them in variables.

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.

An algebraic number belonging to K = ℚ[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:ℚ], 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 is not allowed.

Functions to manipulate elements in a number field share the prefix nfelt: nfeltadd, nfeltmul, nfeltnorm, etc. Their first argument is a number field structure, followed by other operands. For instance nfeltmul(K, x, y) computes xy in K.

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, as output by idealprimedec or idealfactor.

* a t_MAT, square and in Hermite Normal Form, whose columns represent a ℤ-basis of the ideal.

One may use idealhnf to convert any ideal to the last (preferred) format. Functions to create or manipulate ideals in a number field share the prefix ideal: idealadd, idealmul, idealinv, idealnorm, etc. Their first argument is a number field structure, followed by other operands. For instance idealmul(K, A, B) computes the ideal product AB. The idealred functions allows to "factor out" a principal ideal (t) from a fractional ideal B, writing it as B = tA where A is an integral ideal whose norm is bounded in terms of the discriminant of K.

An extended ideal is a 2-component vector [A, t], where A is an ideal as above and t is an algebraic number. It represent the ideal (t)A. This is useful whenever idealred is involved, implicitly working in the ideal class group, while keeping track of principal ideals. The following multiplicative ideal operations update the principal part: idealmul, idealinv, idealsqr, idealpow and idealred; e.g. using idealmul on [A,t], [B,u], we obtain [AB, tu]. In all other functions, the extended part is silently discarded, e.g. using idealadd with the above input produces A+B.

The "principal part" t in an extended ideal may be represented in any of the above forms. Additionally, and this is the preferred form, as a factorization matrix, or famat. Such factorizations (in terms of number field elements, not ideals!) can be multiplied in a formal way (generators merged, exponents added), corresponding to the multiplication in K. The empty factorization matrix factor(1) represents 1 and acts as neutral element.

When t is such a factorization matrix, elements stay in factored form, which is a convenient way to avoid coefficient explosion. To recover the conventional expanded form, try nffactorback; but many functions already accept famats as input and expanding huge elements should not be necessary.

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 bnf structure must contain the fundamental units:

  ? K = bnfinit(x^3+2^2^3+1); bnfcertify(K)
    ***   at top-level: K=bnfinit(x^3+2^2^3+1);bnfcertify(K)
    ***                                        ^ —  —  —  — -
    *** bnfcertify: precision too low in makeunits [use bnfinit(,1)].
  ? K = bnfinit(x^3+2^2^3+1, 1); \\ include units
  ? bnfcertify(K)
  %3 = 1

If flag is present, only certify that the class group is a quotient of the one computed in bnf (much simpler in general); likewise, the computed units may form a subgroup of the full unit group. In this variant, the units are no longer needed:

  ? K = bnfinit(x^3+2^2^3+1); bnfcertify(K, 1)
  %4 = 1

The library syntax is long bnfcertify0(GEN bnf, long flag ). Also available is GEN bnfcertify(GEN bnf) (flag = 0).

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

  ? K = bnfinit(x^2+23); L = bnrdisclist(K, 10); s = L[2]
  %1 = [[[Vecsmall([8]), Vecsmall([1])], [[0, 0, 0]]],
        [[Vecsmall([9]), Vecsmall([1])], [[0, 0, 0]]]]
  ? bnfdecodemodule(K, s[1][1])
  %2 =
  [2 0]
  
  [0 1]
  ? bnfdecodemodule(K,s[2][1])
  %3 =
  [2 1]
  
  [0 1]

The library syntax is GEN decodemodule(GEN nf, GEN m).

Initializes a bnf structure used in programs such as bnfisprincipal, bnfisunit. The result is conditional on the GRH, hence any output from functions requiring a bnf may be wrong. The output bnf may be certified using bnfcertify, thereby certifying all later uses of the resulting bnf. Unconditionally, the only guarantee is that the computed units generate a subgroup of finite index in the full unit group.

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 monic irreducible polynomial P with integer coefficients.

The meaning of flag is as follows:

* flag = 0 (default). This is the historical behavior, kept for compatibility reasons and speed. It has severe drawbacks but is likely to be a little faster than the alternative, twice faster say, so only use it if speed is paramount, you obtain a useful speed gain for the fields under consideration, and you are only interested in the field invariants such as the classgroup structure or its regulator. The computations involve exact algebraic numbers which are replaced by floating point embeddings for the sake of speed. If the precision is insufficient, gp may not be able to compute fundamental units, nor to solve some discrete logarithm problems. It may be possible to increase the precision of the bnf structure using nfnewprec but this may fail, in particular when fundamental units are large. In short, the resulting bnf structure is correct and contains useful information but later function calls to bnfisprincpal or bnrclassfield may fail.

When flag = 1, we keep an exact algebraic version of all floating point data and this allows to guarantee that functions using the structure will always succeed, as well as to compute the fundamental units exactly. The units are computed in compact form, as a product of small S-units, possibly with huge exponents. This flag also allows bnfisprincipal to compute generators of principal ideals in factored form as well. Be warned that expanding such products explicitly can take a very long time, but they can easily be mapped to floating point or ℓ-adic embeddings of bounded accuracy, or to K^*/(K^*)^ℓ, and this is enough for applications. In short, this flag should be used by default, unless you have a very good reason for it, for instance building massive tables of class numbers, and you do not care about units or the effect large units would have on your computation.

The tech argument (technical).

This argument is better left omitted unless default tuning turns out to be inadequate and it looks like the algorithm made little progress over a few hours (or days). This can be diagnosed interactively using setdebug(bnf,1) or higher debugging levels. Careful use of this parameter may then speed up your computations. Assuming GRH, the correction of bnfinit output does not depend on the chosen parameters.

Its format is [c₁, c₂, nrpid, max_fact, idex, usethr], You do not need to supply all values. However, should you choose to modify a subset, they must be given in the given order, where a 0 encodes "the default value". For example, to specify nrpid = 20 without affecting c₁ and c₂, you can provide [0,0,20]. Their meaning is as follows

* 0 ≤ c₁ ≤ c₂ are real numbers. For i = 1,2, let B_i = c_i(log |d_K|)², and denote by S(B) the set of maximal ideals of K whose norm is less than B. We want S(B₁) to generate Cl(K) and hope that S(B₂) can be proven to generate Cl(K).

More precisely, S(B₁) is a factorbase used to compute a tentative Cl(K) by generators and relations. We then check, using essentially bnfisprincipal, that the elements of S(B₂) belong to the span of S(B₁). Under the assumption that S(B₂) generates Cl(K), we are done.

When c₁ is unspecified (equal to 0) the algorithm takes it equal to c₂. User-supplied c_i are only used to compute initial guesses for the bounds B_i, and the algorithm increases them until one can prove under GRH that S(B₂) generates Cl(K). A uniform result of Grenié and Molteni says that c₂ = 4 is always suitable, but this bound is pessimistic and a direct algorithm due to Belabas-Diaz-Friedman, improved by Grenié and Molteni, is used to check the condition, assuming GRH.

If the algorithm does not find enough relations, you may want to increase c₁ and c₂ to be larger than the so-called Bach constant displayed by setdebug("bnf",1), at the cost of increased memory usage and linear algebra time. It is quite possible to take c₂ > 4 but using an unconditional bound and dividing it by (log |d_K|)^2 is not a great idea: the complexity becomes exponential while the result remains conditional (we only know for sure that the true class group is a quotient of the computed one).

* nrpid is the maximal number of small norm relations attached to each ideal in the factor base. Set it to -1 to disable the search for small norm relations. Reasonable values are between 4 and 20. The default is 4 (which is also used if nrpid is zero). Increasing this value has seldom much effect, but setting it to -1 can have a large positive or negative effect on the running time.

* max_fact is the maximal number of trial factorizations to perform per ideal. There is an inherent trade-off between testing more ideals or testing more elements per ideals. The default is 500 (which is also used if max_fact is zero). If the algorithm does not find enough small norm relations, increase this value. Reasonable values are between 100 and 10000. When using parallelism (see below) it can be reasonable to increase it up to about 10⁶.

* idex is the power of the ideal to use. Reasonable values are between 1 and 12. The default is 0, which lets the algorithm picks a small power of the ideal depending on its norm.

* usethr decides whether to use parallelism when searching for relations. The possible values are 0: no parallelism (default), 1: use default(nbthreads) threads, and n > 1: use n threads. Parallelism requires to omit early-abort strategies when looking for relations which slows down the algorithm in easy cases. This setting does not affect the linear algebra part of the algorithm (which may use parallelism on its own).

A good strategy is to first try to change idex, then increase max_fact. If this is not sufficient, try to increase c₁ and c₂. If this causes the search to be too slow, try parallelism.

The components of a bnf are technical. 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 (𝔭_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 𝔭_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₁+r₂) x (r₁+r₂-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] 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, the number of roots of unity and a generator bnf.tu, the fundamental units in expanded form bnf.fu. If the fundamental units were omitted in the bnf, bnf.fu returns the sentinel value 0. If flag = 1, this vector contain also algebraic data corresponding to the fundamental units and to the discrete logarithm problem (see bnfisprincipal). In particular, if flag = 1 we may only know the units in factored form: the first call to bnf.fu expands them, which may be very costly, then caches the result.

bnf[9] is a 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], followed by technical exact components which allow to recompute g_a and GD_a to higher accuracy.

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).

The library syntax is GEN bnfinit0(GEN P, long flag, GEN tech = NULL, long prec).

Also available is GEN Buchall(GEN P, long flag, long prec), corresponding to tech = NULL, where flag is either 0 (default) or nf_FORCE (include all data in algebraic form). The function GEN Buchall_param(GEN P, double c1, double c2, long nrpid, long flag, long prec) gives direct access to the technical parameters.

Computes a complete system of solutions (modulo units of positive norm) of the absolute norm equation Norm(a) = b, where a is an integer in bnf. If bnf has not been certified, the correctness of the result depends on the validity of GRH. If (optional) flag is set, allows returning solutions in factored form, which helps a lot when the fundamental units are large (equivalently, when bnf.reg is large); having an exact algebraic bnf from bnfinit(,1) is necessary in this case, else setting the flag will mostly be a no-op.

  ? bnf = bnfinit(x^4-2, 1);
  ? bnfisintnorm(bnf,7)
  %2 = [-x^2 + x - 1, x^2 + x + 1]
  ? bnfisintnorm(bnf,-7)
  %3 = [-x^3 - 1, x^3 + 2*x^2 + 2*x + 1]
  
  ? bnf = bnfinit(x^2-2305843005992468481, 1); b = 2305843008139952128;
  ? bnf.reg \\ fundamental unit is huge
  %5 = 14054016.227457155120413774802385952043
  
  ? v = bnfisintnorm(bnf, b, 1); #v
  %7 = 31   \\ succeeds instantly
  ? s = v[1]; [type(s), matsize(s)]
  %8 = ["t_MAT", [162, 2]]   \\ solution 1 is a product of 162 factors
  ? exponent(s[,2])
  %9 = 22

The exponents have 22 bits, so there is little hope of writing down the solutions in expanded form. And indeed, bnfisintnorm(bnr,b) produces a stack overflow with 100GB parisize. Note that the number of solutions is well defined but the precise form of the result depends on the random seed: the factored form is highly non-unique.

See also bnfisnorm.

The library syntax is GEN bnfisintnorm0(GEN bnf, GEN b, long flag). The function GEN bnfisintnormabs0(GEN bnf, GEN a, long flag), where bnf is a true bnf structure, returns a complete system of solutions modulo units of the absolute norm equation |Norm(x) |= |a|. As fast as bnfisintnorm, but solves the two equations Norm(x) = ± a simultaneously. The functions GEN bnfisintnormabs(GEN bnf, GEN a), GEN bnfisintnorm(GEN bnf, GEN a) correspond to flag = 0.

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, you may set flag = 0 (in this case, x is a norm iff b = 1). If flag is nonzero 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 4log(disc(Bnf))², where Bnf is the Galois closure of bnf.

See also bnfisintnorm.

The library syntax is GEN bnfisnorm(GEN bnf, GEN x, long flag).

bnf being the number field data output by bnfinit, and x being an ideal, this function tests whether the ideal is principal or not. The result is more complete than a simple true/false answer and solves a general discrete logarithm problem. Assume the class group is ⨁ (ℤ/d_iℤ)g_i (where the generators g_i and their orders d_i are respectively given by bnf.gen and bnf.cyc). The routine returns a row vector [e,t], where e is a vector of exponents 0 ≤ e_i < d_i, and t is a number field element such that x = (t) ∏_i g_i^e_i. For given g_i (i.e. for a given bnf), the e_i are unique, and t is unique modulo units.

In particular, x is principal if and only if e is the zero vector. Note that the empty vector, which is returned when the class number is 1, is considered to be a zero vector (of dimension 0).

  ? K = bnfinit(y^2+23);
  ? K.cyc
  %2 = [3]
  ? K.gen
  %3 = [[2, 0; 0, 1]]          \\ a prime ideal above 2
  ? P = idealprimedec(K,3)[1]; \\ a prime ideal above 3
  ? v = bnfisprincipal(K, P)
  %5 = [[2]~, [3/4, 1/4]~]
  ? idealmul(K, v[2], idealfactorback(K, K.gen, v[1]))
  %6 =
  [3 0]
  
  [0 1]
  ? % == idealhnf(K, P)
  %7 = 1

The binary digits of flag mean:

* 1: If set, outputs [e,t] as explained above, otherwise returns only e, which is easier to compute. The following idiom only tests whether an ideal is principal:

    is_principal(bnf, x) = !bnfisprincipal(bnf,x,0);

* 2: It may not be possible to recover t, given the initial accuracy to which the bnf structure was computed. In that case, a warning is printed and t is set equal to the empty vector []~. If this bit is set, increase the precision and recompute needed quantities until t can be computed. Warning: setting this may induce lengthy computations, and the result may be too large to be physically representable in any case. You should consider using flag = 4 instead.

* 4: Return t in factored form (compact representation), as a small product of S-units for a small set of finite places S, possibly with huge exponents. This kind of result can be cheaply mapped to K^*/(K^*)^ℓ or to ℂ or ℚ_p to bounded accuracy and this is usually enough for applications. Explicitly expanding such a compact representation is possible using nffactorback but may be very costly. The algorithm is guaranteed to succeed if the bnf was computed using bnfinit(,1). If not, the algorithm may fail to compute a huge generator in this case (and replace it by []~). This is orders of magnitude faster than flag = 2 when the generators are indeed large.

The library syntax is GEN bnfisprincipal0(GEN bnf, GEN x, long flag). Instead of the above hardcoded numerical flags, one should rather use an or-ed combination of the symbolic flags nf_GEN (include generators, possibly a place holder if too difficult), nf_GENMAT (include generators in compact form) and nf_FORCE (insist on finding the generators, a no-op if nf_GENMAT is included).

This function is obsolete, use bnfisunit.

The library syntax is GEN bnfissunit(GEN bnf, GEN sfu, GEN 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₁,...,u_r are the fundamental units, and ζ is the generator of the group of roots of unity (bnf.tu), the output is a vector [x₁,...,x_r,x_r+1] such that x = u₁^x₁... u_r^x_r.ζ^x_r+1. The x_i are integers but the last one (i = r+1) is only defined modulo the order w of ζ and is guaranteed to be in [0,w[.

Note that bnf need not contain the fundamental units explicitly: it may contain the placeholder 0 instead:

  ? setrand(1); bnf = bnfinit(x^2-x-100000);
  ? bnf.fu
  %2 = 0
  ? u = [119836165644250789990462835950022871665178127611316131167, \
         379554884019013781006303254896369154068336082609238336]~;
  ? bnfisunit(bnf, u)
  %3 = [-1, 0]~

The given u is 1/u₁, where u₁ is the fundamental unit implicitly stored in bnf. In this case, u₁ was not computed and stored in algebraic form since the default accuracy was too low. Re-run the bnfinit command at \g1 or higher to see such diagnostics.

This function allows x to be given in factored form, but it then assumes that x is an actual unit. (Because it is general too costly to check whether this is the case.)

  ? { v = [2, 85; 5, -71; 13, -162; 17, -76; 23, -37; 29, -104; [224, 1]~, -66;
  [-86, 1]~, 86; [-241, 1]~, -20; [44, 1]~, 30; [124, 1]~, 11; [125, -1]~, -11;
  [-214, 1]~, 33; [-213, -1]~, -33; [189, 1]~, 74; [190, -1]~, 104;
  [-168, 1]~, 2; [-167, -1]~, -8]; }
  ? bnfisunit(bnf,v)
  %5 = [1, 0]~

Note that v is the fundamental unit of bnf given in compact (factored) form.

If the argument U is present, as output by bnfunits(bnf, S), then the function decomposes x on the S-units generators given in U[1].

   ? bnf = bnfinit(x^4 - x^3 + 4*x^2 + 3*x + 9, 1);
   ? bnf.sign
   %2 = [0, 2]
   ? S = idealprimedec(bnf,5); #S
   %3 = 2
   ? US = bnfunits(bnf,S);
   ? g = US[1]; #g  \\ #S = #g, four S-units generators, in factored form
   %5 = 4
   ? g[1]
   %6 = [[6, -3, -2, -2]~ 1]
   ? g[2]
   %7 =
   [[-1, 1/2, -1/2, -1/2]~ 1]
  
   [      [4, -2, -1, -1]~ 1]
   ? [nffactorback(bnf, x) | x <- g]
   %8 = [[6, -3, -2, -2]~, [-5, 5, 0, 0]~, [-1, 1, -1, 0]~,
         [1, -1, 0, 0]~]
  
   ? u = [10,-40,24,11]~;
   ? a = bnfisunit(bnf, u, US)
   %9 = [2, 0, 1, 4]~
   ? nffactorback(bnf, g, a) \\ prodi g[i]^a[i] still in factored form
   %10 =
   [[6, -3, -2, -2]~  2]
  
   [ [0, 0, -1, -1]~  1]
  
   [ [2, -1, -1, 0]~ -2]
  
   [   [1, 1, 0, 0]~  2]
  
   [  [-1, 1, 1, 1]~ -1]
  
   [  [1, -1, 0, 0]~  4]
  
   ? nffactorback(bnf,%)  \\ u = prodi g[i]^a[i]
   %11 = [10, -40, 24, 11]~

The library syntax is GEN bnfisunit0(GEN bnf, GEN x, GEN U = NULL). Also available is GEN bnfisunit(GEN bnf, GEN x) for U = NULL.

Let bnf be a bnf structure attached to the number field F and let l be a prime number, hereafter denoted ℓ for typographical reasons. One define the logarithmic ℓ-class group ~{Cl}_F of F, which is an infinite abelian group, and a logarithmic degree map with values in ℤ_ℓ.

The function bnflog computes the subgroup ~{Cl}⁰_F of classes of logarithmic degree 0 in ~{Cl}_F. This is a finite abelian group if F/ℚ is abelian and conjecturally finite for all number fields. The function returns if and only if the group is indeed finite (otherwise it would run into an infinite loop). Let S = { 𝔭₁,..., 𝔭_k} be the set of ℓ-adic places (maximal ideals containing ℓ). The function returns [D, G(ℓ), G'], where

* D is the vector of elementary divisors for ~{Cl}_F.

* G(ℓ) is the vector of elementary divisors for the (conjecturally finite) abelian group ~{Cl}(ℓ) = { 𝔞 = ∑_{i ≤ k} a_i 𝔭_i : deg_F 𝔞 = 0}, where the 𝔭_i are the ℓ-adic places of F; this is a subgroup of ~{Cl}.

* G' is the vector of elementary divisors for the ℓ-Sylow Cl' of the S-class group of F; the group ~{Cl} maps to Cl' with a simple co-kernel.

The library syntax is GEN bnflog(GEN bnf, GEN l).

Let nf be a nf structure attached to a number field F, and let l be a prime number (hereafter denoted ℓ). The ℓ-adified group of id\`{e}les of F quotiented by the group of logarithmic units is identified to the ℓ-group of logarithmic divisors ⨁ ℤ_ℓ [𝔭], generated by the maximal ideals of F.

The degree map deg_F is additive with values in ℤ_ℓ, defined by deg_F 𝔭 = ~{f}_𝔭 deg_ℓ p, where the integer ~{f}_𝔭 is as in bnflogef and deg_ℓ p is log_ℓ p for p != ℓ, log_ℓ (1 + ℓ) for p = ℓ != 2 and log_ℓ (1 + 2²) for p = ℓ = 2.

Let A = ∏ 𝔭^n_𝔭 be an ideal and let ~{A} = ∑ n_𝔭 [𝔭] be the attached logarithmic divisor. Return the exponential of the ℓ-adic logarithmic degree deg_F A, which is a natural number.

The library syntax is GEN bnflogdegree(GEN nf, GEN A, GEN l).

Let nf be a nf structure attached to a number field F and let pr be a prid structure attached to a maximal ideal 𝔭 / p. Return [~{e}(F_𝔭 / ℚ_p), ~{f}(F_𝔭 / ℚ_p)] the logarithmic ramification and residue degrees. Let ℚ_p^c/ℚ_p be the cyclotomic ℤ_p-extension, then ~{e} = [F_𝔭 : F_𝔭 ∩ ℚ_p^c] and ~{f} = [F_𝔭 ∩ ℚ_p^c : ℚ_p]. Note that ~{e}~{f} = e(𝔭/p) f(𝔭/p), where e(𝔭/p) and f(𝔭/p) denote the usual ramification and residue degrees.

  ? F = nfinit(y^6 - 3*y^5 + 5*y^3 - 3*y + 1);
  ? bnflogef(F, idealprimedec(F,2)[1])
  %2 = [6, 1]
  ? bnflogef(F, idealprimedec(F,5)[1])
  %3 = [1, 2]

The library syntax is GEN bnflogef(GEN nf, GEN pr).

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: 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 bnf need not contain fundamental units.

The library syntax is GEN bnfnarrow(GEN bnf).

bnf being as output by bnfinit, this computes an r₁ x (r₁+r₂-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 K.tu, K.fu */
  tpuexpo(K)=
  { my(M, S = bnfsignunit(K), [m,n] = matsize(S));
    \\ m = K.r1, n = r1+r2-1
    S = matrix(m,n, i,j, if (S[i,j] < 0, 1,0));
    S = concat(vectorv(m,i,1), S);   \\ add sign(-1)
    M = matkermod(S, 2);
    if (M, mathnfmodid(M, 2), 2*matid(n+1))
  }
  
  /* totally positive fundamental units of bnf K */
  tpu(K)=
  { my(ex = tpuexpo(K)[,^1]); \\ remove ex[,1], corresponds to 1 or -1
    my(v = concat(K.tu[2], K.fu));
    [ nffactorback(K, v, c) | c <- ex];
  }

The library syntax is GEN signunits(GEN bnf).

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 obsoleted component, now the empty vector.

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

v[5] gives the S-class group structure, in the usual abelian group format: a 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 GEN bnfsunit(GEN bnf, GEN S, long prec). Also available is GEN sunits_mod_units(GEN bnf, GEN S) which returns only v[1].

Return the fundamental units of the number field bnf output by bnfinit; if S is present and is a list of prime ideals, compute fundamental S-units instead. The first component of the result contains independent integral S-units generators: first nonunits, then r₁+r₂-1 fundamental units, then the torsion unit. The result may be used as an optional argument to bnfisunit. The units are given in compact form: no expensive computation is attempted if the bnf does not already contain units.

   ? bnf = bnfinit(x^4 - x^3 + 4*x^2 + 3*x + 9, 1);
   ? bnf.sign   \\ r1 + r2 - 1 = 1
   %2 = [0, 2]
   ? U = bnfunits(bnf); u = U[1];
   ? #u \\ r1 + r2 = 2 units
   %5 = 2;
   ? u[1] \\ fundamental unit as factorization matrix
   %6 =
   [[0, 0, -1, -1]~  1]
  
   [[2, -1, -1, 0]~ -2]
  
   [  [1, 1, 0, 0]~  2]
  
   [ [-1, 1, 1, 1]~ -1]
   ? u[2] \\ torsion unit as factorization matrix
   %7 =
   [[1, -1, 0, 0]~ 1]
   ? [nffactorback(bnf, z) | z <- u]  \\ same units in expanded form
   %8 = [[-1, 1, -1, 0]~, [1, -1, 0, 0]~]

Now an example involving S-units for a nontrivial S:

   ? S = idealprimedec(bnf,5); #S
   %9 = 2
   ? US = bnfunits(bnf, S); uS = US[1];
   ? g = [nffactorback(bnf, z) | z <- uS] \\ now 4 units
   %11 = [[6, -3, -2, -2]~, [-5, 5, 0, 0]~, [-1, 1, -1, 0]~, [1, -1, 0, 0]~]
   ? bnfisunit(bnf,[10,-40,24,11]~)
   %12 = []~  \\ not a unit
   ? e = bnfisunit(bnf, [10,-40,24,11]~, US)
   %13 = [2, 0, 1, 4]~  \\ ...but an S-unit
   ? nffactorback(bnf, g, e)
   %14 = [10, -40, 24, 11]~
   ? nffactorback(bnf, uS, e) \\ in factored form
   %15 =
   [[6, -3, -2, -2]~  2]
  
   [ [0, 0, -1, -1]~  1]
  
   [ [2, -1, -1, 0]~ -2]
  
   [   [1, 1, 0, 0]~  2]
  
   [  [-1, 1, 1, 1]~ -1]
  
   [  [1, -1, 0, 0]~  4]

Note that in more complicated cases, any nffactorback fully expanding an element in factored form could be very expensive. On the other hand, the final example expands a factorization whose components are themselves in factored form, hence the result is a factored form: this is a cheap operation.

The library syntax is GEN bnfunits(GEN bnf, GEN S = NULL).

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 GEN dirzetak(GEN nf, GEN b).

This function is obsolete, use nffactor.

factorization of the univariate polynomial x over the number field defined by the (univariate) polynomial t. x may have coefficients in ℚ or in the number field. The algorithm reduces to factorization over ℚ (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 se:priority). However if nonrational 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)
    ***   at top-level: factornf(x^2+Mod(z,z
    ***                 ^ —  —  —  —  —  — --
    *** factornf: inconsistent data in rnf function.
  ? factornf(x^2 + z, y^2+1)
    ***   at top-level: factornf(x^2+z,y^2+1
    ***                 ^ —  —  —  —  —  — --
    *** factornf: incorrect variable in rnf function.

The library syntax is GEN polfnf(GEN x, GEN t).

Sum of the two ideals x and y in the number field nf. The result is given in HNF.

   ? K = nfinit(x^2 + 1);
   ? a = idealadd(K, 2, x + 1)  \\ ideal generated by 2 and 1+I
   %2 =
   [2 1]
  
   [0 1]
   ? pr = idealprimedec(K, 5)[1];  \\ a prime ideal above 5
   ? idealadd(K, a, pr)     \\ coprime, as expected
   %4 =
   [1 0]
  
   [0 1]

This function cannot be used to add arbitrary ℤ-modules, since it assumes that its arguments are ideals:

    ? b = Mat([1,0]~);
    ? idealadd(K, b, b)     \\ only square t_MATs represent ideals
    *** idealadd: nonsquare t_MAT in idealtyp.
    ? c = [2, 0; 2, 0]; idealadd(K, c, c)   \\ nonsense
    %6 =
    [2 0]
  
    [0 2]
    ? d = [1, 0; 0, 2]; idealadd(K, d, d)   \\ nonsense
    %7 =
    [1 0]
  
    [0 1]
  

In the last two examples, we get wrong results since the matrices c and d do not correspond to an ideal: the ℤ-span of their columns (as usual interpreted as coordinates with respect to the integer basis K.zk) is not an ℤ_K-module. To add arbitrary ℤ-modules generated by the columns of matrices A and B, use mathnf(concat(A,B)).

The library syntax is GEN idealadd(GEN nf, GEN x, GEN 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 ∈ x, b ∈ 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 ℤ_K. This outputs a k-component vector e such that e[i] ∈ x[i] for 1 ≤ i ≤ k and ∑_{1 ≤ i ≤ k}e[i] = 1.

The library syntax is GEN idealaddtoone0(GEN nf, GEN x, GEN y = NULL).

If x is a fractional ideal (given in any form), gives an element α in nf such that for all prime ideals 𝔭 such that the valuation of x at 𝔭 is nonzero, we have v_𝔭(α) = v_𝔭(x), and v_𝔭(α) ≥ 0 for all other 𝔭.

The argument x may also be given as a prime ideal factorization, as output by idealfactor, but allowing zero exponents. This yields an element α such that for all prime ideals 𝔭 occurring in x, v_𝔭(α) = v_𝔭(x); for all other prime ideals, v_𝔭(α) ≥ 0.

flag is deprecated (ignored), kept for backward compatibility.

The library syntax is GEN idealappr0(GEN nf, GEN x, long flag). Use directly GEN idealappr(GEN nf, GEN x) since flag is ignored.

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

v_𝔭(b - y_𝔭) ≥ v_𝔭(x) for all prime ideals in x and v_𝔭(b) ≥ 0 for all other 𝔭.

  ? K = nfinit(t^2-2);
  ? x = idealfactor(K, 2^2*3)
  %2 =
  [[2, [0, 1]~, 2, 1, [0, 2; 1, 0]] 4]
  
  [           [3, [3, 0]~, 1, 2, 1] 1]
  ? y = [t,1];
  ? idealchinese(K, x, y)
  %4 = [4, -3]~

The argument x may also be of the form [x, s] where the first component is as above and s is a vector of signs, with r₁ components s_i in {-1,0,1}: if σ_i denotes the i-th real embedding of the number field, the element b returned satisfies further sign(σ_i(b)) = s_i for all i such that s_i = ±1. In other words, the sign is fixed to s_i at the i-th embedding whenever s_i is nonzero.

  ? idealchinese(K, [x, [1,1]], y)
  %5 = [16, -3]~
  ? idealchinese(K, [x, [-1,-1]], y)
  %6 = [-20, -3]~
  ? idealchinese(K, [x, [1,-1]], y)
  %7 = [4, -3]~

If y is omitted, return a data structure which can be used in place of x in later calls and allows to solve many chinese remainder problems for a given x more efficiently. In this case, the right hand side y is not allowed to have denominators, unless they are coprime to x.

  ? C = idealchinese(K, [x, [1,1]]);
  ? idealchinese(K, C, y) \\ as above
  %9 = [16, -3]~
  ? for(i=1,10^4, idealchinese(K,C,y))  \\ ... but faster !
  time = 80 ms.
  ? for(i=1,10^4, idealchinese(K,[x,[1,1]],y))
  time = 224 ms.

Finally, this structure is itself allowed in place of x, the new s overriding the one already present in the structure. This allows to initialize for different sign conditions more efficiently when the underlying ideal factorization remains the same.

  ? D = idealchinese(K, [C, [1,-1]]);   \\ replaces [1,1]
  ? idealchinese(K, D, y)
  %13 = [4, -3]~
  ? for(i=1,10^4,idealchinese(K,[C,[1,-1]]))
  time = 40 ms.   \\ faster than starting from scratch
  ? for(i=1,10^4,idealchinese(K,[x,[1,-1]]))
  time = 128 ms.

The library syntax is GEN idealchinese(GEN nf, GEN x, GEN y = NULL). Also available is GEN idealchineseinit(GEN nf, GEN x) when y = NULL.

Given two integral ideals x and y in the number field nf, returns a β in the field, such that β.x is an integral ideal coprime to y. In fact, β is also guaranteed to be integral outside primes dividing y.

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

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 nonzero, 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. More precisely, the algorithm cheaply removes all maximal ideals above rational primes such that v_p(Nx) = v_p(Ny).

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

Let nf be a number field as output by nfinit, and x a fractional ideal. This function returns the nonnegative rational generator of x ∩ ℚ. If x is an extended ideal, the extended part is ignored.

  ? nf = nfinit(y^2+1);
  ? idealdown(nf, -1/2)
  %2 = 1/2
  ? idealdown(nf, (y+1)/3)
  %3 = 2/3
  ? idealdown(nf, [2, 11]~)
  %4 = 125
  ? x = idealprimedec(nf, 2)[1]; idealdown(nf, x)
  %5 = 2
  ? idealdown(nf, [130, 94; 0, 2])
  %6 = 130

The library syntax is GEN idealdown(GEN nf, GEN 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. If lim is set, return partial factorization, including only prime ideals above rational primes < lim.

  ? nf = nfinit(x^3-2);
  ? idealfactor(nf, x) \\ a prime ideal above 2
  %2 =
  [[2, [0, 1, 0]~, 3, 1, ...] 1]
  
  ? A = idealhnf(nf, 6*x, 4+2*x+x^2)
  %3 =
  [6 0 4]
  
  [0 6 2]
  
  [0 0 1]
  
  ? idealfactor(nf, A)
  %4 =
   [[2, [0, 1, 0]~, 3, 1, ...] 2]
  
   [[3, [1, 1, 0]~, 3, 1, ...] 2]
  
  ? idealfactor(nf, A, 3) \\ restrict to primes above p < 3
  %5 =
  [[2, [0, 1, 0]~, 3, 1, ...] 2]

The library syntax is GEN gpidealfactor(GEN nf, GEN x, GEN lim = NULL). This function should only be used by the gp interface. Use directly GEN idealfactor(GEN nf, GEN x) or GEN idealfactor_limit(GEN nf, GEN x, ulong lim).

Gives back the ideal corresponding to a factorization. The integer 1 corresponds to the empty factorization. If e is present, e and f must be vectors of the same length (e being integral), and the corresponding factorization is the product of the f[i]^e[i].

If not, and f is vector, it is understood as in the preceding case with e a vector of 1s: we return the product of the f[i]. Finally, f can be a regular factorization, as produced by idealfactor.

  ? nf = nfinit(y^2+1); idealfactor(nf, 4 + 2*y)
  %1 =
  [  [2, [1, 1]~, 2, 1, [1, -1; 1, 1]] 2]
  
  [[5, [2, 1]~, 1, 1, [-2, -1; 1, -2]] 1]
  
  ? idealfactorback(nf, %)
  %2 =
  [10 4]
  
  [0  2]
  
  ? f = %1[,1]; e = %1[,2]; idealfactorback(nf, f, e)
  %3 =
  [10 4]
  
  [0  2]
  
  ? % == idealhnf(nf, 4 + 2*y)
  %4 = 1

If flag is nonzero, performs ideal reductions (idealred) along the way. This is most useful if the ideals involved are all extended ideals (for instance with trivial principal part), so that the principal parts extracted by idealred are not lost. Here is an example:

  ? f = vector(#f, i, [f[i], [;]]);  \\ transforms to extended ideals
  ? idealfactorback(nf, f, e, 1)
  %6 = [[1, 0; 0, 1], [2, 1; [-2, 1]~, -1; 5, 1]]
  ? nffactorback(nf, %[2])
  %7 = [-4, -2]~

The extended ideal returned in %6 is the trivial ideal 1, extended with a principal generator given in factored form. We use nffactorback to recover it in standard form.

The library syntax is GEN idealfactorback(GEN nf, GEN f, GEN e = NULL, long flag ).

Let K be the number field defined by nf and assume K/ℚ be a Galois extension with Galois group given gal = galoisinit(nf), and that pr is an unramified prime ideal 𝔭 in prid format. This function returns a permutation of gal.group which defines the Frobenius element Frob_𝔭 attached to 𝔭. If p is the unique prime number in 𝔭, then Frob(x) = x^p mod 𝔭 for all x ∈ ℤ_K.

  ? nf = nfinit(polcyclo(31));
  ? gal = galoisinit(nf);
  ? pr = idealprimedec(nf,101)[1];
  ? g = idealfrobenius(nf,gal,pr);
  ? galoispermtopol(gal,g)
  %5 = x^8

This is correct since 101 = 8 mod 31.

The library syntax is GEN idealfrobenius(GEN nf, GEN gal, GEN pr).

Gives the Hermite normal form of the (fractional) ideal of the number field nf generated as ℤ_K module by the components of the vector v, which must belong to nf. If v is a matrix, the components are the columns seen as elements expressed over the integral basis of nf. For ideals generated by one or two elements, idealhnf is an alternative.

The library syntax is GEN idealfromgens(GEN nf, GEN v).

Gives the Hermite normal form of the ideal uℤ_K+vℤ_K, where u and v are elements of the number field K defined by nf.

  ? nf = nfinit(y^3 - 2);
  ? idealhnf(nf, 2, y+1)
  %2 =
  [1 0 0]
  
  [0 1 0]
  
  [0 0 1]
  ? idealhnf(nf, y/2, [0,0,1/3]~)
  %3 =
  [1/3 0 0]
  
  [0 1/6 0]
  
  [0 0 1/6]

If v is omitted, returns the HNF of the ideal defined by u: u may be an algebraic number (defining a principal ideal), a maximal ideal (as given by idealprimedec or idealfactor) or an ideal in HNF (not very useful, but idempotent).

  ? idealhnf(nf, idealprimedec(nf,2)[1])
  %4 =
  [2 0 0]
  
  [0 1 0]
  
  [0 0 1]
  ? idealhnf(nf, %)  \\ already in HNF
  %5 =
  [2 0 0]
  
  [0 1 0]
  
  [0 0 1]

Another deprecated format, generalizing the last one, allows u to be a matrix whose columns give generators for the ideal. This format is awkward and error-prone, please use idealfromgens instead; for completeness, we still describe it but it will disappear in future versions:

* if strictly less than N = [K:ℚ] columns are present, u is the ℤ_K-module they generate,

* unfortunately, if N or more are given, it is assumed that they form a ℤ-basis of the ideal, in particular that the matrix has maximal rank N. This acts as mathnf since the ℤ_K-module structure is (taken for granted hence) not taken into account in this case.

The function idealfromgens does not have this limitation: it always returns the ℤ_K-module generated by any number of elements of K, without any assumption.

Finally, when K is quadratic with discriminant D_K, we allow u = Qfb(a,b,c), provided b² - 4ac = D_K. As usual, this represents the ideal a ℤ + (1/2)(-b + sqrt{D_K}) ℤ.

  ? K = nfinit(x^2 - 60); K.disc
  %1 = 60
  ? idealhnf(K, qfbprimeform(60,2))
  %2 =
  [2 1]
  
  [0 1]
  ? idealhnf(K, Qfb(1,2,3))
    ***   at top-level: idealhnf(K,Qfb(1,2,3
    ***                 ^ —  —  —  —  —  — --
    *** idealhnf: Qfb(1, 2, 3) has discriminant != 60 in idealhnf.

The library syntax is GEN idealhnf0(GEN nf, GEN u, GEN v = NULL). Also available is GEN idealhnf(GEN nf, GEN a), where nf is a true nf structure.

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 ℤ-modules, e.g. orders, since its arguments are replaced by the ideals they generate. The following script intersects ℤ-modules A and B given by matrices of compatible dimensions with integer coefficients:

  ZM_intersect(A,B) =
  { my(Ker = matkerint(concat(A,B)));
    mathnf( A * Ker[1..#A,] )
  }

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

Inverse of the ideal x in the number field nf, given in HNF. If x is an extended ideal, its principal part is suitably updated: i.e. inverting [I,t], yields [I^-1, 1/t].

The library syntax is GEN idealinv(GEN nf, GEN x).

Given nf a number field as output by nfinit and an ideal x, return 0 if x is not a maximal ideal. Otherwise return a prid structure nf attached to the ideal. This function uses ispseudoprime and may return a wrong result in case the underlying rational pseudoprime is not an actual prime number: apply isprime(pr.p) to guarantee correctness. If x is an extended ideal, the extended part is ignored.

  ? K = nfinit(y^2 + 1);
  ? idealismaximal(K, 3) \\ 3 is inert
  %2 = [3, [3, 0]~, 1, 2, 1]
  ? idealismaximal(K, 5) \\ 5 is not
  %3 = 0
  ? pr = idealprimedec(K,5)[1] \\ already a prid
  %4 = [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]]
  ? idealismaximal(K, pr) \\ trivial check
  %5 = [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]]
  ? x = idealhnf(K, pr)
  %6 =
  [5 3]
  
  [0 1]
  ? idealismaximal(K, x) \\ converts from matrix form to prid
  %7 = [5, [-2, 1]~, 1, 1, [2, -1; 1, 2]]

This function is noticeably faster than idealfactor since it never involves an actually factorization, in particular when x ∩ ℤ is not a prime number.

The library syntax is GEN idealismaximal(GEN nf, GEN x).

Let nf be a number field and n > 0 be a positive integer. Return 1 if the fractional ideal A = Bⁿ is an n-th power and 0 otherwise. If the argument B is present, set it to the n-th root of A, in HNF.

  ? K = nfinit(x^3 - 2);
  ? A = [46875, 30966, 9573; 0, 3, 0; 0, 0, 3];
  ? idealispower(K, A, 3, &B)
  %3 = 1
  ? B
  %4 =
  [75 22 41]
  
  [ 0  1  0]
  
  [ 0  0  1]
  
  ? A = [9375, 2841, 198; 0, 3, 0; 0, 0, 3];
  ? idealispower(K, A, 3)
  %5 = 0

The library syntax is long idealispower(GEN nf, GEN A, long n, GEN *B = NULL).

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. The information is inferred from local data and Chinese remainders and less expensive than computing than a direct global computation.

The binary digits of flag mean:

* 1: if the ideals are given by a bid, include generators; otherwise don't.

* 2: if this bit is set, nf must be a bnf with units. Each component is of the form [bid,U], where bid is attached to an ideal f and U is a vector of discrete logarithms of the units in (ℤ_K/f)^*. More precisely, U gives the ideallogs with respect to bid of (ζ,u₁,...,u_r) where ζ is the torsion unit generator bnf.tu[2] and (u_i) are the fundamental units in bnf.fu. This structure is technical, meant to be used in conjunction with bnrclassnolist or bnrdisclist.

* 4: give only the ideal (in HNF), else a bid.

* 8: omit ideals which cannot be conductors, i.e. divisible exactly by a prime ideal of norm 2.

  ? 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 65 in ℤ[i]

If one wants more information:

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

where we ask for the structures of the (ℤ[i]/f)^* 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.

Finally, one can input a negative bound. The function then returns the ideals of norm |bound|, given by their factorization matrix. The only valid value of flag is then the default. If needed, one can obtain their HNF using idealfactorback, and the corresponding bid structures using idealstar (which accepts ideals in factored form).

The library syntax is GEN gideallist(GEN nf, GEN bound, long flag). Also available is GEN ideallist0(GEN nf,long bound, long flag) for a non-negative bound.

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 ℤ/2ℤ to (ℤ_K/f)^*. 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];
  %4 = [2, 12, 2]

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

nf is a number field, bid is as output by idealstar(nf, D,...) and x an element of nf which must have valuation equal to 0 at all prime ideals in the support of D and need not be integral. This function computes the discrete logarithm of x on the generators given in bid.gen. 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 = ∏_i g_i^x_i (mod ^*D) . Note that when the support of D contains places at infinity, this congruence implies also sign conditions on the attached real embeddings. See znlog for the limitations of the underlying discrete log algorithms.

When nf is omitted, take it to be the rational number field. In that case, x must be a t_INT and bid must have been initialized by znstar(N,1).

The library syntax is GEN ideallog(GEN nf = NULL, GEN x, GEN bid). Also available are GEN Zideallog(GEN bid, GEN x) when nf is NULL, and GEN ideallogmod(GEN nf, GEN x, GEN bid, GEN mod) that returns the discrete logarithm of x modulo the t_INT mod; the value mod = NULL is treated as 0 (full discrete logarithm), but nf = NULL is not implemented with nonzero mod.

This function is useless and kept for backward compatibility only, use idealred. Computes a pseudo-minimum of the ideal x in the direction vdir in the number field nf.

The library syntax is GEN idealmin(GEN nf, GEN ix, GEN vdir = NULL).

Ideal multiplication of the ideals x and y in the number field nf; the result is the ideal product in HNF. If either x or y are extended ideals, their principal part is suitably updated: i.e. multiplying [I,t], [J,u] yields [IJ, tu]; multiplying I and [J, u] yields [IJ, u].

  ? nf = nfinit(x^2 + 1);
  ? idealmul(nf, 2, x+1)
  %2 =
  [4 2]
  
  [0 2]
  ? idealmul(nf, [2, x], x+1)        \\ extended ideal * ideal
  %3 = [[4, 2; 0, 2], x]
  ? idealmul(nf, [2, x], [x+1, x])   \\ two extended ideals
  %4 = [[4, 2; 0, 2], [-1, 0]~]

If flag is nonzero, reduce the result using idealred.

The library syntax is GEN idealmul0(GEN nf, GEN x, GEN y, long flag).

See also GEN idealmul(GEN nf, GEN x, GEN y) (flag = 0) and GEN idealmulred(GEN nf, GEN x, GEN y) (flag != 0).

Computes the norm of the ideal x in the number field nf.

The library syntax is GEN idealnorm(GEN nf, GEN x).

Returns [A,B], where A,B are coprime integer ideals such that x = A/B, in the number field nf.

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

The library syntax is GEN idealnumden(GEN nf, GEN x).

Computes the k-th power of the ideal x in the number field nf; k ∈ ℤ. If x is an extended ideal, its principal part is suitably updated: i.e. raising [I,t] to the k-th power, yields [I^k, t^k].

If flag is nonzero, reduce the result using idealred, throughout the (binary) powering process; in particular, this is not the same as idealpow(nf,x,k) followed by reduction.

The library syntax is GEN idealpow0(GEN nf, GEN x, GEN k, long flag).

See also GEN idealpow(GEN nf, GEN x, GEN k) and GEN idealpows(GEN nf, GEN x, long k) (flag = 0). Corresponding to flag = 1 is GEN idealpowred(GEN nf, GEN vp, GEN k).

Computes the prime ideal decomposition of the (positive) prime number p in the number field K represented by nf. If a nonprime p is given the result is undefined. If f is present and nonzero, restrict the result to primes of residue degree ≤ f.

The result is a vector of prid structures, each representing one of the prime ideals above p in the number field nf. The representation pr = [p,a,e,f,mb] of a prime ideal means the following: a is an algebraic integer in the maximal order ℤ_K and the prime ideal is equal to 𝔭 = pℤ_K + aℤ_K; e is the ramification index; f is the residual index; finally, mb is the multiplication table attached to an algebraic integer b such that 𝔭^-1 = ℤ_K+ b/ pℤ_K, which is used internally to compute valuations. In other words if p is inert, then mb is the integer 1, and otherwise it is a square t_MAT whose j-th column is b.nf.zk[j].

The algebraic number a is guaranteed to have a valuation equal to 1 at the prime ideal (this is automatic if e > 1).

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

  ? K = nfinit(x^3-2);
  ? P = idealprimedec(K, 5);
  ? #P       \\ 2 primes above 5 in Q(2^(1/3))
  %3 = 2
  ? [p1,p2] = P;
  ? [p1.e, p1.f]    \\ the first is unramified of degree 1
  %5 = [1, 1]
  ? [p2.e, p2.f]    \\ the second is unramified of degree 2
  %6 = [1, 2]
  ? p1.gen
  %7 = [5, [2, 1, 0]~]
  ? nfbasistoalg(K, %[2])  \\ a uniformizer for p1
  %8 = Mod(x + 2, x^3 - 2)
  ? #idealprimedec(K, 5, 1) \\ restrict to f = 1
  %9 = 1            \\ now only p1

The library syntax is GEN idealprimedec_limitf(GEN nf, GEN p, long f).

Given a prime ideal in idealprimedec format, returns the multiplicative group (1 + pr) / (1 + pr^k) as an abelian group. This function is much faster than idealstar when the norm of pr is large, since it avoids (useless) work in the multiplicative group of the residue field.

  ? K = nfinit(y^2+1);
  ? P = idealprimedec(K,2)[1];
  ? G = idealprincipalunits(K, P, 20);
  ? G.cyc
  %4 = [512, 256, 4]   \\ Z/512 x Z/256 x Z/4
  ? G.gen
  %5 = [[-1, -2]~, 1021, [0, -1]~] \\ minimal generators of given order

The library syntax is GEN idealprincipalunits(GEN nf, GEN pr, long k).

Let K be the number field defined by nf and assume that K/ℚ is Galois with Galois group G given by gal = galoisinit(nf). Let pr be the prime ideal 𝔓 in prid format. This function returns a vector g of subgroups of gal as follows:

* g[1] is the decomposition group of 𝔓,

* g[2] is G₀(𝔓), the inertia group of 𝔓,

and for i ≥ 2,

* g[i] is G_i-2(𝔓), the i-2-th ramification group of 𝔓.

The length of g is the number of nontrivial groups in the sequence, thus is 0 if e = 1 and f = 1, and 1 if f > 1 and e = 1. The following function computes the cardinality of a subgroup of G, as given by the components of g:

  card(H) =my(o=H[2]); prod(i=1,#o,o[i]);

  ? nf=nfinit(x^6+3); gal=galoisinit(nf); pr=idealprimedec(nf,3)[1];
  ? g = idealramgroups(nf, gal, pr);
  ? apply(card,g)
  %3 = [6, 6, 3, 3, 3] \\ cardinalities of the Gi

  ? nf=nfinit(x^6+108); gal=galoisinit(nf); pr=idealprimedec(nf,2)[1];
  ? iso=idealramgroups(nf,gal,pr)[2]
  %5 = [[Vecsmall([2, 3, 1, 5, 6, 4])], Vecsmall([3])]
  ? nfdisc(galoisfixedfield(gal,iso,1))
  %6 = -3

The field fixed by the inertia group of 2 is not ramified at 2.

The library syntax is GEN idealramgroups(GEN nf, GEN gal, GEN pr).

LLL reduction of the ideal I in the number field K attached to nf, along the direction v. The v parameter is best left omitted, but if it is present, it must be an nf.r1 + nf.r2-component vector of nonnegative integers. (What counts is the relative magnitude of the entries: if all entries are equal, the effect is the same as if the vector had been omitted.)

This function finds an a ∈ K^* such that J = (a)I is "small" and integral (see the end for technical details). The result is the Hermite normal form of the "reduced" ideal J.

  ? K = nfinit(y^2+1);
  ? P = idealprimedec(K,5)[1];
  ? idealred(K, P)
  %3 =
  [1 0]
  
  [0 1]

More often than not, a principal ideal yields the unit ideal as above. This is a quick and dirty way to check if ideals are principal, but it is not a necessary condition: a nontrivial result does not prove that the ideal is nonprincipal. For guaranteed results, see bnfisprincipal, which requires the computation of a full bnf structure.

If the input is an extended ideal [I,s], the output is [J, sa]; in this way, one keeps track of the principal ideal part:

  ? idealred(K, [P, 1])
  %5 = [[1, 0; 0, 1], [2, -1]~]

meaning that P is generated by [2, -1] . The number field element in the extended part is an algebraic number in any form or a factorization matrix (in terms of number field elements, not ideals!). In the latter case, elements stay in factored form, which is a convenient way to avoid coefficient explosion; see also idealpow.

Technical note. The routine computes an LLL-reduced basis for the lattice I^-1 equipped with the quadratic form || x ||_v² = ∑_{i = 1}^r₁+r₂ 2^v_iϵ_i|σ_i(x)|², where as usual the σ_i are the (real and) complex embeddings and ϵ_i = 1, resp. 2, for a real, resp. complex place. The element a is simply the first vector in the LLL basis. The only reason you may want to try to change some directions and set some v_i != 0 is to randomize the elements found for a fixed ideal, which is heuristically useful in index calculus algorithms like bnfinit and bnfisprincipal.

Even more technical note. In fact, the above is a white lie. We do not use ||.||_v exactly but a rescaled rounded variant which gets us faster and simpler LLLs. There's no harm since we are not using any theoretical property of a after all, except that it belongs to I^-1 and that a I is "expected to be small".

The library syntax is GEN idealred0(GEN nf, GEN I, GEN v = NULL).

Let nf be a number field, x an ideal in nf and n > 0 be a positive integer. Return a number field element b such that x bⁿ = v is small. If x is integral, then v is also integral.

More precisely, idealnumden reduces the problem to x integral. Then, factoring out the prime ideals dividing a rational prime p ≤ B, we rewrite x = I Jⁿ where the ideals I and J are both integral and I is B-smooth. Then we return a small element b in J^-1.

The bound B avoids a costly complete factorization of x; as soon as the n-core of x is B-smooth (i.e., as soon as I is n-power free), then J is as large as possible and so is the expected reduction.

  ? T = x^6+108; nf = nfinit(T); a = Mod(x,T);
  ? setrand(1); u = (2*a^2+a+3)*random(2^1000*x^6)^6;
  ? sizebyte(u)
  %3 = 4864
  ? b = idealredmodpower(nf,u,2);
  ? v2 = nfeltmul(nf,u, nfeltpow(nf,b,2))
  %5 = [34, 47, 15, 35, 9, 3]~
  ? b = idealredmodpower(nf,u,6);
  ? v6 = nfeltmul(nf,u, nfeltpow(nf,b,6))
  %7 = [3, 0, 2, 6, -7, 1]~

The last element v6, obtained by reducing modulo 6-th powers instead of squares, looks smaller than v2 but its norm is actually a little larger:

  ? idealnorm(nf,v2)
  %8 = 81309
  ? idealnorm(nf,v6)
  %9 = 731781

The library syntax is GEN idealredmodpower(GEN nf, GEN x, ulong n, ulong B).

Outputs a bid structure, necessary for computing in the finite abelian group G = (ℤ_K/N)^*. Here, nf is a number field and N 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₁ 0 or 1. Ideals can also be given by a factorization into prime ideals, as produced by idealfactor.

If the positive integer cycmod is present, only compute the group modulo cycmod-th powers, which may save a lot of time when some maximal ideals in the modulus have a huge residue field. Whereas you might only be interested in quadratic or cubic residuosity; see also bnrinit for applications in class field theory.

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: they are well defined but not explicitly computed, which saves time.

If flag = 2, as flag = 1, but including generators.

If flag = 0, only outputs (ℤ_K/N)^* 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.

If nf is omitted, we take it to be the rational number fields, N must be an integer and we return the structure of (ℤ/Nℤ)^*. In other words idealstar(, N, flag) is short for

    idealstar(nfinit(x), N, flag)

but faster. The alternative syntax znstar(N, flag) is also available for an analogous effect but, due to an unfortunate historical oversight, the default value of flag is different in the two functions (znstar does not initialize by default, you probably want znstar(N,1)).

The library syntax is GEN idealstarmod(GEN nf = NULL, GEN N, long flag, GEN cycmod = NULL). Instead the above hardcoded numerical flags, one should rather use GEN Idealstarmod(GEN nf, GEN ideal, long flag, GEN cycmod) or GEN Idealstar(GEN nf, GEN ideal, long flag) (cycmod is NULL), where flag is an or-ed combination of nf_GEN (include generators) and nf_INIT (return a full bid, not a group), possibly 0. This offers one more combination: gen, but no init. The nf argument must be a true nf structure.

Computes a two-element representation of the ideal x in the number field nf, combining a random search and an approximation theorem; x is an ideal in any form (possibly an extended ideal, whose principal part is ignored)

* When called as idealtwoelt(nf,x), the result is a row vector [a,α] with two components such that x = aℤ_K+αℤ_K and a is chosen to be the positive generator of x∩ℤ, unless x was given as a principal ideal in which case we may choose a = 0. The algorithm uses a fast lazy factorization of x∩ ℤ and runs in randomized polynomial time.

  ? K = nfinit(t^5-23);
  ? x = idealhnf(K, t^2*(t+1), t^3*(t+1))
  %2 =  \\ some random ideal of norm 552*23
  [552 23 23 529 23]
  
  [  0 23  0   0  0]
  
  [  0  0  1   0  0]
  
  [  0  0  0   1  0]
  
  [  0  0  0   0  1]
  
  ? [a,alpha] = idealtwoelt(K, x)
  %3 = [552, [23, 0, 1, 0, 0]~]
  ? nfbasistoalg(K, alpha)
  %4 = Mod(t^2 + 23, t^5 - 23)

* When called as idealtwoelt(nf,x,a) with an explicit nonzero a supplied as third argument, the function assumes that a ∈ x and returns α ∈ x such that x = aℤ_K + αℤ_K. Note that we must factor a in this case, and the algorithm is generally slower than the default variant and gives larger generators:

  ? alpha2 = idealtwoelt(K, x, 552)
  %5 = [-161, -161, -183, -207, 0]~
  ? idealhnf(K, 552, alpha2) == x
  %6 = 1

Note that, in both cases, the return value is not recognized as an ideal by GP functions; one must use idealhnf as above to recover a valid ideal structure from the two-element representation.

The library syntax is GEN idealtwoelt0(GEN nf, GEN x, GEN a = NULL). Also available are GEN idealtwoelt(GEN nf, GEN x) and GEN idealtwoelt2(GEN nf, GEN x, GEN a).

Gives the valuation of the ideal x at the prime ideal pr in the number field nf, where pr is in idealprimedec format. The valuation of the 0 ideal is +oo.

The library syntax is GEN gpidealval(GEN nf, GEN x, GEN pr). Also available is long idealval(GEN nf, GEN x, GEN pr), which returns LONG_MAX if x = 0 and the valuation as a long integer.

This function is deprecated, use apply.

nf being a number field in nfinit format, and x a (row or column) vector or matrix, apply nfalgtobasis to each entry of x.

The library syntax is GEN matalgtobasis(GEN nf, GEN x).

This function is deprecated, use apply.

nf being a number field in nfinit format, and x a (row or column) vector or matrix, apply nfbasistoalg to each entry of x.

The library syntax is GEN matbasistoalg(GEN nf, GEN x).

Let z = Mod(A, T) be a polmod, and Q be its minimal polynomial, which must satisfy deg(Q) = deg(T). Returns a "reverse polmod" Mod(B, Q), which is a root of T.

This is quite useful when one changes the generating element in algebraic extensions:

  ? u = Mod(x, x^3 - x -1); v = u^5;
  ? w = modreverse(v)
  %2 = Mod(x^2 - 4*x + 1, x^3 - 5*x^2 + 4*x - 1)

which means that x³ - 5x² + 4x -1 is another defining polynomial for the cubic field ℚ(u) = ℚ[x]/(x³ - x - 1) = ℚ[x]/(x³ - 5x² + 4x - 1) = ℚ(v), and that u → v² - 4v + 1 gives an explicit isomorphism. From this, it is easy to convert elements between the A(u) ∈ ℚ(u) and B(v) ∈ ℚ(v) representations:

  ? A = u^2 + 2*u + 3; subst(lift(A), 'x, w)
  %3 = Mod(x^2 - 3*x + 3, x^3 - 5*x^2 + 4*x - 1)
  ? B = v^2 + v + 1;   subst(lift(B), 'x, v)
  %4 = Mod(26*x^2 + 31*x + 26, x^3 - x - 1)

If the minimal polynomial of z has lower degree than expected, the routine fails

  ? u = Mod(-x^3 + 9*x, x^4 - 10*x^2 + 1)
  ? modreverse(u)
   *** modreverse: domain error in modreverse: deg(minpoly(z)) < 4
   ***   Break loop: type 'break' to go back to GP prompt
  break> Vec( dbg_err() ) \\ ask for more info
  ["e_DOMAIN", "modreverse", "deg(minpoly(z))", "<", 4,
    Mod(-x^3 + 9*x, x^4 - 10*x^2 + 1)]
  break> minpoly(u)
  x^2 - 8

The library syntax is GEN modreverse(GEN z).

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 +oo.

The library syntax is GEN newtonpoly(GEN x, GEN p).

Given an algebraic number x in the number field nf, transforms it to a column vector on the integral basis nf.zk.

  ? nf = nfinit(y^2 + 4);
  ? nf.zk
  %2 = [1, 1/2*y]
  ? nfalgtobasis(nf, [1,1]~)
  %3 = [1, 1]~
  ? nfalgtobasis(nf, y)
  %4 = [0, 2]~
  ? nfalgtobasis(nf, Mod(y, y^2+4))
  %5 = [0, 2]~

This is the inverse function of nfbasistoalg.

The library syntax is GEN algtobasis(GEN nf, GEN x).

Let T(X) be an irreducible polynomial with integral coefficients. This function returns an integral basis of the number field defined by T, that is a ℤ-basis of its maximal order. If present, dK is set to the discriminant of the returned order. The basis elements are given as elements in K = ℚ[X]/(T), in Hermite normal form with respect to the ℚ-basis (1,X,...,X^{deg T-1}) of K, lifted to ℚ[X]. In particular its first element is always 1 and its i-th element is a polynomial of degree i-1 whose leading coefficient is the inverse of an integer: the product of those integers is the index of ℤ[X]/(T) in the maximal order ℤ_K:

  ? nfbasis(x^2 + 4) \\ Z[X]/(T) has index 2 in ZK
  %1 = [1, x/2]
  ? nfbasis(x^2 + 4, &D)
  %2 = [1, x/2]
  ? D
  %3 = -4

This function uses a modified version of the round 4 algorithm, due to David Ford, Sebastian Pauli and Xavier Roblot.

Local basis, orders maximal at certain primes.

Obtaining the maximal order is hard: it requires factoring the discriminant D of T. Obtaining an order which is maximal at a finite explicit set of primes is easy, but it may then be a strict suborder of the maximal order. To specify that we are interested in a given set of places only, we can replace the argument T by an argument [T,listP], where listP encodes the primes we are interested in: it must be a factorization matrix, a vector of integers or a single integer.

* Vector: we assume that it contains distinct prime numbers.

* Matrix: we assume that it is a two-column matrix of a (partial) factorization of D; namely the first column contains distinct primes and the second one the valuation of D at each of these primes.

* Integer B: this is replaced by the vector of primes up to B. Note that the function will use at least O(B) time: a small value, about 10⁵, should be enough for most applications. Values larger than 2³² are not supported.

In all these cases, the primes may or may not divide the discriminant D of T. The function then returns a ℤ-basis of an order whose index is not divisible by any of these prime numbers. The result may actually be a global integral basis, in particular if all the prime divisors of the field discriminant are included, but this is not guaranteed! Note that nfinit has built-in support for such a check:

  ? K = nfinit([T, listP]);
  ? nfcertify(K)   \\ we computed an actual maximal order
  %2 = [];

The first line initializes a number field structure incorporating nfbasis([T, listP] in place of a proven integral basis. The second line certifies that the resulting structure is correct. This allows to create an nf structure attached to the number field K = ℚ[X]/(T), when the discriminant of T cannot be factored completely, whereas the prime divisors of disc K are known. If present, the argument dK is set to the discriminant of the returned order, and is equal to the field discriminant if and only if the order is maximal.

Of course, if listP contains a single prime number p, the function returns a local integral basis for ℤ_p[X]/(T):

  ? nfbasis(x^2+x-1001)
  %1 = [1, 1/3*x - 1/3]
  ? nfbasis( [x^2+x-1001, [2]] )
  %2 = [1, x]

The following function computes the index i_T of ℤ[X]/(T) in the order generated by the ℤ-basis B:

  nfbasisindex(T, B) = vecprod([denominator(pollead(Q)) | Q <- B]);

In particular, B is a basis of the maximal order if and only if poldisc(T) / i_T² is equal to the field discriminant. More generally, this formula gives the square of index of the order given by B in ℤ_K. For instance, assume that P is a vector of prime numbers containing (at least) all prime divisors of the field discriminant, then the following construct allows to provably compute the field discriminant and to check whether the returned basis is actually a basis of the maximal order

  ? B = nfbasis([T, P], &D);
  ? dK = sign(D) * vecprod([p^valuation(D,p) | p<-P]);
  ? dK * nfbasisindex(T, B)^2 == poldisc(T)

The variable dK contains the field discriminant and the last command returns 1 if and only if B is a ℤ-basis of the maximal order. Of course, the nfinit / nfcertify approach is simpler, but it is also more costly.

The Buchmann-Lenstra algorithm.

We now complicate the picture: it is in fact allowed to include composite numbers instead of primes in listP (Vector or Matrix case), provided they are pairwise coprime. The result may still be a correct integral basis if the field discriminant factors completely over the actual primes in the list; again, this is not guaranteed. Adding a composite C such that C² divides D may help because when we consider C as a prime and run the algorithm, two good things can happen: either we succeed in proving that no prime dividing C can divide the index (without actually needing to find those primes), or the computation exhibits a nontrivial zero divisor, thereby factoring C and we go on with the refined factorization. (Note that including a C such that C² does not divide D is useless.) If neither happen, then the computed basis need not generate the maximal order. Here is an example:

  ? B = 10^5;
  ? listP = factor(poldisc(T), B); \\ primes <= B dividing D + cofactor
  ? basis = nfbasis([T, listP], &D)

If the computed discriminant D factors completely over the primes less than B (together with the primes contained in the addprimes table), then everything is certified: D is the field discriminant and basis generates the maximal order. This can be tested as follows:

    F = factor(D, B); P = F[,1]; E = F[,2];
    for (i = 1, #P,
      if (P[i] > B && !isprime(P[i]), warning("nf may be incorrect")));

This is a sufficient but not a necessary condition, hence the warning, instead of an error.

The function nfcertify speeds up and automates the above process:

  ? B = 10^5;
  ? nf = nfinit([T, B]);
  ? nfcertify(nf)
  %3 = []      \\ nf is unconditionally correct
  ? [basis, disc] = [nf.zk, nf.disc];

The library syntax is GEN nfbasis(GEN T, GEN *dK = NULL).

Given an algebraic number x in the number field nf, transforms it into t_POLMOD form.

  ? nf = nfinit(y^2 + 4);
  ? nf.zk
  %2 = [1, 1/2*y]
  ? nfbasistoalg(nf, [1,1]~)
  %3 = Mod(1/2*y + 1, y^2 + 4)
  ? nfbasistoalg(nf, y)
  %4 = Mod(y, y^2 + 4)
  ? nfbasistoalg(nf, Mod(y, y^2+4))
  %5 = Mod(y, y^2 + 4)

This is the inverse function of nfalgtobasis.

The library syntax is GEN basistoalg(GEN nf, GEN x).

nf being as output by nfinit, checks whether the integer basis is known unconditionally. This is in particular useful when the argument to nfinit was of the form [T, listP], specifying a finite list of primes when p-maximality had to be proven, or a list of coprime integers to which Buchmann-Lenstra algorithm was to be applied.

The function returns a vector of coprime composite integers. If this vector is empty, then nf.zk and nf.disc are correct. Otherwise, the result is dubious. In order to obtain a certified result, one must completely factor each of the given integers, then addprime each of their prime factors, then check whether nfdisc(nf.pol) is equal to nf.disc.

The library syntax is GEN nfcertify(GEN nf).

Let nf be a number field structure attached to the field K and let P and Q be squarefree polynomials in K[X] in the same variable. Outputs the simple factors of the étale K-algebra A = K[X, Y] / (P(X), Q(Y)). The factors are given by a list of polynomials R in K[X], attached to the number field K[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. In this case, there will be a single factor R if and only if the number fields defined by P and Q are linearly disjoint (their intersection is K).

The binary digits of flag mean

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 K[X]/(R). Finally, k is a small integer such that b + ka = X modulo R.

2: assume that P and Q define number fields that are linearly disjoint: both polynomials are irreducible and the corresponding number fields have no common subfield besides K. This allows to save a costly factorization over K. In this case return the single simple factor instead of a vector with one element.

A compositum is often defined by a complicated polynomial, which it is advisable to reduce before further work. Here is an example involving the field K(ζ₅, 5^1/10), K = ℚ(sqrt{5}):

  ? K = nfinit(y^2-5);
  ? L = nfcompositum(K, x^5 - y, polcyclo(5), 1); \\  list of [R,a,b,k]
  ? [R, a] = L[1];  \\  pick the single factor, extract R,a (ignore b,k)
  ? lift(R)         \\  defines the compositum
  %4 = x^10 + (-5/2*y + 5/2)*x^9 + (-5*y + 20)*x^8 + (-20*y + 30)*x^7 + \
  (-45/2*y + 145/2)*x^6 + (-71/2*y + 121/2)*x^5 + (-20*y + 60)*x^4 +    \
  (-25*y + 5)*x^3 + 45*x^2 + (-5*y + 15)*x + (-2*y + 6)
  ? a^5 - y         \\  a fifth root of y
  %5 = 0
  ? [T, X] = rnfpolredbest(K, R, 1);
  ? lift(T)     \\  simpler defining polynomial for K[x]/(R)
  %7 = x^10 + (-11/2*y + 25/2)
  ? liftall(X)  \\   root of R in K[x]/(T(x))
  %8 = (3/4*y + 7/4)*x^7 + (-1/2*y - 1)*x^5 + 1/2*x^2 + (1/4*y - 1/4)
  ? a = subst(a.pol, 'x, X);  \\  a in the new coordinates
  ? liftall(a)
  %10 = (-3/4*y - 7/4)*x^7 - 1/2*x^2
  ? a^5 - y
  %11 = 0

The main variables of P and Q must be the same and have higher priority than that of nf (see varhigher and varlower).

The library syntax is GEN nfcompositum(GEN nf, GEN P, GEN Q, long flag).

field discriminant of the number field defined by the integral, preferably monic, irreducible polynomial T(X). Returns the discriminant of the number field ℚ[X]/(T), using the Round 4 algorithm.

Local discriminants, valuations at certain primes.

As in nfbasis, the argument T can be replaced by [T,listP], where listP is as in nfbasis: a vector of pairwise coprime integers (usually distinct primes), a factorization matrix, or a single integer. In that case, the function returns the discriminant of an order whose basis is given by nfbasis(T,listP), which need not be the maximal order, and whose valuation at a prime entry in listP is the same as the valuation of the field discriminant.

In particular, if listP is [p] for a prime p, we can return the p-adic discriminant of the maximal order of ℤ_p[X]/(T), as a power of p, as follows:

  ? padicdisc(T,p) = p^valuation(nfdisc([T,[p]]), p);
  ? nfdisc(x^2 + 6)
  %2 = -24
  ? padicdisc(x^2 + 6, 2)
  %3 = 8
  ? padicdisc(x^2 + 6, 3)
  %4 = 3

The following function computes the discriminant of the maximal order under the assumption that P is a vector of prime numbers containing (at least) all prime divisors of the field discriminant:

  globaldisc(T, P) =
  { my (D = nfdisc([T, P]));
    sign(D) * vecprod([p^valuation(D,p) | p <-P]);
  }
  ? globaldisc(x^2 + 6, [2, 3, 5])
  %1 = -24

The library syntax is GEN nfdisc(GEN T). Also available is GEN nfbasis(GEN T, GEN *d), which returns the order basis, and where *d receives the order discriminant.

Given a polynomial T with integer coefficients, return [D, faD] where D is nfdisc(T) and faD is the factorization of |D|. All the variants [T,listP] are allowed (see ??nfdisc), in which case faD is the factorization of the discriminant underlying order (which need not be maximal at the primes not specified by listP) and the factorization may contain large composites.

  ? T = x^3 - 6021021*x^2 + 12072210077769*x - 8092423140177664432;
  ? [D,faD] = nfdiscfactors(T); print(faD); D
  [3, 3; 500009, 2]
  %2 = -6750243002187]
  
  ? T = x^3 + 9*x^2 + 27*x - 125014250689643346789780229390526092263790263725;
  ? [D,faD] = nfdiscfactors(T); print(faD); D
  [3, 3; 1000003, 2]
  %4 = -27000162000243
  
  ? [D,faD] = nfdiscfactors([T, 10^3]); print(faD)
  [3, 3; 125007125141751093502187, 2]

In the final example, we only get a partial factorization, which is only guaranteed correct at primes ≤ 10³.

The function also accept number field structures, for instance as output by nfinit, and returns the field discriminant and its factorization:

  ? T = x^3 + 9*x^2 + 27*x - 125014250689643346789780229390526092263790263725;
  ? nf = nfinit(T); [D,faD] = nfdiscfactors(T); print(faD); D
  %2 = -27000162000243
  ? nf.disc
  %3 = -27000162000243

The library syntax is GEN nfdiscfactors(GEN T).

Given two elements x and y in nf, computes their sum x+y in the number field nf.

  ? nf = nfinit(1+x^2);
  ? nfeltadd(nf, 1, x) \\ 1 + I
  %2 = [1, 1]~

The library syntax is GEN nfadd(GEN nf, GEN x, GEN y).

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

The library syntax is GEN nfdiv(GEN nf, GEN x, GEN 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(nfdiv(nf,x,y)).

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

This function is obsolete, use nfmodpr.

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 GEN nfdivmodpr(GEN nf, GEN x, GEN y, GEN pr). This function is normally useless in library mode. Project your inputs to the residue field using nf_to_Fq, then work there.

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 GEN nfdivrem(GEN nf, GEN x, GEN y).

Given an element x in the number field nf, return the (real or) complex embeddings of x specified by optional argument pl, at the current realprecision:

* pl omitted: return the vector of embeddings at all r₁+r₂ places;

* pl an integer between 1 and r₁+r₂: return the i-th embedding of x, attached to the i-th root of nf.pol, i.e. nf.roots[i];

* pl a vector or t_VECSMALL: return the vector of embeddings; the i-th entry gives the embedding at the place attached to the pl[i]-th real root of nf.pol.

  ? nf = nfinit('y^3 - 2);
  ? nf.sign
  %2 = [1, 1]
  ? nfeltembed(nf, 'y)
  %3 = [1.25992[...], -0.62996[...] + 1.09112[...]*I]]
  ? nfeltembed(nf, 'y, 1)
  %4 = 1.25992[...]
  ? nfeltembed(nf, 'y, 3) \\ there are only 2 arch. places
   ***   at top-level: nfeltembed(nf,'y,3)
   ***                 ^ —  —  —  —  — --
   *** nfeltembed: domain error in nfeltembed: index > 2

The library syntax is GEN nfeltembed(GEN nf, GEN x, GEN pl = NULL, long prec).

Returns 1 if x is an n-th power in the number field nf (and sets y to an n-th root if the argument is present), else returns 0.

  ? nf = nfinit(1+x^2);
  ? nfeltispower(nf, -4, 4, &y)
  %2 = 1
  ? y
  %3 = [-1, -1]~

The library syntax is long nfispower(GEN nf, GEN x, long n, GEN *y = NULL).

Returns 1 if x is a square in nf (and sets y to a square root if the argument is present), else returns 0.

  ? nf = nfinit(1+x^2);
  ? nfeltissquare(nf, -1, &y)
  %2 = 1
  ? y
  %3 = [0, -1]~

The library syntax is long nfissquare(GEN nf, GEN x, GEN *y = NULL).

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 - nfmul(nf,round(nfdiv(nf,x,y)),y).

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

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

The library syntax is GEN nfmul(GEN nf, GEN x, GEN y).

This function is obsolete, use nfmodpr.

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 GEN nfmulmodpr(GEN nf, GEN x, GEN y, GEN pr). This function is normally useless in library mode. Project your inputs to the residue field using nf_to_Fq, then work there.

Returns the absolute norm of x.

The library syntax is GEN nfnorm(GEN nf, GEN x).

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 GEN nfpow(GEN nf, GEN x, GEN k). GEN nfinv(GEN nf, GEN x) correspond to k = -1, and GEN nfsqr(GEN nf,GEN x) to k = 2.

This function is obsolete, use nfmodpr.

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 GEN nfpowmodpr(GEN nf, GEN x, GEN k, GEN pr). This function is normally useless in library mode. Project your inputs to the residue field using nf_to_Fq, then work there.

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

The library syntax is GEN nfreduce(GEN nf, GEN a, GEN id).

This function is obsolete, use nfmodpr.

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 GEN nfreducemodpr(GEN nf, GEN x, GEN pr). This function is normally useless in library mode. Project your inputs to the residue field using nf_to_Fq, then work there.

Given an element x in the number field nf, returns the signs of the real embeddings of x specified by optional argument pl:

* pl omitted: return the vector of signs at all r₁ real places;

* pl an integer between 1 and r₁: return the sign of the i-th embedding of x, attached to the i-th real root of nf.pol, i.e. nf.roots[i];

* pl a vector or t_VECSMALL: return the vector of signs; the i-th entry gives the sign at the real place attached to the pl[i]-th real root of nf.pol.

  ? nf = nfinit(polsubcyclo(11,5,'y)); \\ Q(cos(2 pi/11))
  ? nf.sign
  %2 = [5, 0]
  ? x = Mod('y, nf.pol);
  ? nfeltsign(nf, x)
  %4 = [-1, -1, -1, 1, 1]
  ? nfeltsign(nf, x, 1)
  %5 = -1
  ? nfeltsign(nf, x, [1..4])
  %6 = [-1, -1, -1, 1]
  ? nfeltsign(nf, x, 6) \\ there are only 5 real embeddings
   ***   at top-level: nfeltsign(nf,x,6)
   ***                 ^ —  —  —  —  — --
   *** nfeltsign: domain error in nfeltsign: index > 5

The library syntax is GEN nfeltsign(GEN nf, GEN x, GEN pl = NULL).

Returns the absolute trace of x.

The library syntax is GEN nftrace(GEN nf, GEN x).

Given an element x in nf and a prime ideal pr in the format output by idealprimedec, computes the valuation v at pr of the element x. The valuation of 0 is +oo.

  ? nf = nfinit(x^2 + 1);
  ? P = idealprimedec(nf, 2)[1];
  ? nfeltval(nf, x+1, P)
  %3 = 1

This particular valuation can also be obtained using idealval(nf,x,pr), since x is then converted to a principal ideal.

If the y argument is present, sets y = x τ^v, where τ is a fixed "anti-uniformizer" for pr: its valuation at pr is -1; its valuation is 0 at other prime ideals dividing pr.p and nonnegative at all other primes. In other words y is the part of x coprime to pr. If x is an algebraic integer, so is y.

  ? nfeltval(nf, x+1, P, &y); y
  %4 = [0, 1]~

For instance if x = ∏_i x_i^e_i is known to be coprime to pr, where the x_i are algebraic integers and e_i ∈ ℤ then, if v_i = nfeltval(nf, x_i, pr, &y_i), we still have x = ∏_i y_i^e_i, where the y_i are still algebraic integers but now all of them are coprime to pr. They can then be mapped to the residue field of pr more efficiently than if the product had been expanded beforehand: we can reduce mod pr after each ring operation.

The library syntax is GEN gpnfvalrem(GEN nf, GEN x, GEN pr, GEN *y = NULL). Also available are long nfvalrem(GEN nf, GEN x, GEN pr, GEN *y = NULL), which returns LONG_MAX if x = 0 and the valuation as a long integer, and long nfval(GEN nf, GEN x, GEN pr), which only returns the valuation (y = NULL).

Factorization of the univariate polynomial (or rational function) T over the number field nf given by nfinit; T has coefficients in nf (i.e. either scalar, polmod, polynomial or column vector). The factors are sorted by increasing degree.

The main variable of nf must be of lower priority than that of T, see Section se:priority. However if the polynomial defining the number field occurs explicitly in the coefficients of T as modulus of a t_POLMOD or as a t_POL coefficient, its main variable must be the same as the main variable of T. 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

It is possible to input a defining polynomial for nf instead, but this is in general less efficient since parts of an nf structure will then be computed internally. This is useful in two situations: when you do not need the nf elsewhere, or when you cannot initialize an nf due to integer factorization difficulties when attempting to compute the field discriminant and maximal order. In all cases, the function runs in polynomial time using Belabas's variant of van Hoeij's algorithm, which copes with hundreds of modular factors.

Caveat. nfinit([T, listP]) allows to compute in polynomial time a conditional nf structure, which sets nf.zk to an order which is not guaranteed to be maximal at all primes. Always either use nfcertify first (which may not run in polynomial time) or make sure to input nf.pol instead of the conditional nf: nffactor is able to recover in polynomial time in this case, instead of potentially missing a factor.

The library syntax is GEN nffactor(GEN nf, GEN T).

Gives back the nf element corresponding to a factorization. The integer 1 corresponds to the empty factorization.

If e is present, e and f must be vectors of the same length (e being integral), and the corresponding factorization is the product of the f[i]^e[i].

If not, and f is vector, it is understood as in the preceding case with e a vector of 1s: we return the product of the f[i]. Finally, f can be a regular factorization matrix.

  ? nf = nfinit(y^2+1);
  ? nffactorback(nf, [3, y+1, [1,2]~], [1, 2, 3])
  %2 = [12, -66]~
  ? 3 * (I+1)^2 * (1+2*I)^3
  %3 = 12 - 66*I

The library syntax is GEN nffactorback(GEN nf, GEN f, GEN e = NULL).

This routine is obsolete, use nfmodpr and factormod.

Factors the univariate polynomial Q modulo the prime ideal pr in the number field nf. The coefficients of Q belong to the number field (scalar, polmod, polynomial, even column vector) and the main variable of nf must be of lower priority than that of Q (see Section se:priority). The prime ideal pr is either in idealprimedec or (preferred) modprinit format. The coefficients of the polynomial factors are lifted to elements of nf:

  ? K = nfinit(y^2+1);
  ? P = idealprimedec(K, 3)[1];
  ? nffactormod(K, x^2 + y*x + 18*y+1, P)
  %3 =
  [x + (2*y + 1) 1]
  
  [x + (2*y + 2) 1]
  ? P = nfmodprinit(K, P);  \\ convert to nfmodprinit format
  ? nffactormod(K, x^2 + y*x + 18*y+1)
  %5 =
  [x + (2*y + 1) 1]
  
  [x + (2*y + 2) 1]

Same result, of course, here about 10% faster due to the precomputation.

The library syntax is GEN nffactormod(GEN nf, GEN Q, GEN pr).

Let nf be a number field as output by nfinit, and let aut be a Galois automorphism of nf expressed by its image on the field generator (such automorphisms can be found using nfgaloisconj). The function computes the action of the automorphism aut on the object x in the number field; x can be a number field element, or an ideal (possibly extended). Because of possible confusion with elements and ideals, other vector or matrix arguments are forbidden.

   ? nf = nfinit(x^2+1);
   ? L = nfgaloisconj(nf)
   %2 = [-x, x]~
   ? aut = L[1]; /* the nontrivial automorphism */
   ? nfgaloisapply(nf, aut, x)
   %4 = Mod(-x, x^2 + 1)
   ? P = idealprimedec(nf,5); /* prime ideals above 5 */
   ? nfgaloisapply(nf, aut, P[2]) == P[1]
   %6 = 0 \\ !!!!
   ? idealval(nf, nfgaloisapply(nf, aut, P[2]), P[1])
   %7 = 1

The surprising failure of the equality test (%7) is due to the fact that although the corresponding prime ideals are equal, their representations are not. (A prime ideal is specified by a uniformizer, and there is no guarantee that applying automorphisms yields the same elements as a direct idealprimedec call.)

The automorphism can also be given as a column vector, representing the image of Mod(x, nf.pol) as an algebraic number. This last representation is more efficient and should be preferred if a given automorphism must be used in many such calls.

   ? nf = nfinit(x^3 - 37*x^2 + 74*x - 37);
   ? aut = nfgaloisconj(nf)[2]; \\   an automorphism in basistoalg form
   %2 = -31/11*x^2 + 1109/11*x - 925/11
   ? AUT = nfalgtobasis(nf, aut); \\   same in algtobasis form
   %3 = [16, -6, 5]~
   ? v = [1, 2, 3]~; nfgaloisapply(nf, aut, v) == nfgaloisapply(nf, AUT, v)
   %4 = 1 \\   same result...
   ? for (i=1,10^5, nfgaloisapply(nf, aut, v))
   time = 463 ms.
   ? for (i=1,10^5, nfgaloisapply(nf, AUT, v))
   time = 343 ms.  \\   but the latter is faster

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

nf being a number field as output by nfinit, computes the conjugates of a root r of the nonconstant polynomial x = nf[1] expressed as polynomials in r. This also makes sense when the number field is not Galois since some conjugates may lie in the field. nf can simply be a polynomial.

If no flags or flag = 0, use a combination of flag 4 and 1 and the result is always complete. There is no point whatsoever in using the other flags.

If flag = 1, use nfroots: a little slow, but guaranteed to work in polynomial time.

If flag = 4, use galoisinit: very fast, but only applies to (most) Galois fields. If the field is Galois with weakly super-solvable Galois group (see galoisinit), 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.

This routine can only compute ℚ-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)
  {
    my(polabs, N,al,S, ala,k, vR);
    R *= Mod(1, nfK.pol); \\ convert coeffs to polmod elts of K
    vR = variable(R);
    al = Mod(variable(nfK.pol),nfK.pol);
    [polabs,ala,k] = rnfequation(nfK, R, 1);
    Rt = if(k==0,R,subst(R,vR,vR-al*k));
    N = nfgaloisconj(polabs) % Rt; \\ Q-automorphisms of L
    S = select(s->subst(Rt, vR, Mod(s,Rt)) == 0, N);
    if (k==0, S, apply(s->subst(s,vR,vR+k*al)-k*al,S));
  }
  K  = nfinit(y^2 + 7);
  rnfgaloisconj(K, x^4 - y*x^3 - 3*x^2 + y*x + 1)  \\ K-automorphisms of L

The library syntax is GEN galoisconj0(GEN nf, long flag, GEN d = NULL, long prec). Use directly GEN galoisconj(GEN nf, GEN d), corresponding to flag = 0, the others only have historical interest.

If pr is omitted, compute the global quadratic Hilbert symbol (a,b) in nf, that is 1 if x² - a y² - b z² 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 quaternion algebra (a,b) over nf can be created with alginit(nf,[a,b]) (see alginit).

The library syntax is long nfhilbert0(GEN nf, GEN a, GEN b, GEN pr = NULL).

Also available is long nfhilbert(GEN nf,GEN a,GEN b) (global quadratic Hilbert symbol), where nf is a true nf structure.

pol being a nonconstant irreducible polynomial in ℚ[X], preferably monic and integral, initializes a number field (or nf) structure attached to the field K defined by pol. As such, it's a technical object passed as the first argument to most nfxxx 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 given 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 [r₁,r₂] (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. [ℤ_K : ℤ[θ]], where θ is any root of nf[1].

nf[5] is a vector containing 7 matrices M, G, roundG, T, MD, TI, MDI and a vector vP defined as follows:

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

  * G is an n x n matrix such that T2 = ^t G G, where T2 is the quadratic form T₂(x) = ∑ |σ(x)|², σ running over the embeddings of K into ℂ.

  * roundG is a rescaled copy of G, rounded to nearest integers.

  * T is the n x n matrix whose coefficients are Tr(ω_iω_j) where the ω_i are the elements of the integral basis. Note also that det(T) is equal to the discriminant of the field K. Also, when understood as an ideal, the matrix T^-1 generates the codifferent ideal.

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

  * TI is equal to the primitive part of T^-1, which has integral coefficients.

  * 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). This is used in idealinv.

  * vP is the list of prime divisors of the field discriminant, i.e, the ramified primes (nf.p); nfdiscfactors(nf) is the preferred way to access that information.

nf[6] is the vector containing the r₁+r₂ roots (nf.roots) of nf[1] corresponding to the r₁+r₂ embeddings of the number field into ℂ (the first r₁ components are real, the next r₂ have positive imaginary part).

nf[7] is a ℤ-basis for dℤ_K, where d = [ℤ_K:ℤ(θ)], expressed on the powers of θ. The multiplication by d ensures that all polynomials have integral coefficients and nf[7] / d (nf.zk) is an integral basis for ℤ_K. Its first element is guaranteed to be 1. This basis is LLL-reduced with respect to T₂ (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² matrix giving the multiplication table of the integral basis.

If a non monic or non integral polynomial is input, nfinit will transform it, and return a structure attached to the new (monic integral) polynomial together with the attached change of variables, 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. It is also allowed to input a rnf, in which case an nf structure attached to the absolute defining polynomial polabs is returned (flag is then ignored).

  ? 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]  \\   𝔭23

Huge discriminants, helping nfdisc.

In case pol has a huge discriminant which is difficult to factor, it is hard to compute from scratch the maximal order. The following special input formats are also accepted:

* [pol, B] where pol is a monic integral polynomial and B is the lift of an integer basis, as would be computed by nfbasis: a vector of polynomials with first element 1 (implicitly modulo pol). This is useful if the maximal order is known in advance.

* [pol, B, P] where pol and B are as above (a monic integral polynomial and the lift of an integer basis), and P is the list of ramified primes in the extension.

* [pol, listP] where pol is a rational polynomial and listP specifies a list of primes as in nfbasis. Instead of the maximal order, nfinit then computes an order which is maximal at these particular primes as well as the primes contained in the private prime table, see addprimes. The result has a good chance of being correct when the discriminant nf.disc factors completely over this set of primes but this is not guaranteed. The function nfcertify automates this:

  ? pol = polcompositum(x^5 - 101, polcyclo(7))[1];
  ? nf = nfinit( [pol, 10^3] );
  ? nfcertify(nf)
  %3 = []

A priori, nf.zk defines an order which is only known to be maximal at all primes ≤ 10³ (no prime ≤ 10³ divides nf.index). The certification step proves the correctness of the computation. Had it failed, that particular nf structure could not have been trusted and may have caused routines using it to fail randomly. One particular function that remains trustworthy in all cases is idealprimedec when applied to a prime included in the above list of primes or, more generally, a prime not dividing any entry in nfcertify output.

In order to explain the meaning of flag, let P = polredbest(pol), a polynomial defining the same number field obtained using the LLL algorithm on the lattice (ℤ_K, T₂), which may be equal to pol but is usually different and simpler. Binary digits of flag mean:

* 1: return [nf,Mod(a,P)], where nf is nfinit(P) and Mod(a,P) = Mod(x,pol) gives the change of variables. If only this bit is set, the behaviour is useless since we have P = pol.

* 2: return nfinit(P).

Both flags are set automatically when pol is not monic or not integral: first a linear change of variables is performed, to get a monic integral polynomial, then polredbest.

* 4: do not LLL-reduce nf.zk, which saves time in large degrees, you may expect to gain a factor 2 or so in degree n ≥ 100 or more, at the expense of possibly slowing down later uses of the nf structure. Use this flag if you only need basic arithmetic (the nfelt*, nfmodpr* and ideal* functions); or if you expect the natural basis of the maximal order to contain small elements, this will be the case for cyclotomic fields for instance. On the other hand, functions involving LLL reduction of rank n lattices should be avoided since each call will be about as costly as the initial LLL reduction that the flag prevents and may become more costly because of this missing initial reduction. In particular it is silly to use this flag in addition to the first two, although GP will not protest.

  ? T = polcyclo(307);
  ? K = nfinit(T);
  time = 19,390 ms.
  ? a = idealhnf(K,1-x);
  time = 477ms
  ? idealfactor(K, a)
  time = 294ms
  
  ? Kno = nfinit(T, 4);
  time = 11,256 ms.
  ? ano = idealhnf(Kno,1-x); \\ no slowdown, even sligthly faster
  time = 460ms
  ? idealfactor(Kno, ano)
  time = 264ms
  
  ? nfinit(T, 2); \\ polredbest is very slow in high degree
  time = 4min, 34,870 ms.
  ? norml2(%.pol) == norml2(T) \\ and gains nothing here
  %9 = 1

The library syntax is GEN nfinit0(GEN pol, long flag, long prec). Also available are GEN nfinit(GEN x, long prec) (flag = 0), GEN nfinitred(GEN x, long prec) (flag = 2), GEN nfinitred2(GEN x, long prec) (flag = 3). Instead of the above hardcoded numerical flags in nfinit0, one should rather use an or-ed combination of

* nf_RED: find a simpler defining polynomial,

* nf_ORIG: also return the change of variable,

* nf_NOLLL: do not LLL-reduce the maximal order ℤ-basis.

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

The library syntax is long isideal(GEN nf, GEN x).

Let f and g define number fields, where f and g are irreducible polynomials in ℚ[X] and nf structures as output by nfinit. If either f or g is not irreducible, the result is undefined. Tests whether the number field f is conjugate to a subfield of the field g. If not, the output is the integer 0; if it is, the output depends on the value of flag:

* flag = 0 (default): return a vector of polynomials [a₁,...,a_n] with rational coefficients, representing all distinct embeddings: we have g | f o a_i for all i.

* flag = 1: return a single polynomial a representing a single embedding; this can be n times faster than the default when the embeddings have huge coefficients.

* flag = 2: return a vector of rational functions [r₁,...,r_n] whose denominators are coprime to g and such that r_i % g is the polynomial a_i from flag = 0. This variant is always faster than flag = 0 but produces results which are harder to use. If the denominators are hard to invert in ℚ[X]/(g), this may be even faster than flag = 1.

  ? T = x^6 + 3*x^4 - 6*x^3 + 3*x^2 + 18*x + 10;
  ? U = x^3 + 3*x^2 + 3*x - 2;
  ? nfisincl(U, T)
  %3 = [24/179*x^5-27/179*x^4+80/179*x^3-234/179*x^2+380/179*x+94/179]
  ? a = nfisincl(U, T, 1)
  %4 = 24/179*x^5-27/179*x^4+80/179*x^3-234/179*x^2+380/179*x+94/179
  ? subst(U, x, Mod(a,T))
  %5 = Mod(0, x^6 + 3*x^4 - 6*x^3 + 3*x^2 + 18*x + 10)
  ? nfisincl(U, T, 2) \\ a as a t_RFRAC
  %6 = [(2*x^3 - 3*x^2 + 2*x + 4)/(3*x^2 - 1)]
  ? (a - %[1]) % T
  %7 = 0
  ? #nfisincl(x^2+1, T) \\ two embeddings
  %8 = 2
  
  \\ same result with nf structures
  ? L = nfinit(T); K = nfinit(U); v = [a];
  ? nfisincl(U, L) == v
  %10 = 1
  ? nfisincl(K, T) == v
  %11 = 1
  ? nfisincl(K, L) == v
  %12 = 1
  
  \\ comparative bench: an nf is a little faster, esp. for the subfield
  ? B = 2000;
  ? for (i=1, B, nfisincl(U,T))
  time = 1,364 ms.
  ? for (i=1, B, nfisincl(K,T))
  time = 988 ms.
  ? for (i=1, B, nfisincl(U,L))
  time = 1,341 ms.
  ? for (i=1, B, nfisincl(K,L))
  time = 880 ms.

Using an nf structure for the tentative subfield is faster if the structure is already available. On the other hand, the gain in nfisincl is usually not sufficient to make it worthwhile to initialize only for that purpose.

  ? for (i=1, B, nfinit(U))
  time = 590 ms.

A final more complicated example

  ? f = x^8 - 72*x^6 + 1944*x^4 - 30228*x^2 - 62100*x - 34749;
  ? g = nfsplitting(f); poldegree(g)
  %2 = 96
  ? #nfisincl(f, g)
  time = 559 ms.
  %3 = 8
  ? nfisincl(f,g,1);
  time = 172 ms.
  ? v = nfisincl(f,g,2);
  time = 199 ms.
  ? apply(x->poldegree(denominator(x)), v)
  %6 = [81, 81, 81, 81, 81, 81, 80, 81]
  ? v % g;
  time = 407 ms.

This final example shows that mapping rational functions to ℚ[X]/(g) can be more costly than that the rest of the algorithm. Note that nfsplitting also admits a flag yielding an embedding.

The library syntax is GEN nfisincl0(GEN f, GEN g, long flag). Also available is GEN nfisisom(GEN a, GEN b) (flag = 0).

As nfisincl, but tests for isomorphism. More efficient if f or g is a number field structure.

  ? f = x^6 + 30*x^5 + 495*x^4 + 1870*x^3 + 16317*x^2 - 22560*x + 59648;
  ? g = x^6 + 42*x^5 + 999*x^4 + 8966*x^3 + 36117*x^2 + 21768*x + 159332;
  ? h = x^6 + 30*x^5 + 351*x^4 + 2240*x^3 + 10311*x^2 + 35466*x + 58321;
  
  ? #nfisisom(f,g)  \\ two isomorphisms
  %3 = 2
  ? nfisisom(f,h) \\ not isomorphic
  %4 = 0
  \\ comparative bench
  ? K = nfinit(f); L = nfinit(g); B = 10^3;
  ? for (i=1, B, nfisisom(f,g))
  time = 6,124 ms.
  ? for (i=1, B, nfisisom(K,g))
  time = 3,356 ms.
  ? for (i=1, B, nfisisom(f,L))
  time = 3,204 ms.
  ? for (i=1, B, nfisisom(K,L))
  time = 3,173 ms.

The function is usually very fast when the fields are nonisomorphic, whenever the fields can be distinguished via a simple invariant such as degree, signature or discriminant. It may be slower when the fields share all invariants, but still faster than computing actual isomorphisms:

  \\ usually very fast when the answer is 'no':
  ? for (i=1, B, nfisisom(f,h))
  time = 32 ms.
  
  \\ but not always
  ? u = x^6 + 12*x^5 + 6*x^4 - 377*x^3 - 714*x^2 + 5304*x + 15379
  ? v = x^6 + 12*x^5 + 60*x^4 + 166*x^3 + 708*x^2 + 6600*x + 23353
  ? nfisisom(u,v)
  %13 = 0
  ? polsturm(u) == polsturm(v)
  %14 = 1
  ? nfdisc(u) == nfdisc(v)
  %15 = 1
  ? for(i=1,B, nfisisom(u,v))
  time = 1,821 ms.
  ? K = nfinit(u); L = nfinit(v);
  ? for(i=1,B, nfisisom(K,v))
  time = 232 ms.

The library syntax is GEN nfisisom(GEN f, GEN g).

Let nf be a nf structure attached to a number field K, let a ∈ K and let pr be a prid structure attached to a maximal ideal v. Return 1 if a is an n-th power in the completed local field K_v, and 0 otherwise.

  ? K = nfinit(y^2+1);
  ? P = idealprimedec(K,2)[1]; \\ the ramified prime above 2
  ? nfislocalpower(K,P,-1, 2) \\ -1 is a square
  %3 = 1
  ? nfislocalpower(K,P,-1, 4) \\ ... but not a 4-th power
  %4 = 0
  ? nfislocalpower(K,P,2, 2)  \\ 2 is not a square
  %5 = 0
  
  ? Q = idealprimedec(K,5)[1]; \\ a prime above 5
  ? nfislocalpower(K,Q, [0, 32]~, 30)  \\ 32*I is locally a 30-th power
  %7 = 1

The library syntax is long nfislocalpower(GEN nf, GEN pr, GEN a, GEN n).

This function is obsolete, use nfmodpr.

Kernel of the matrix a in ℤ_K/pr, where pr is in modpr format (see nfmodprinit).

The library syntax is GEN nfkermodpr(GEN nf, GEN x, GEN pr). This function is normally useless in library mode. Project your inputs to the residue field using nfM_to_FqM, then work there.

Map x to a t_FFELT in the residue field modulo pr. The argument pr is either a maximal ideal in idealprimedec format or, preferably, a modpr structure from nfmodprinit. The function nfmodprlift allows to lift back to ℤ_K.

Note that the function applies to number field elements and not to vector / matrices / polynomials of such. Use apply to convert recursive structures.

  ? K = nfinit(y^3-250);
  ? P = idealprimedec(K, 5)[2];
  ? modP = nfmodprinit(K, P, 't);
  ? K.zk
  %4 = [1, 1/5*y, 1/25*y^2]
  ? apply(t->nfmodpr(K,t,modP), K.zk)
  %5 = [1, t, 2*t + 1]
  ? %[1].mod
  %6 = t^2 + 3*t + 4
  ? K.index
  %7 = 125

For clarity, we represent elements in the residue field 𝔽₅[t]/(T) as polynomials in the variable t. Whenever the underlying rational prime does not divide K.index, it is actually the case that t is the reduction of y in ℚ[y]/(K.pol) modulo an irreducible factor of K.pol over 𝔽_p. In the above example, 5 divides the index and t is actually the reduction of y/5.

Elements can be given in factored form if their global valuation at pr is non-negative.

  ? nfmodpr(K, [y/5, 2; 1+y, 3], modP) \\ (y/5)^2 * (1 + y)^3
  %8 = 2*t + 1
  ? nfmodpr(K, [y, -1; 1+y, 3], modP)  \\ negative valuation at pr
   ***   at top-level: nfmodpr(K,[y,-1;1+y,3],modP)
   ***                 ^ —  —  —  —  —  —  —  —  — -
   *** nfmodpr: impossible inverse in nfmodpr: Mod(0, 5).

The library syntax is GEN nfmodpr(GEN nf, GEN x, GEN pr).

Transforms the prime ideal pr into modpr format necessary for all operations modulo pr in the number field nf. The functions nfmodpr and nfmodprlift allow to project to and lift from the residue field. The variable v is used to display finite field elements which are not in the prime field (see ffgen).

  ? K = nfinit(y^3-250);
  ? P = idealprimedec(K, 5)[2];
  ? modP = nfmodprinit(K, P, 't);
  ? K.zk
  %4 = [1, 1/5*y, 1/25*y^2]
  ? apply(t->nfmodpr(K,t,modP), K.zk)
  %5 = [1, t, 2*t + 1]
  ? %[1].mod
  %6 = t^2 + 3*t + 4
  ? K.index
  %7 = 125

For clarity, we represent elements in the residue field 𝔽₅[t]/(T) as polynomials in the variable t. Whenever the underlying rational prime does not divide K.index, it is actually the case that t is the reduction of y in ℚ[y]/(K.pol) modulo an irreducible factor of K.pol over 𝔽_p. In the above example, 5 divides the index and t is actually the reduction of y/5.

The library syntax is GEN nfmodprinit0(GEN nf, GEN pr, long v = -1) where v is a variable number.

Lift an element x from in the residue field modulo pr to the ring of integers; x is a t_INTMOD or t_FFELT from nfmodpr. Vectors and matrices of such elements are also supported. For polynomials, use apply and the present function.

The argument pr is either a maximal ideal in idealprimedec format or, preferably, a modpr structure from nfmodprinit. There are no compatibility checks to try and decide whether x is attached the same residue field as defined by pr: the result is undefined if not.

The function nfmodpr allows to reduce to the residue field.

  ? K = nfinit(y^3-250);
  ? P = idealprimedec(K, 5)[2];
  ? modP = nfmodprinit(K,P);
  ? K.zk
  %4 = [1, 1/5*y, 1/25*y^2]
  ? apply(t->nfmodpr(K,t,modP), K.zk)
  %5 = [1, y, 2*y + 1]
  ? nfmodprlift(K, %, modP)
  %6 = [1, 1/5*y, 2/5*y + 1]
  ? nfeltval(K, %[3] - K.zk[3], P)
  %7 = 1

The library syntax is GEN nfmodprlift(GEN nf, GEN x, GEN pr).

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, a bnr or a rnf (update structure to current precision). If the original bnf structure was not computed by bnfinit(,1), then this may be quite slow and even fail: many generators of principal ideals have to be computed and the algorithm may fail because the accuracy is not sufficient to bootstrap the required generators and fundamental units.

The library syntax is GEN nfnewprec(GEN nf, long prec). See also GEN bnfnewprec(GEN bnf, long prec) and GEN bnrnewprec(GEN bnr, long prec).

Given a polynomial T with coefficients in the number field nf, returns the number of real roots of the s(T) where s runs through the real embeddings of the field specified by optional argument pl:

* pl omitted: all r₁ real places;

* pl an integer between 1 and r₁: the embedding attached to the i-th real root of nf.pol, i.e. nf.roots[i];

* pl a vector or t_VECSMALL: the embeddings attached to the pl[i]-th real roots of nf.pol.

  ? nf = nfinit('y^2 - 2);
  ? nf.sign
  %2 = [2, 0]
  ? nf.roots
  %3 = [-1.414..., 1.414...]
  ? T = x^2 + 'y;
  ? nfpolsturm(nf, T, 1) \\ subst(T,y,sqrt(2)) has two real roots
  %5 = 2
  ? nfpolsturm(nf, T, 2) \\ subst(T,y,-sqrt(2)) has no real root
  %6 = 0
  ? nfpolsturm(nf, T) \\ all embeddings together
  %7 = [2, 0]
  ? nfpolsturm(nf, T, [2,1]) \\ second then first embedding
  %8 = [0, 2]
  ? nfpolsturm(nf, x^3)  \\ number of distinct roots !
  %9 = [1, 1]
  ? nfpolsturm(nf, x, 6) \\ there are only 2 real embeddings !
   ***   at top-level: nfpolsturm(nf,x,6)
   ***                 ^ —  —  —  —  — --
   *** nfpolsturm: domain error in nfpolsturm: index > 2

The library syntax is GEN nfpolsturm(GEN nf, GEN T, GEN pl = NULL).

Roots of the polynomial x in the number field nf given by nfinit without multiplicity (in ℚ 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 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).

It is possible to input a defining polynomial for nf instead, but this is in general less efficient since parts of an nf structure will then be computed internally. This is useful in two situations: when you do not need the nf elsewhere, or when you cannot initialize an nf due to integer factorization difficulties when attempting to compute the field discriminant and maximal order.

Caveat. nfinit([T, listP]) allows to compute in polynomial time a conditional nf structure, which sets nf.zk to an order which is not guaranteed to be maximal at all primes. Always either use nfcertify first (which may not run in polynomial time) or make sure to input nf.pol instead of the conditional nf: nfroots is able to recover in polynomial time in this case, instead of potentially missing a factor.

The library syntax is GEN nfroots(GEN nf = NULL, GEN x). See also GEN nfrootsQ(GEN x), corresponding to nf = NULL.

Returns a two-component vector [w,z] where w is the number of roots of unity in the number field nf, and z is a primitive w-th root of unity. It is possible to input a defining polynomial for nf instead.

  ? K = nfinit(polcyclo(11));
  ? nfrootsof1(K)
  %2 = [22, [0, 0, 0, 0, 0, -1, 0, 0, 0, 0]~]
  ? z = nfbasistoalg(K, %[2])   \\ in algebraic form
  %3 = Mod(-x^5, x^10 + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)
  ? [lift(z^11), lift(z^2)]     \\ proves that the order of z is 22
  %4 = [-1, -x^9 - x^8 - x^7 - x^6 - x^5 - x^4 - x^3 - x^2 - x - 1]

This function guesses the number w as the gcd of the #k(v)^* for unramified v above odd primes, then computes the roots in nf of the w-th cyclotomic polynomial. The algorithm is polynomial time with respect to the field degree and the bitsize of the multiplication table in nf (both of them polynomially bounded in terms of the size of the discriminant). Fields of degree up to 100 or so should require less than one minute.

The library syntax is GEN nfrootsof1(GEN nf).

This function is obsolete, use nfmodpr.

Let P be a prime ideal in modpr format (see nfmodprinit), let a be a matrix, invertible over the residue field, and let b be a column vector or matrix. This function returns a solution of a.x = b; the coefficients of x are lifted to nf elements.

  ? K = nfinit(y^2+1);
  ? P = idealprimedec(K, 3)[1];
  ? P = nfmodprinit(K, P);
  ? a = [y+1, y; y, 0]; b = [1, y]~
  ? nfsolvemodpr(K, a,b, P)
  %5 = [1, 2]~

The library syntax is GEN nfsolvemodpr(GEN nf, GEN a, GEN b, GEN P). This function is normally useless in library mode. Project your inputs to the residue field using nfM_to_FqM, then work there.

Defining polynomial S over ℚ for the splitting field of P ∈ ℚ[x], that is the smallest field over which P is totally split. If irreducible, the polynomial P can also be given by a nf structure, which is more efficient. If d is given, it must be a multiple of the splitting field degree. Note that if P is reducible the splitting field degree can be smaller than the degree of P.

If flag is non-zero, we assume P to be monic, integral and irreducible and the return value depends on flag:

* flag = 1: return [S,C] where S is as before and C is an embedding of ℚ[x]/(P) in its splitting field given by a polynomial (implicitly modulo S, as in nfisincl).

* flag = 2: return [S,C] where C is vector of rational functions whose image in ℚ[x]/(S) yields the embedding; this avoids inverting the denominator, which is costly. when the degree of the splitting field is huge.

* flag = 3: return [S, v, p] a data structure allowing to quickly compute the Galois group of the splitting field, which is used by galoissplittinginit; more precisely, p is a prime splitting completely in the splitting field and v is a vector with deg S elements describing the automorphisms of S acting on the roots of S modulo p.

  ? K = nfinit(x^3 - 2);
  ? nfsplitting(K)
  %2 = x^6 + 108
  ? nfsplitting(x^8 - 2)
  %3 = x^16 + 272*x^8 + 64
  ? S = nfsplitting(x^6 - 8) \\ reducible
  %4 = x^4 + 2*x^2 + 4
  ? lift(nfroots(subst(S,x,a),x^6-8))
  %5 = [-a, a, -1/2*a^3 - a, -1/2*a^3, 1/2*a^3, 1/2*a^3 + a]
  
  ? P = x^8-2;
  ? [S,C] = nfsplitting(P,,1)
  %7 = [x^16 + 272*x^8 + 64, -7/768*x^13 - 239/96*x^5 + 1/2*x]
  ? subst(P, x, Mod(C,S))
  %8 = Mod(0, x^16 + 272*x^8 + 64)

Specifying the degree d of the splitting field can make the computation faster; if d is not a multiple of the true degree, it will be ignored with a warning.

  ? nfsplitting(x^17-123);
  time = 3,607 ms.
  ? poldegree(%)
  %2 = 272
  ? nfsplitting(x^17-123,272);
  time = 150 ms.
  ? nfsplitting(x^17-123,273);
   *** nfsplitting: Warning: ignoring incorrect degree bound 273
  time = 3,611 ms.

The complexity of the algorithm is polynomial in the degree d of the splitting field and the bitsize of T; if d is large the result will likely be unusable, e.g. nfinit will not be an option:

  ? nfsplitting(x^6-x-1)
  [... degree 720 polynomial deleted ...]
  time = 11,020 ms.

Variant: Also available is GEN nfsplitting(GEN T, GEN D) for flag = 0.

The library syntax is GEN nfsplitting0(GEN P, GEN d = NULL, long fl).

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] (default) or simply g (flag = 1), 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

* Allombert's galoissubfields when nf is Galois (with weakly supersolvable Galois group).

* Klüners's or van Hoeij-Klüners-Novocin algorithm in the general case. The latter runs in polynomial time and is generally superior unless there exists a small unramified prime p such that pol has few irreducible factors modulo p.

An input of the form [nf, fa] is also allowed, where fa is the factorisation of nf.pol over nf, expressed as a famat of polynomials with coefficients in the variable of nf, in which case the van Hoeij-Klüners-Novocin algorithm is used.

  ? pol = x^4 - x^3 - x^2 + x + 1;
  ? nfsubfields(pol)
  %2 = [[x, 0], [x^2 - x + 1, x^3 - x^2 + 1], [x^4 - x^3 - x^2 + x + 1, x]]
  ? nfsubfields(pol,,1)
  %2 = [x, x^2 - x + 1, x^4 - x^3 - x^2 + x + 1]
  ? y=varhigher("y"); fa = nffactor(pol,subst(pol,x,y));
  ? #nfsubfields([pol,fa])
  %5 = 3

The library syntax is GEN nfsubfields0(GEN pol, long d, long flag). Also available is GEN nfsubfields(GEN nf, long d), corresponding to flag = 0.

Computes the maximal CM subfield of nf. Returns 0 if nf does not have a CM subfield, otherwise returns [g,h] (default) or g (flag = 1) where g is an absolute equation and h expresses a root of g in terms of the generator of nf. Moreover, the CM involution is given by X mod g(X) ⟼ -X mod g(X), i.e. X mod g(X) is a totally imaginary element.

An input of the form [nf, fa] is also allowed, where fa is the factorisation of nf.pol over nf, and nf is also allowed to be a monic defining polynomial for the number field.

  ? nf = nfinit(x^8 + 20*x^6 + 10*x^4 - 4*x^2 + 9);
  ? nfsubfieldscm(nf)
  %2 = [x^4 + 4480*x^2 + 3612672, 3*x^5 + 58*x^3 + 5*x]
  ? pol = y^16-8*y^14+29*y^12-60*y^10+74*y^8-48*y^6+8*y^4+4*y^2+1;
  ? fa = nffactor(pol, subst(pol,y,x));
  ? nfsubfieldscm([pol,fa])
  %5 = [y^8 + ... , ...]

The library syntax is GEN nfsubfieldscm(GEN nf, long flag).

Computes the list of maximal subfields of nf. The result is a vector as in nfsubfields.

An input of the form [nf, fa] is also allowed, where fa is the factorisation of nf.pol over nf, and nf is also allowed to be a monic defining polynomial for the number field.

The library syntax is GEN nfsubfieldsmax(GEN nf, long flag).

Let nf be attached to a number field K, let v be a vector of elements of K, not all of them 0, seen as element of the projective space of dimension #v - 1. Returns the absolute logarithmic Weil height of that element, which does not depend on the number field used to compute it.

When the entries of v are rational, the height is log(normlp(v / content(v), oo)).

  ? v = [1, 2, -3, 101]; Q = nfinit(x); Qi = nfinit(x^2 + 1);
  ? exponent(nfweilheight(Q, v) - log(101))
  %2 = -125
  ? exponent(nfweilheight(Qi, v) - log(101))
  %3 = -125

The library syntax is GEN nfweilheight(GEN nf, GEN v, long prec).

P and Q being squarefree polynomials in ℤ[X] in the same variable, outputs the simple factors of the étale ℚ-algebra A = ℚ(X, Y) / (P(X), Q(Y)). The factors are given by a list of polynomials R in ℤ[X], attached to the number field ℚ(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. In this case, there will be a single factor R if and only if the number fields defined by P and Q are linearly disjoint (their intersection is ℚ).

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]).

The binary digits of flag mean

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 ℚ(X)/(R). Finally, k is a small integer such that b + ka = X modulo R.

2: assume that P and Q define number fields which are linearly disjoint: both polynomials are irreducible and the corresponding number fields have no common subfield besides ℚ. This allows to save a costly factorization over ℚ. In this case return the single simple factor instead of a vector with one element.

A compositum is often defined by a complicated polynomial, which it is advisable to reduce before further work. Here is an example involving the field ℚ(ζ₅, 5^1/5):

  ? L = polcompositum(x^5 - 5, polcyclo(5), 1); \\  list of [R,a,b,k]
  ? [R, a] = L[1];  \\  pick the single factor, extract R,a (ignore b,k)
  ? R               \\  defines the compositum
  %3 = 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^5 - 5         \\  a fifth root of 5
  %4 = 0
  ? [T, X] = polredbest(R, 1);
  ? T     \\  simpler defining polynomial for ℚ[x]/(R)
  %6 = x^20 + 25*x^10 + 5
  ? X     \\   root of R in ℚ[y]/(T(y))
  %7 = Mod(-1/11*x^15 - 1/11*x^14 + 1/22*x^10 - 47/22*x^5 - 29/11*x^4 + 7/22,\
  x^20 + 25*x^10 + 5)
  ? a = subst(a.pol, 'x, X)  \\  a in the new coordinates
  %8 = Mod(1/11*x^14 + 29/11*x^4, x^20 + 25*x^10 + 5)
  ? a^5 - 5
  %9 = 0

In the above example, x⁵-5 and the 5-th cyclotomic polynomial are irreducible over ℚ; they have coprime degrees so define linearly disjoint extensions and we could have started by

  ? [R,a] = polcompositum(x^5 - 5, polcyclo(5), 3); \\  [R,a,b,k]

The library syntax is GEN polcompositum0(GEN P, GEN Q, long flag). Also available are GEN compositum(GEN P, GEN Q) (flag = 0) and GEN compositum2(GEN P, GEN Q) (flag = 1).

Galois group of the nonconstant polynomial T ∈ ℚ[X]. In the present version 2.19.0, T must be irreducible and the degree d of T must be less than or equal to 7. If the galdata package has been installed, degrees 8, 9, 10 and 11 are also implemented. By definition, if K = ℚ[x]/(T), this computes the action of the Galois group of the Galois closure of K on the d distinct roots of T, up to conjugacy (corresponding to different root orderings).

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_d, 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 the numbering of the group among all transitive subgroups of S_d, 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). Specifically, for polynomials of degree d ≤ 7, the groups are coded as follows, using standard notations

In degree 1: S₁ = [1,1,1].

In degree 2: S₂ = [2,-1,1].

In degree 3: A₃ = C₃ = [3,1,1], S₃ = [6,-1,2].

In degree 4: C₄ = [4,-1,1], V₄ = [4,1,2], D₄ = [8,-1,3], A₄ = [12,1,4], S₄ = [24,-1,5].

In degree 5: C₅ = [5,1,1], D₅ = [10,1,2], M₂₀ = [20,-1,3], A₅ = [60,1,4], S₅ = [120,-1,5].

In degree 6: C₆ = [6,-1,1], S₃ = [6,-1,2], D₆ = [12,-1,3], A₄ = [12,1,4], G₁₈ = [18,-1,5], A₄ x C₂ = [24,-1,6], S₄⁺ = [24,1,7], S₄⁻ = [24,-1,8], G₃₆⁻ = [36,-1,9], G₃₆⁺ = [36,1,10], S₄ x C₂ = [48,-1,11], A₅ = PSL₂(5) = [60,1,12], G₇₂ = [72,-1,13], S₅ = PGL₂(5) = [120,-1,14], A₆ = [360,1,15], S₆ = [720,-1,16].

In degree 7: C₇ = [7,1,1], D₇ = [14,-1,2], M₂₁ = [21,1,3], M₄₂ = [42,-1,4], PSL₂(7) = PSL₃(2) = [168,1,5], A₇ = [2520,1,6], S₇ = [5040,-1,7].

For compatibility with older PARI/GP versions, when new_galois_format is set to 0, the numbering is different for d ≤ 7, the groups are coded as follows, using standard notations:

In degree 1: S₁ = [1,1,1].

In degree 2: S₂ = [2,-1,1].

In degree 3: A₃ = C₃ = [3,1,1], S₃ = [6,-1,1].

In degree 4: C₄ = [4,-1,1], V₄ = [4,1,1], D₄ = [8,-1,1], A₄ = [12,1,1], S₄ = [24,-1,1].

In degree 5: C₅ = [5,1,1], D₅ = [10,1,1], M₂₀ = [20,-1,1], A₅ = [60,1,1], S₅ = [120,-1,1].

In degree 6: C₆ = [6,-1,1], S₃ = [6,-1,2], D₆ = [12,-1,1], A₄ = [12,1,1], G₁₈ = [18,-1,1], S₄⁻ = [24,-1,1], A₄ x C₂ = [24,-1,2], S₄⁺ = [24,1,1], G₃₆⁻ = [36,-1,1], G₃₆⁺ = [36,1,1], S₄ x C₂ = [48,-1,1], A₅ = PSL₂(5) = [60,1,1], G₇₂ = [72,-1,1], S₅ = PGL₂(5) = [120,-1,1], A₆ = [360,1,1], S₆ = [720,-1,1].

In degree 7: C₇ = [7,1,1], D₇ = [14,-1,1], M₂₁ = [21,1,1], M₄₂ = [42,-1,1], PSL₂(7) = PSL₃(2) = [168,1,1], A₇ = [2520,1,1], S₇ = [5040,-1,1].

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 GEN polgalois(GEN T, long prec). GEN polgalois0(GEN T, long ngf, long prec) where ngf is either 0 for the traditional format and 1 for the new Galois format. Alternatively, in library mode, to force the use of the older format for compatibility purpose, set the global variable new_galois_format to 0.

This function is deprecated, use polredbest instead. Let T be a separable polynomial with rational coefficients and consider the étale algebra A = ℚ[x]/(T). Finds polynomials with reasonably small coefficients defining subalgebras of A. One of the polynomials always defines ℚ, hence has degree 1. If T is irreducible then another always defines the same number field as T.

All T accepted by nfinit are also allowed here; in particular, the format [T, listP] is recommended, e.g. with listP = 10⁵ or a vector containing all ramified primes. Otherwise, the maximal order of ℚ[x]/(T) must be computed.

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. This flag is deprecated, the [T, listP] format is generic and more flexible.

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

  ? M = polred(x^4 + 8, 2)
  %1 =
  [           1         x - 1]
  
  [ 1/2*x^2 + 1 x^2 - 2*x + 3]
  
  [-1/2*x^2 + 1 x^2 - 2*x + 3]
  
  [     1/2*x^2       x^2 + 2]
  
  [     1/4*x^3       x^4 + 2]
  ? minpoly(Mod(M[4,1], x^4+8))
  %2 = x^2 + 2

The library syntax is GEN polred0(GEN T, long flag). Also available are GEN polred(GEN T) (flag = 0) and GEN polred2(GEN T) (flag = 2).

Let T be a separable polynomial with rational coefficients and consider the étale algebra A = ℚ[x]/(T). Returns a canonical defining polynomial P defining A ~ Q[x]/(P), such that the sum of the squares of the modulus of the roots (i.e. the T₂-norm) is minimal. This is mostly useful when T is irreducible and A is a number field, else you should probably first factor T, thereby factoring A as a product of number fields.

Different T defining isomorphic algebras will yield the same P. All T accepted by nfinit are also allowed here, e.g. nonmonic polynomials, or pairs [T, listP] specifying that a nonmaximal order may be used. For convenience, any number field structure (nf, bnf,...) can also be used instead of T.

  ? polredabs(x^2 + 16)
  %1 = x^2 + 1
  ? K = bnfinit(x^2 + 16); polredabs(K)
  %2 = x^2 + 1

Warning 1. Using a t_POL T requires computing and fully factoring the discriminant d_K of the maximal order which may be very hard. You can use the format [T, listP], where listP encodes a list of known coprime divisors of disc(T) (see ??nfbasis), to help the routine, thereby replacing this part of the algorithm by a polynomial time computation But this may only compute a suborder of the maximal order, when the divisors are not squarefree or do not include all primes dividing d_K. The routine attempts to certify the result independently of this order computation as per nfcertify: we try to prove that the computed order is maximal. If the certification fails, the routine then fully factors the integers returned by nfcertify. You can also use polredbest to avoid this factorization step; in this case, the result is small but no longer canonical.

Warning 2. Apart from the factorization of the discriminant of T, this routine runs in polynomial time for a fixed degree. But the complexity is exponential in the degree: this routine may be exceedingly slow. If you do not need a canonical polynomial, the function polredbest is in general much faster (it runs in polynomial time), and tends to return polynomials with smaller discriminants.

The binary digits of flag mean

1: outputs a two-component row vector [P,a], where P is the default output and Mod(a, P) is a root of the original T.

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

16: (OBSOLETE) Possibly use a suborder of the maximal order, without attempting to certify the result as in Warning 1. This makes polredabs behave like polredbest. Just use the latter.

  ? T = x^16 - 136*x^14 + 6476*x^12 - 141912*x^10 + 1513334*x^8 \
        - 7453176*x^6 + 13950764*x^4 - 5596840*x^2 + 46225
  ? T1 = polredabs(T); T2 = polredbest(T);
  ? [ norml2(polroots(T1)), norml2(polroots(T2)) ]
  %3 = [88.0000000, 120.000000]
  ? [ sizedigit(poldisc(T1)), sizedigit(poldisc(T2)) ]
  %4 = [75, 67]

The precise definition of the output of polredabs is as follows.

* Consider the finite list of characteristic polynomials of primitive elements of K that are in ℤ_K and minimal for the T₂ norm; now remove from the list the polynomials whose discriminant do not have minimal absolute value. Note that this condition is restricted to the original list of polynomials with minimal T₂ norm and does not imply that the defining polynomial for the algebra with smallest discriminant belongs to the list !

* To a polynomial P(x) = xⁿ +...+ a_n ∈ ℝ[x] we attach the sequence S(P) given by |a₁|, a₁,..., |a_n|, a_n. Order the polynomials P by the lexicographic order on the coefficient vectors S(P). Then the output of polredabs is the smallest polynomial in the above list for that order. In other words, the monic polynomial which is lexicographically smallest with respect to the absolute values of coefficients, favouring negative coefficients to break ties, i.e. choosing x³-2 rather than x³+2.

The library syntax is GEN polredabs0(GEN T, long flag). Instead of the above hardcoded numerical flags, one should use an or-ed combination of

* nf_PARTIALFACT (OBSOLETE): possibly use a suborder of the maximal order, without attempting to certify the result.

* nf_ORIG: return [P, a], a is a root of T, given as a t_POLMOD modulo P.

* nf_RAW: return [P, b], where Mod(b, T) is a root of P. The algebraic integer b is the raw result produced by the small vectors enumeration in the maximal order; P was computed as the characteristic polynomial of Mod(b, T). The root a of T as in nf_ORIG (a t_POLMOD modulo P) is modreverse(Mod(b, T)).

* nf_ALL: return a vector of results of the above form, for all polynomials of minimal T₂-norm.

Let T be a separable polynomial with rational coefficients and consider the étale algebra A = ℚ[X]/(T). Finds a polynomial P with reasonably small coefficients defining the same algebra A ~ Q[X]/(P). This is mostly useful when T is irreducible and A is a number field, else you should probably first factor T, thereby factoring A as a product of number fields.

All T accepted by nfinit are also allowed here (e.g. nonmonic polynomials, nf, bnf, [T,Z_K_basis]). Contrary to polredabs, this routine runs in polynomial time, but it offers no guarantee as to the minimality of its result.

This routine computes an LLL-reduced basis for an order in ℚ[X]/(T), then examines small linear combinations of the basis vectors, computing their characteristic polynomials. It returns the separable polynomial P of smallest discriminant, the one with lexicographically smallest abs(Vec(P)) in case of ties. This is a good candidate for subsequent number field computations since it guarantees that the denominators of algebraic integers, when expressed in the power basis, are reasonably small. With no claim of minimality, though.

It can happen that iterating this functions yields better and better polynomials, until it stabilizes:

  ? \p5
  ? P = X^12+8*X^8-50*X^6+16*X^4-3069*X^2+625;
  ? poldisc(P)*1.
  %2 = 1.2622 E55
  ? P = polredbest(P);
  ? poldisc(P)*1.
  %4 = 2.9012 E51
  ? P = polredbest(P);
  ? poldisc(P)*1.
  %6 = 8.8704 E44

In this example, the initial polynomial P is the one returned by polredabs, and the last one is stable.

If flag = 1: outputs a two-component row vector [P,a], where P is the default output and a, a t_POLMOD modulo P, is a root of the original T.

  ? [P,a] = polredbest(x^4 + 8, 1)
  %1 = [x^4 + 2, Mod(x^3, x^4 + 2)]
  ? charpoly(a)
  %2 = x^4 + 8

In particular, the map ℚ[x]/(T) → ℚ[x]/(P), x ⟼ a defines an isomorphism of ℚ-algebras, which can be computed as

    subst(lift(Q), 'x, a)

if Q is a t_POLMOD modulo T; b = modreverse(a) returns a t_POLMOD giving the inverse of the above map (which should be useless since ℚ[x]/(P) provides a priori a better representation for the algebra and its elements).

The library syntax is GEN polredbest(GEN T, long flag).

This function is obsolete, use polredbest.

The library syntax is GEN polredord(GEN x).

Applies a random Tschirnhausen transformation to the polynomial x, which is assumed to be nonconstant 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 GEN tschirnhaus(GEN x).

Relative version of polredabs. Given an irreducible monic polynomial pol with coefficients in the maximal order of nf, finds a canonical relative polynomial defining the same field, hopefully with small coefficients. Note that the equation is only canonical for a fixed nf, using a different defining polynomial in the nf structure will produce a different relative equation.

The binary digits of flag correspond to 1: add information to convert elements to the new representation, 2: absolute polynomial, instead of relative, 16: possibly use a suborder of the maximal order. More precisely:

0: default, return P

1: returns [P,a] where P is the default output and a, a t_POLMOD modulo P, is a root of pol.

2: returns Pabs, an absolute, instead of a relative, polynomial. This polynomial is canonical and does not depend on the nf structure. Same as but faster than

    polredabs(rnfequation(nf, pol))

3: returns [Pabs,a,b], where Pabs is an absolute polynomial as above, a, b are t_POLMOD modulo Pabs, roots of nf.pol and pol respectively.

16: (OBSOLETE) possibly use a suborder of the maximal order. This makes rnfpolredabs behave as rnfpolredbest. Just use the latter.

Warning. The complexity of rnfpolredabs is exponential in the absolute degree. The function rnfpolredbest runs in polynomial time, and tends to return polynomials with smaller discriminants. It also supports polynomials with arbitrary coefficients in nf, neither integral nor necessarily monic.

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

Relative version of polredbest. Given a polynomial pol with coefficients in nf, finds a simpler relative polynomial P defining the same field. As opposed to rnfpolredabs this function does not return a smallest (canonical) polynomial with respect to some measure, but it does run in polynomial time.

The binary digits of flag correspond to 1: add information to convert elements to the new representation, 2: absolute polynomial, instead of relative. More precisely:

0: default, return P

1: returns [P,a] where P is the default output and a, a t_POLMOD modulo P, is a root of pol.

2: returns Pabs, an absolute, instead of a relative, polynomial. Same as but faster than

    rnfequation(nf, rnfpolredbest(nf,pol))

3: returns [Pabs,a,b], where Pabs is an absolute polynomial as above, a, b are t_POLMOD modulo Pabs, roots of nf.pol and pol respectively.

  ? K = nfinit(y^3-2); pol = x^2 +x*y + y^2;
  ? [P, a] = rnfpolredbest(K,pol,1);
  ? P
  %3 = x^2 - x + Mod(y - 1, y^3 - 2)
  ? a
  %4 = Mod(Mod(2*y^2+3*y+4,y^3-2)*x + Mod(-y^2-2*y-2,y^3-2),
           x^2 - x + Mod(y-1,y^3-2))
  ? subst(K.pol,y,a)
  %5 = 0
  ? [Pabs, a, b] = rnfpolredbest(K,pol,3);
  ? Pabs
  %7 = x^6 - 3*x^5 + 5*x^3 - 3*x + 1
  ? a
  %8 = Mod(-x^2+x+1, x^6-3*x^5+5*x^3-3*x+1)
  ? b
  %9 = Mod(2*x^5-5*x^4-3*x^3+10*x^2+5*x-5, x^6-3*x^5+5*x^3-3*x+1)
  ? subst(K.pol,y,a)
  %10 = 0
  ? substvec(pol,[x,y],[a,b])
  %11 = 0

The library syntax is GEN rnfpolredbest(GEN nf, GEN pol, long flag).

Given an nf structure attached to a number field K, as output by nfinit, and a monic irreducible polynomial T in ℤ_K[x] defining a relative extension L = K[x]/(T), computes the relative discriminant of L and a pseudo-basis (A,J) for the maximal order ℤ_L viewed as a ℤ_K-module. This is output as a vector [A,J,D,d], where D is the relative ideal discriminant and d is the relative discriminant considered as an element of K^*/{K^*}².

  ? K = nfinit(y^2+1);
  ? [A,J,D,d] = rnfpseudobasis(K, x^2+y);
  ? A
  %3 =
  [1 0]
  
  [0 1]
  
  ? J
  %4 = [1, 1]
  ? D
  %5 = [0, -4]~
  ? d
  %6 = [0, -1]~

Huge discriminants, helping rnfdisc. The format [T,B] is also accepted instead of T and produce an order which is maximal at all prime ideals specified by B, see ??rnfinit.

  ? p = 585403248812100232206609398101;
  ? q = 711171340236468512951957953369;
  ? T = x^2 + 3*(p*q)^2;
  ? [A,J,D,d] = V = rnfpseudobasis(K, T); D
  time = 22,178 ms.
  %10 = 3
  ? [A,J,D,d] = W = rnfpseudobasis(K, [T,100]); D
  time = 5 ms.
  %11 = 3
  ? V == W
  %12 = 1
  ? [A,J,D,d] = W = rnfpseudobasis(K, [T, [3]]); D
  %13 = 3
  ? V == W
  %14 = 1

In this example, the results are identical since D ∩ ℤ factors over primes less than 100 (and in fact, over 3). Had it not been the case, the order would have been guaranteed maximal at primes 𝔭 | p for p ≤ 100 only (resp. 𝔭 | 3). And might have been nonmaximal at any other prime ideal 𝔭 such that 𝔭² divided D.

The library syntax is GEN rnfpseudobasis(GEN nf, GEN T).

Given a nf attached to a number field K and a projective module M given by a pseudo-matrix, returns a 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. If M is a polynomial with coefficients in K, replace it by the pseudo-matrix returned by rnfpseudobasis and return the four-component row vector [A,I,D,d] where (A,I) are as before and (D,d) are discriminants as returned by rnfpseudobasis. The ideal class of the last ideal of I is well defined; it is the Steinitz class of M (its image in SK₀(ℤ_K)).

The library syntax is GEN rnfsteinitz(GEN nf, GEN M).

cyc being a vector of positive integers giving the cyclic components for a finite Abelian group G (or any object which has a .cyc method), outputs the list of subgroups of G. Subgroups are given as HNF left divisors of the SNF matrix corresponding to G.

If flag = 0 (default) and cyc is a bnr structure output by bnrinit, gives only the subgroups whose conductor is the modulus bnr.mod. Otherwise, all subgroups are given.

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 ℚ(ζ₁₂₀), 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 bnrclassfield.)

Warning. This function requires factoring the exponent of G. If you are only interested in subgroups of index n (or dividing n), you may considerably speed up the function by computing the subgroups of G/Gⁿ, whose cyclic components are apply(x- > gcd(n,x), C) (where C gives the cyclic components of G). If you want the bnr variant, now is a good time to use bnrinit(,,, n) as well, to directly compute the ray class group modulo n-th powers.

The library syntax is GEN subgrouplist0(GEN cyc, GEN bound = NULL, long flag).