THE MONTES PACKAGE WEB PAGE

Fast computation of integral basis of number fields

Jordi Guàrdia, Jesús Montes & Enric Nart

You can download the package here (v. 3.0)

You can download a pdf file with this documentation here

1. PRESENTATION

2. COMPUTATION OF INTEGRAL BASES

3. GENERATORS OF PRIME IDEALS

4. FOLLOWING THE COMPUTATIONS

5. CONSTRUCTION OF EXAMPLES

6. NOTES ON THE IMPLEMENTATION & SUPPORT

7. DATA FOR THE EXAMPLES IN THE PAPER “Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields”

8. DATA FOR THE EXAMPLES IN THE PAPER “Higher Newton polygons and integral bases”

9. HOW TO CITE THE PROGRAM

10. REFERENCES

11. CHANGE LOG

PRESENTATION

Montes package computes integral bases of number fields. Given a number field defined by an irreducible monic polynomial , and the list S of prime divisors of the discriminant of , the program computes:

1. An integral basis of the ring of integers

2. The index of .

3. The factorization of the ideal in for every prime

The algorithm has excellent heuristic running times and very low memory requirements, thus giving the possibility to work with polynomials of huge index and/or large degree. It takes only a few seconds to find the maximal order of a number field of degree about 300.

The algorithms used in the package are described in [GMN 08], [GMN 08a] and [GMN 09]. The algorithm for the determination of the maximal order depends on a conjecture not yet proven. Anyway, the output of the package is unconditional: the program checks whether the returned basis generates a maximal order and warns the user if the test fails. (Of course, we have not found any counterexample to our conjecture, after checking thousands of examples!)

COMPUTATION OF INTEGRAL BASES

In order to use our program follow the next steps:

0. Download the package.

1. Attach the package to Magma:

> Attach(“/yourdirectory/montes.m”);

2. Define the irreducible polynomial determining your number field:

> Zx<x>:=PolynomialRing(Integers());

> pol:=x^21+193*x^14+4*x^13+12416*x^7+512*x^6+266240;

3. Find the primes dividing the discriminant of the polynomial:

> primes:=PrimeDivisors(Discriminant(pol));

4. Compute an integral basis, the factorization of the index and the decomposition of the ramified primes:

> basis,index,ramifiedideals:=HNIntegralBasis(pol,primes);

The integral basis is given as a list of elements of the number field determined by . If you define this field in Magma by means of

> K<a>:=NumberField(pol: Global:=true);

> basis;

you will see the elements of the basis as polynomials in the variable a. The basis is given in Hermite normal form.

The index is returned in factored form, as a list of pairs [prime,exponent]:

> index;

[ [ 2, 80 ], [ 5, 0 ], [ 7, 0 ], [ 13, 0 ], [ 175594403, 0 ], [ 1907182975124798797, 0 ],

[ 26340120745682237993437, 0 ]]

Finally, the decomposition of the primes that ramify in is returned as a list of pairs [*p, {[e1,f1],…,[eg,fg]}*], each one giving the ramification index and residual degree of one of the primes in above the specified rational prime:

> ramifiedideals;

[ [* 2, [[ 1, 1 ], [ 1, 3 ], [ 1, 3 ], [ 7, 2 ]]*], [* 5, [ [ 6, 1 ], [ 1, 7 ], [ 1, 8 ]]*], [* 7, [ [ 7, 1 ], [ 1, 2 ], [ 1, 4 ], [ 1, 8 ]]*],

[* 13, [ [ 6, 1 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ]]*], [* 175594403, [ [ 2, 1 ], [ 1, 5 ], [ 1, 6 ], [ 1, 8 ]]*],

[* 1907182975124798797, [ [ 1, 1 ], [ 2, 1 ], [ 1, 2 ], [ 1, 2 ], [ 1, 2 ], [ 1, 4 ], [ 1, 8 ]]*],

[* 26340120745682237993437, [ [ 1, 1 ], [ 2, 1 ], [ 1, 9 ], [ 1, 9 ]]*] ]

