The Montes Algorithm

The Montes algorithm can be considered as a factorization algorithm for polynomials over local fields. For a defining polynomial f of a number field K and a prime number p the Montes algorithm produces OM representations for all prime ideals of K lying of over p, which parametrize the irreducible factors of f over the p-adic numbers. The OM representation for prime ideals leads to an OM presentation of fractional ideals. The basic algorithms are explained in [GMN13]

These OM representations allow the construction of ideals and divisors without the computation of a maximal order, which the construction of ideals of types RngOrdIdl and RngOrdFracIdl require. The Montes algorithm can also be used to efficiently compute integral bases which can be use to construct maximal orders.

This section explains the use of the Montes Algorithm. For how to use the Montes algorithm to compute maximal orders of number fields see Section Maximal Orders, maximal orders of function fields see Section Construction of Orders of Algebraic Function Fields, decomposition of primes in number fields see Sections Factorization and Primes and Creation of Elements and decomposition of primes in function fields see Sections Further Ideal Operations and Creation of Elements.

The Montes algorithm can also be called for a number field K if it is defined by a monic polynomial with integer coefficients.

Montes(f, p) : RngUPolElt, RngElt -> SeqEnum, SeqEnum, RngIntElt

    Field: BoolElt                      Default: false

Let f be a monic polynomial with integer or polynomial coefficients and p be a prime number. The Montes algorithm outputs the triple:

1.

A sequence of OM representations for the p-adic irreducible factors of f.

2.

A sequence of intervals with the position of the prime ideals in each disconnected tree of OM representations.

3.

The p-index of f.

If the parameter Field is set to true the ψ polynomial at the last level of each type of each OM representation will be computed.

> _<x> := PolynomialRing(Integers());                                       
> f := x^5 + 343*x^4 + 49*x^3 + 343*x^2 + 7*x + 6;                           
> p := 7;                                                                    
> Montes(f,p);  
[
    ,

]
[
    [ 1 ],
    [ 2 ]
]
0

> _<x> := PolynomialRing(Integers());                                       
> f := x^5 + 343*x^4 + 49*x^3 + 343*x^2 + 7*x + 6;                           
> K := NumberField(f);    
> p := 7;                                                                    
> Montes(K,p);
> K`PrimeIdeals[p];
[
    OM prime ideal over   7
    of Number Field with defining polynomial x^5 + 343*x^4 + 49*x^3 + 343*x^2 + 
    7*x + 6 over the Rational Field
    having residual degree   1
    and ramification index   1
    Last phi polynomial is x + 6,
    OM prime ideal over   7
    of Number Field with defining polynomial x^5 + 343*x^4 + 49*x^3 + 343*x^2 + 
    7*x + 6 over the Rational Field
    having residual degree   4
    and ramification index   1
    Last phi polynomial is x^4 + x^3 + x^2 + x + 1
]
> K`LocalIndex[p];  
0

> Ax<x> := PolynomialRing(Integers());
> f := x^5 + 343*x^4 + 49*x^3 + 343*x^2 + 7*x + 6;
> L := NumberField(f);
> p := 7;
> Montes(L,p);
> P := L`PrimeIdeals[p,1];
> P`Type[#P`Type]`slope;
1
> P`Type[#P`Type]`Phi; // the approximation
x + 6
> slope := 50;                                  
> SFL(~P,slope:update := true);            
> P`Type[#P`Type]`slope;                   
50
> P`Type[#P`Type]`Phi; // the approximation
x + 332598606638994184508401217986166728134618