See below how to compute generators for these ideals.

You can put in the list primes any set of primes, and the output will be an -maximal order of. This might be useful when we do not have the full factorization of the discriminant of . For instance, you can compute a 2-integral basis of typing:

>basis,index,ramifiedideals:=HNIntegralBasis(pol,[2]);

The algorithm has a very good performance in comparison with the standard computational number theory packages. Here you have an example:

> time basis,index,ramifiedideals:=HNIntegralBasis(x^32+16,[2]);

Time: 0.031

> time OK:=MaximalOrder(x^32+16: Ramification:=[2]);

Time: 3.307

This second example goes further:

> time i,b,f:=HNIntegralBasis(x^800+2^50*x^600+2^100*x^400+2^200,[2,5,257]);

Time: 126.060

PARI takes more than 2 hours and 32Gb of memory to make this computation!

Next example goes out of reach for the usual software:

> time i,b,f:= HNIntegralBasis(x^1600+2^50*x^1200+2^100*x^800+2^200,[2,5,257]);

Time:

In this situation, one can try to compute local bases, for whose computation the algorithm is specifically designed:

> time i,b,ids:= HNIntegralBasis (x^1600+2^50*x^1200+2^100*x^800+2^200,[2]);

Time: 1448.640

The running time is dominated by the computation of the Hermite forms of the local p-integral bases, which took 1426 seconds.

GENERATORS OF THE PRIME IDEALS

You can use the HNIntegralBasis routine to completely factor a prime in ZK, by means of the option Generators:=true :

> index, basis, factorization:=HNIntegralBasis(x^6+24,[2]: Generators:=true);

> factorization;

[

rec<recformat<prime: IntegerRing(), generator: RngUPolElt, e: IntegerRing(),

f: IntegerRing()> |

prime := 2,

generator := 7/4*a^5 + 7/4*a^4 + 1,

e := 2,

f := 1

rec<recformat<prime: IntegerRing(), generator: RngUPolElt, e: IntegerRing(),

f: IntegerRing()> |

prime := 2,

generator := 7/4*a^4 + 3/2*a^3 + 3/2*a^2 + 1,

e := 2,

f := 2

]

These records contain fields for the ramification index (e), residual degree (f) and generators (generator) for the ideal. In this case we see that the ideal generated by 2 factors as the product of two prime ideals and , with and , and these ideals are

and .

The computation of the generators of the ideals can take much time for polynomials of very high degree.

FOLLOWING THE COMPUTATIONS

If you want to follow accurately the flow of the program, you can set the verbose flag "montestalk” to levels 1 to 5. (You should read [GMN 08], [GMN 08a] to understand all the output information.). Setting “montestalk” level to 1, the program displays running times of different parts of the algorithm, while level 5 gives almost all the computed information.

> SetVerbose("montestalk",3);

> b,i,f:=HNIntegralBasis((x^4 + x^3 + 17*x^2 + 16*x + 32)^2+4,[2]);

++++++++++++++++++++++++++++++++++++++++++++++++

Analyzing type of order 1

Sides of Newton polygon: [

[ -1, 0, 2, 2, 0 ]

]

Added 2 to the index

----------------------

Annalyzing side [ -1, 0, 2, 2, 0 ]

Slope: -1

Origin: ( 0 , 2 )

End point: ( 2 , 0 )

----------------------

Monic Residual Polynomial= Y0^2 + z0 + 1

The residual polynomial has 1 factors

----------------------

Analyzing a factor of the residual polynomial

psi= Y0 + z0

----------------------

Refining

cuttingslope= -1

***********

++++++++++++++++++++++++++++++++++++++++++++++++

Analyzing type of order 1

Sides of Newton polygon: [

[ -3/2, 0, 3, 2, 0 ]

]

Added 0 to the index

----------------------

Annalyzing side [ -3/2, 0, 3, 2, 0 ]

Slope: -3/2

Origin: ( 0 , 3 )

End point: ( 2 , 0 )

----------------------

Monic Residual Polynomial= Y0 + z0 + 1

The residual polynomial has 1 factors

----------------------

Analyzing a factor of the residual polynomial

psi= Y0 + z0 + 1

----------------------

Found a factor in order 1

++++++++++++++++++++++++++++++++++++++++++++++++

Analyzing type of order 1

Sides of Newton polygon: [

[ -1/2, 0, 2, 4, 0 ]

]

Added 2 to the index

----------------------

Annalyzing side [ -1/2, 0, 2, 4, 0 ]

Slope: -1/2

Origin: ( 0 , 2 )

End point: ( 4 , 0 )

----------------------

Monic Residual Polynomial= Y0^2 + 1

The residual polynomial has 1 factors

----------------------

Analyzing a factor of the residual polynomial

psi= Y0 + 1

----------------------

Proceeding to higher order

***********

++++++++++++++++++++++++++++++++++++++++++++++++

Analyzing type of order 2

Sides of Newton polygon: [

[ -3/2, 0, 7, 2, 4 ]

]

Added 1 to the index

----------------------

Annalyzing side [ -3/2, 0, 7, 2, 4 ]

Slope: -3/2

Origin: ( 0 , 7 )

End point: ( 2 , 4 )

----------------------

Monic Residual Polynomial= Y1 + 1

The residual polynomial has 1 factors

----------------------

Analyzing a factor of the residual polynomial

psi= Y1 + 1

----------------------

Found a factor in order 2

All the types are completed

The index is 5

Ellapsed time: 0

Time reducing basis coefficients: 0

Max Valuation: 9/4 6

Total time for determining the types: 0

Time to find Hermite Form: 0

Time to simplify Hermite Form: 0

Time to find second Hermite Form: 0

CONSTRUCTION OF EXAMPLES

The package is based on the construction of types, a data structure introduced in [GMN 08], [GMN 08a]. The package performs basically two inverse tasks: the determination of the types associated to a polynomial and the computation of polynomial representing a given type.

While the first task can be used without any knowledge of the algorithm (see the following section), the constructive application requires certain knowledge of the concepts and terminology introduced in [GMN 08], [GMN 08a], so that a basic understanding of both papers is recommended for constructing examples.

Types and their construction

Automatic (random) creation of types

Combining polynomials with given types at different primes

Formatted output

Types and their construction

Suppose that you want to construct a number field K where , where is a prime ideal with residual degree 3. The easiest way to do this is choosing an irreducible cubic polynomial over , lifting to and then construct a proper type. We let Magma choose the polynomial:

> FY<y>:= PolynomialRing(GF(2));

> psi:=ZX!RandomPrimePolynomial(FY,3);psi;

y^3 + y + 1

We must initialize the type:

> t,Y,z:=InitializeType(2,x);

This command returns the type t, and two lists Y, z. The list z contain a root of every residual polynomial in the type, while the list Y contains the indeterminate of the polynomial rings over the finite fields defined by these residual polynomials. They are useful for enlarging the type, as you will see in a moment.

Now we create a representative of the order one type given by the chosen polynomial and slope 5=5/3 with:

> EnlargeType(5,3,y^3+y+1,~t,~Y,~z);

A number field satisfying our demand is given by the polynomial:

> t[1]`Pol;

x^15 + 64*x^5 + 512

Of course, this is a very simple example. The function EnlargeType allows the recursive construction of higher order types and their representatives. Its general usage is

>EnlargeType(e,h,psi, ~t, ~Y,~z);

where Y, Z are as before and t is a type of order r. This command computes a representative of the order r+1 type having a Newton polygon with a unique side of slope e/h (note that e and h must be co-prime) and residual polynomial psi, and enlarges t adding these values to it. For instance, we could enlarge the type before with:

> EnlargeType(3,2,Y[2]^2+z[2]*Y[2]+z[1],~t,~Y,~z);

> t[1]`Pol;

x^90 + 384*x^80 + 3072*x^75 + 61440*x^70 + 983040*x^65 + 9175040*x^60 +125829120*x^55 + 4194304*x^54 + 1258291200*x^50 + 10737418240*x^45 +805306368*x^44 + 103079215104*x^40 + 6442450944*x^39 + 773094113280*x^35 +51539607552*x^34 + 5222680231936*x^30 + 824633720832*x^29 +36283883716608*x^25 + 4398046511104*x^24 + 197912092999680*x^20 +26388279066624*x^19 + 914793674309632*x^15 + 211106232532992*x^14 +4222124650659840*x^10 + 562949953421312*x^9 + 1125899906842624*x^8 +13510798882111488*x^5 + 18014398509481984

Automatic (random) creation of types

A simple way to randomly enlarge a type t is the use of the commands

> psi:=RandomPrimePolynomial(PolynomialRing( t[n]`Fq),d);

> EnlargeType(e,h,psi, ~t, ~Y,~z);

Where n=#t is the order of t, and d is the degree of the desired residual polynomial. Since this can be a bit boring if one wants a type of high order, the package includes a function to create a type of any given order from the scratch:

> t:=CreateRandomType(p,r);

This command creates a type of order r for the prime p. All the parameters involved along the process, that is, all the e’s, h’s and f’s are randomly chosen small integers. After the command is executed, we have the type t and a representative of it:

> pol:=t[r]`Pol;

> a,b,c:=montes(pol,p);

The package includes an extended version of CreateRandomType, which is useful to determine a polynomial having several different types:

> pol:=CreateRandomMultipleTypePolynomial(p,k,r,s);

This command generates a list of k random types of order r, and tries to build a polynomial having all these types. The method to build this polynomial is to pick representatives of the types, multiply them altogether and sum p^s to this product until you get an irreducible polynomial. It is the user’s responsibility to take s big enough to assure that the obtained polynomial as exactly the r types randomly created.

Combining polynomials with given types at different primes

In case you want to construct a number field specifying the type of factorization of several different prime numbers, the following function will be useful:

> pol:=CombinePolynomialsWithDifferentPrimes(f1,p1,f2,p2,k);

The input of this command are two polynomials f1,f2 and two co-prime numbers p1,p2 and an integer k. The function computes a polynomial pol which is congruent to fi (mod pi^k), i=1,2.

Formatted output

We have included a number of functions to write polynomials involved in a type in a pretty format. There are two possible output formats: TeX and Magma. These functions are not intended to make your life wonderful: they are only a small help to avoid you typing a huge amount of numbers.

The basic formatting functions are ExpandPolynomialTex and ExpandPolynomialMagma. Both of them take a polynomial and a type on input, and generate an output string containing the multiple f–adic expansion of the polynomial in terms of the f–components of the type. In the first case, the output string can be inserted into a TeX file, while in the second case you can use the output as a Magma command. Be prepared to get some ugly expressions!

> t:=CreateType(5,3);

> pol:=x^125+5^40;

> ExpandPolynomialTeX(pol,t);

There are specific functions for writing the expansion of the the f–components of a type in terms of the previous f’s. They are ExpandPhiTeX(k,t) and ExpandPhiMagma(k,t) (which expand in terms of ), and ExpandAllPhiTeX(t) and ExpandAllPhiMagma(t), which write the expansions of all the f–components of the type t.

DATA FOR THE EXAMPLES IN THE PAPER “Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields”

Example 5.1

> f:= x^12-588*x^10+476*x^9+130095*x^8-172872*x^7-12522636*x^6 + 24745392*x^5+486721116*x^4-1583408736*x^3-641009376*x^2+ 10978063488*x+59914669248;

Example 5.2

>f:=(x^3+x+5)^50+2^89*(x^3+x+5)^25+2^178;

Example 6.1

Here you have a file with the definition of the polynomials

Example 6.2

The table was constructed using the following function

> function timing(k,p)

> pol:=(x^2+x+1)^2-p^(2*k+1);

> a,b,c:=montes(pol,p);

> return b;

> end function;

Example 6.3

The polynomial is computed with the following code:

> p1:=x^2+13^2*x+13^4*3;

> p2:=p1^3+13^18*2;

> p3:=p2^10+13^89*(x+13^2)*p2^5+13^176*p1;

> p4:=p3^2+13^248*(12*(x+13^2)*p1+13^8)*p2^6+13^335*12*p1^2*p2;

> tablefj:=&*[Evaluate(p4,x+j): j in [0..12]]+13^5000;

> for j:=1 to 13 do time a,b,c:=montes(tablefj[j],13); end for;

Example 6.4

Here you have the polynomials appearing in [FPR 02]:

> f1:=x^9-2*x^4-10*x^3+x-2;

> f2:=x^9-2*x^5+17*x^3+4;

> f3:=x^9-2*x^3-10;

> f4:=x^10+7*x^9-2*x^8-2*x^7-3*x^5+x^4+1;

> f5:=x^10-4*x^9-8*x^5+5*x^4+1;

> f6:=x^10-2*x^9-15;

> f7:=x^11+x^8-2*x^2+4;

> f8:=x^11-x^6-2*x^3-12*x^2-6;

> f9:=x^11-x^10-x^4-4;

> f10:=x^12-3*x^9+4*x^8-x^6-x^2+10;

> f11:=x^12+4*x^11+5*x^10+6*x^6-3*x^4+12;

> f12:=x^12+x^9-9*x^7-2*x^6-9*x^5-6;

> f13:=x^13+6*x^10-10*x^5+9*x^2-2;

> f14:=x^13+x^10+x^9-4*x^8-x^4+x^2-1;

> f15:=x^13+x^11-8;

> f16:=x^14-x^12-x^7+10*x^5-4;

> f17:=x^14+2*x^8+6*x-1;

> f18:=x^14-8*x^7+418;

> f19:=x^15+4*x^11+12*x^10+x^3-4;

> f20:=x^15+9*x^5+1;

> f21:=x^15-13*x^5-2;

> f22:=x^15-30*x^13+360*x^11-2200*x^9+7200*x^7-12096*x^5+8960*x^3-120*x-249;

> f23:=x^15-30*x^13+360*x^11-2200*x^9+7200*x^7-12096*x^5+8960*x^3-120*x-257;

> f24:=x^16+132*x^14+6868*x^12+179570*x^10+2394972*x^8+18111820*x^6+65000173*x^4+

102234000*x^2+46240000;

> f25:= x^21-42*x^19+ 756*x^17-7616*x^15+47040*x^13-183456*x^11+448448*x^9-658944*x^7+532224*x^5-197120*x^3+21504*x-1691;

> f26:=x^12- 181170*x^11 + 13676070375*x^10-564635734535475*x^9 + 14120575648656756795*x^8-224213861531349946866060*x^7+2299324928127100837257833640*x^6-15120132032108410885407953780505*x^5+ 61607021939453175254804920116967515*x^4-144536083330213614666317706146365094565*x^3+ 170426077617455313511361437803852538934904*x^2-83139235455474245627641509862888062014092560*x +12253655221465755667504199645608996691723374656;

> f27:=x^16 - 12*x^14 - 84*x^13 - 196*x^12 + 2856*x^11 + 6328*x^10- 42336*x^9 - 64820*x^8 + 352464*x^7 + 298928*x^6 - 1776096*x^5- 262416*x^4 + 5458656*x^3 - 1875872*x^2 - 6688416*x + 7866576;

> f28:=x^16 - 432*x^14 + 68688*x^12 - 4717440*x^10 + 112637304*x^8+ 409406400*x^6 + 2774305728*x^4 + 4041156096*x^2 + 11224978704;

> f29:=x^24+ 57*x^22 + 1197*x^20 + 13681*x^18 + 136854*x^16 + 1048044*x^14+ 4603892*x^12 + 11460015*x^10 + 16001100*x^8 + 11131014*x^6+ 2739339*x^4 - 368793*x^2 - 7569;

> f30:=x^32+16;

> f31:=x^32+160*x^30+11216*x^28+455360*x^26+11928052*x^24+212540000*x^22+2645190320*x^20+ 23223642560*x^18+143402547926*x^16+613283590880*x^14+1764753386480*x^12+3275906117440*x^10+3788371498452*x^8+2940754348320*x^6+1769278869776*x^4+73445288000*x^2+87782430961;

> f32:=x^40-2*x^39-22*x^37+26*x^36-2*x^35+185*x^34-120*x^33-270*x^32-1232*x^31+689*x^30+1972*x^29+4298*x^28-2588*x^27-6040*x^26-5558*x^25+19939*x^24+21850*x^23+12277*x^22-20890*x^21+4071*x^20+28388*x^19+35210*x^18+10304*x^17+18728*x^16+1408*x^15-3352*x^14-16288*x^13+20512*x^12+16320*x^11-37728*x^10-13312*x^9-7168*x^8+2560*x^7-1280*x^6-7680*x^5+10496*x^4+7168*x^3+512*x^2+2048*x+1024;

DATA FOR THE EXAMPLES IN THE PAPER “Higher Newton polygons and integral bases”

Example 5.1

Example 5.2

Example 5.3

Example 5.1

Here you have a file with the definition of the polynomials

Example 5.2

The table was constructed using the following function

> function timing(k,p)

> pol:=(x^2+x+1)^2-p^(2*k+1);

> time i,b,f:=montes(pol,p: ComputeStem:=true);

> return b;

> end function;

Example 5.3

You may compute the polynomial in this example with the following code:

> t,Y,z:=InitializeType(3,x);

> EnlargeType(2,3,Y[1]^2+1,~t,~Y,~z);

> FF:=t[2]`Fq;

> l:=[x: x in AllIrreduciblePolynomials(FF,2)];

> tipus:=[];

> for j in [1..#l] do

t,Y,z:=InitializeType(3,x);

EnlargeType(1,3,Y[1]^2+1,~t,~Y,~z);

FF:=t[2]`Fq;

l1:=[x: x in AllIrreduciblePolynomials(FF,2)];

ppol:=l1[j];

EnlargeType(3,2,ppol,~t,~Y,~z);

Append(~tipus,t);

> end for;

> POL:=&*[t[3]`Phi^2: t in tipus]+3^2000;

NOTES ON THE IMPLEMENTATION AND SUPPORT

The package has been designed for Magma V2.11-10, but it should work with any newer version of Magma. Particularly, the improved version of HermiteForm in Magma V2.13 should cause a significant decrease of the running time.

The authors will welcome any comment on the program.

For questions (but not necessarily answers), please contact either of the authors: Jordi Guàrdia, Jesús Montes or Enric Nart.

HOW TO CITE THE PROGRAM

If you use our program in your research, please include a citation to [GMN 08] , [GMN 08a] and [GMN 09] in the bibliography.

CHANGE LOG

V.3.0: Use of GroebnerBasis has been substituted by two calls to HermiteForm over a ResidueClassRing. The functions “MIB” and “montes” have been replaced by a unique function “HNIntegralBasis”.

V.2.6: Added the computation of local and global integral bases.

REFERENCES

[FPR 02] D. Ford, S. Pauli, X. Roblot, A fast algorithm for polynomial factorization over , J. Théorie des Nombres de Bordeaux, 14, no. 1 (2002), pp. 151-169.

[GMN 08] J. Guàrdia, J. Montes, E. Nart, Newton polygons of higher order in algebraic number theory, preprint available at http://arxiv.org/abs/0807.2620.

[GMN 08a] J. Guàrdia, J. Montes, E. Nart, Higher Newton polygons in the computation of discriminants and prime ideal decomposition in number fields, preprint available at http://arxiv.org/abs/0807.4065

[GMN 09] J. Guàrdia, J. Montes, E. Nart, Higher Newton polygons and integral bases, preprint available at http://arxiv.org/abs/0902.3428.

[Mon 99] J. Montes, Polígonos de Newton de orden superior y aplicaciones aritméticas, Tesi Doctoral, Universitat de Barcelona 1999.