5 Rings and their Fields

This section is concerned with fields (mainly local and global arithmetic fields), their rings of integers and valuation rings.

In the case of arithmetic fields, the major facilities include:

5.1 The Rational Field and its Ring of Integers

5.1.1 Arithmetic

  • Multiple precision integer arithmetic

  • Integer multiplication via classical, Karatsuba, Toom and Schönhage-Strassen FFT methods

  • Integer division via classical, Karatsuba, Toom and Schönhage-Strassen FFT methods

  • Greatest common divisor via Weber Accelerated GCD and Schönhage algorithms

  • Extended Greatest common divisor via Lehmer and Schönhage algorithms

  • Alternative representation of integers in factored form

  • Arithmetic functions: Jacobi symbol, Euler φ function, etc.

Magma uses portions of the GMP 4.2 package for the base classical, Karatsuba and Toom algorithms (for which GMP is the state of the art). For larger integers (typically about 30,000 to 50,000 decimals), Magma uses an optimized Schönhage-Strassen FFT method.

Magma also contains an asymptotically-fast integer (and polynomial) division algorithm which reduces division to multiplication with a constant scale factor that is in the practical range. Thus division of integers and polynomials are based on the fast multiplication methods when applicable.

Finally, Magma contains implementations of the fast classical Lehmer extended GCD ('XGCD') algorithm (which is about 5 times faster than the Euclidean XGCD algorithm) and the Schönhage recursive ("half-GCD") algorithm, yielding asymptotically-fast GCD and XGCD algorithms.

On a 2.2GHz Opteron workstation, Magma can multiply 2 arbitrary integers, each having a million decimal/ digits, in 0.07 seconds, or compute their GCD in 0.1 seconds.

5.1.2 Residue Class Rings of Z

A quotient ring ℤ/ < m > of Z is trivially represented by the integers taken modulo m. In the Magma implementation, m may be taken to be a long integer.

  • Arithmetic; square root, all square roots

  • Testing elements for: nilpotency, primitivity, regularity, zero-divisor

  • Order of a unit

  • Gcd and lcm

  • Location of a primitive element

  • Unit group

  • Functor from additive group to an object in the category of abelian groups

  • One or all square roots of an element

5.1.3 Primality and Factorization

  • Probabilistic primality testing (Miller-Rabin)

  • Rigorous primality testing (Morain's Elliptic Curve Primality Prover)

  • Primality certificates; Verification of certificates

  • Generation of primes

  • Elementary factorization techniques: Trial division, SQUFOF, Pollard ρ, Pollard p – 1

  • Elliptic curve method for integer factorization (A. Lenstra)

  • Multiple prime multiple polynomial quadratic sieve algorithm for integer factorization (A. Lenstra)

  • Database of factorizations of integers of the form pn±1

The Elliptic Curve Primality Prover (ECPP) designed and implemented by François Morain at INRIA is installed in Magma. This provides fast rigorous primality proofs for integers having several hundred digits. The primality of a 100 digit integer is established in 24 seconds (on a Sun 200Mhz SPARC workstation 2).

Paul Zimmermann's efficient GMP-ECM package is included for integer factorization. The GMP-ECM package also provides fast p – 1 and p + 1 integer factorisation algorithms.

5.1.4 The Number Field Sieve

Magma provides an experimental implementation of the fastest general purpose factoring algorithm known: the number field sieve (NFS). The implementation can be used for both general number field and special number field factorizations: the only difference is in the polynomial selection. Presently, Magma does not provide a function to choose a good polynomial for a particular number to be factored. However, Magma does provide some functions that are useful for the implementation of the polynomial selection algorithms developed by Peter Montgomery and Brian Murphy.

5.2 Univariate Polynomial Rings

A polynomial ring may be formed over any ring, including a polynomial ring. Since computational methods for univariate polynomial rings are often much simpler and more efficient than those for multivariate rings (especially over a field), we discuss the two cases separately. In this section, the symbol K, appearing as a coefficient ring, will denote a field.

5.2.1 Creation and Ring Operations

  • Creation of a polynomial ring

  • Definition of a ring map

  • Kernel of a ring map

  • Determining whether a ring map is surjective

  • Determining whether a ring map is an isomorphism

5.2.2 Creation of Special Polynomials

  • Orthogonal polynomials: Bernoulli polynomial

  • Orthogonal polynomials: Chebyshev polynomials of the first and second kinds

  • Orthogonal polynomials: Chebyshev polynomials of types T and U

  • Orthogonal polynomials: Gegenbauer polynomial, Hermite polynomial

  • Orthogonal polynomials: Generalised Laguerre polynomial

  • Orthogonal polynomials: Legendre polynomial

  • Binomial polynomial

  • Conway polynomial of degree n over GF(p)

  • Primitive polynomial of degree n over GF(q)

  • Cyclotomic polynomial of order n

  • Permutation polynomials: Dickson polynomials of the first and second kinds

5.2.3 Arithmetic with Polynomials

  • Polynomial product via classical, Karatsuba and Schönhage-Strassen FFT algorithms

  • Polynomial quotient via classical and Karatsuba algorithms

  • Pseudo quotient and remainder

  • Modular exponentiation and inverse

  • Modular composition over GF(q) (Brent-Kung)

  • Norms

  • Differentiation and integration

  • Evaluation and interpolation

  • Properties: prime, primitive, separable, permutation

  • Properties: a unit, a zero-divisor, nilpotent

  • Properties: Galois groups of square-free polynomials over the integers or number fields

  • For polynomials over : splitting field and solvability by radicals

Magma employs asymptotically fast algorithms for performing arithmetic with univariate polynomials over certain rings. These include two FFT-based methods for multiplication: the Schönhage-Strassen FFT method for situations where the coefficients are large compared with the degree, and the small-prime modular FFT with Chinese remaindering method for where the coefficients are small compared with the degree. These methods are applied to multiplication of polynomials over , , ℤ/mℤ and GF(q). For some coefficient rings, at least one of the FFT methods outperforms the Karatsuba method for polynomials having degree as small as 32 or 64; for each of the coefficient rings listed, the FFT method beats the Karatsuba method for degree 128 or greater. An asymptotically-fast division algorithm (which reduces division to multiplication) is also used for polynomials over all coefficient rings.

5.2.4 GCD and Factorization

  • Resultant, discriminant (sub-resultant algorithm, Euclidean algorithm)

  • Greatest common divisor, extended greatest common divisor

  • Extended greatest common divisor

  • Hensel lift

  • Squarefree factorization

  • Distinct degree factorization

  • Factorization over GF(q): Small field Berlekamp, large field Berlekamp, Shoup algorithms

  • Factorization over and : van Hoeij algorithm

  • Factorization over p and its extensions

  • Factorization over ℚ(α): Trager algorithm

Greatest common divisors for polynomials over Z are computed using either a modular algorithm or the GCD-HEU method, while for polynomials over a number field, the modular method is used. For polynomials over an algebraic function field, an evaluation/interpolation algorithm of Allan Steel is used.

Factorization of polynomials over Z uses the exciting new algorithm of Mark van Hoeij, which efficiently finds the correct combinations of modular factors by solving a Knapsack problem via the LLL lattice-basis reduction algorithm.

5.2.5 Arithmetic with Ideals

  • Construction of ideals and subrings (over K)

  • Construction of quotient rings

  • Arithmetic with ideals (over K)

  • Properties of an ideal: Maximal, prime, primary

5.3 Residue Class Rings of Univariate Polynomial Rings

  • Arithmetic with elements

  • Construction of ideals and subrings (over K)

  • Construction of quotient rings

  • Arithmetic with ideals (over K)

5.4 Finite Fields

5.4.1 Construction

  • Construction of fields GF(p), p large; GF(pn), p small and n large

  • Optimized representations of GF(pn) in the case of small p and large n

  • Database of sparse irreducible polynomials over GF(2) for all degrees up to 11000.

  • Special optimized packed arithmetic for fields of characteristic 2.

  • Construction of towers of extensions

  • Construction of subfields

  • Compatible embedding of subfields

  • Enumeration of irreducible polynomials

The finite field module uses different representations of finite field elements depending upon the size of the field. Thus, in the case of small to medium sized fields, the Zech logarithm representation is used. For fields of characteristic 2, a packed representation is used (since V2.4), which is very much faster than the representation used in previous versions of Magma. For a large degree extension K of a (small) prime field, K is represented as an extension of an intermediate field F whenever possible. The intermediate field F is chosen to be small enough so that the fast Zech logarithm representation may be used. Thus, Magma supports finite fields ranging from GF(2n), where the degree n may be a ten thousand or more, to fields GF(p), where the characteristic p may be a thousand-bit integer. The finite field code is highly optimized for very small finite fields and especially for linear algebra over such fields.

A noteworthy feature of the facility is that no matter how a field is created, its embedding into an overfield may be determined. One may create and work within a lattice of subfields with create ease. The system is described in detail in a paper [BCS].

5.4.2 Arithmetic

  • Trace and norm; Relative trace and norm

  • Solving Norm and Hilbert-90 equations

  • Order of an element

  • Characteristic and minimum polynomials

  • Testing elements for: Normality, primitivity

  • Construction of primitive and normal elements

5.4.3 Roots and Polynomial Factorization

  • Square root: Tonelli-Shanks method for GF(p)

  • n-th root

  • One root of a polynomial; All roots root of a polynomial

  • Polynomial factorization: Small field Berlekamp, large field Berlekamp

  • Polynomial factorization: Shoup algorithm

  • Construction of a splitting field

  • Factorisation over splitting field

Factorization of polynomials over GF(q) for large q uses Shoup's algorithm. On a 64-bit 200MHz SGI Origin 2000, the n = 2048 polynomial from the von zur Gathen challenge benchmarks (of degree 2048 with sparse coefficients modulo a 2050-bit prime) is factored by Magma V2.7 in about 18.8 hours and the n = 3000 polynomial from the same benchmarks (of degree 3000 with sparse coefficients modulo a 3002-bit prime) is factored by Magma V2.7 in about 75.8 hours. Also, the n = 2048 polynomial from the Shoup challenge benchmarks (of degree 2048 with dense coefficients modulo a 2048-bit prime) is factored by Magma V2.7 in about 36.0 hours on the same machine.

5.4.4 Discrete Logarithms

  • Shanks baby-step giant-step algorithm

  • Pollard rho algorithm

  • Polhig-Hellman algorithm

  • Index calculus method using either the Gaussian integer sieve or linear sieve (for prime fields GF(p)).

  • Index calculus method using Emmanuel Thomé's implementation of Coppersmith's method (for fields GF(2k)).

The index calculus method applied to an arbitrary field GF(p), where p is a 100-bit prime such that (p – 1)/2 is prime (the worst case), takes 10 seconds to perform the sieving and about 0.8 seconds to compute an individual logarithm. For a 20-decimal-digit prime p such that (p – 1)/2 is prime, Magma takes only 1 second for the sieving and about 0.3 seconds to compute an individual logarithm.

5.4.5 Derived Structures

  • Unit group

  • Additive group

  • Field as an algebra over a subfield

5.5 Galois Rings

Magma provides facilities for computing with Galois rings. The features are currently very basic, but advanced features will be available in the near future, including support for the creation of subrings and appropriate embeddings, allowing lattices of compatible embeddings, just as for finite fields.

Because of the valuation defined on them, Galois rings are Euclidean rings, so they may be used in Magma in any place where general Euclidean rings are valid. This includes many matrix and module functions, and the computation of Gröbner bases. Linear codes over Galois rings will also be supported in the near future.

Features:

  • Creation of a default Galois ring (using a default defining polynomial).

  • Creation of a Galois ring by a specified defining polynomial.

  • Basic structural operations and arithmetic.

  • Euclidean operations.

5.6 Number Fields and their Orders

Magma currently has three main categories corresponding to number fields: general number fields, quadratic fields, and cyclotomic number fields. It should be noted, that quadratic fields and cyclotomic fields are in fact number fields that allow special algorithms in some situations, e.g., for class group computation, continued fractions for fundamental units.

Facilities for general number fields have been developed in a joint project with the KANT group in Berlin. The core consists of machinery for performing arithmetic with arbitrary orders and their ideals. The major capabilities include facilities to determine the maximal order (round 2 and 4 algorithms), class group, unit group, Galois group and the computation of defining equations for ray class fields.

Elements of number fields and their orders may have several representations. These representations are implemented generally for elements of number fields and function fields. The standard representation is coefficients of the basis elements. When the basis is a power basis, a polynomial representation is used. All elements may have a product representation which can be a compact way of storing otherwise large elements.

5.6.1 Number Fields

  • Arithmetic of elements

  • Construction of equation orders, maximal orders, arbitrary orders

  • Simple and relative extensions, extensions defined by several polynomials

  • Subfields

  • Transfer between relative and absolute representations

  • Discriminant, reduced discriminant, signature

  • Factorization of polynomials over number fields

  • Completion of absolute fields at finite primes

  • Number fields with arbitrary bases

  • Computation of Hilbert class fields and general class fields.

  • Representation of a number field as a vector space or algebra over a given coefficient field

  • Automorphism group, Galois group of the normal closure

  • Action of the automorphisms on ideals and ideal classes

5.6.2 Orders and Fractional Ideals

  • Multiple relative extensions

  • Maximal order, integral basis (Round 2 and Round 4 algorithms)

  • Suborders, extension orders

  • Construction of integral and fractional ideals

  • Ideal arithmetic: product, quotient, gcd, lcm

  • Determination of whether an ideal is: integral, prime, principal

  • Decomposition of primes

  • Valuations of order elements and ideals at prime ideals

  • Ramification index

  • Factorization of an ideal

  • Residue field of an order modulo a prime ideal

  • Reside class ring of an order modulo an arbitrary ideal

  • Completion of absolute maximal orders at finite primes

5.6.3 Invariants

  • Class group: Conditional (GRH) and unconditional algorithms

  • Unit group: Conditional (GRH) and unconditional algorithms

  • Picard group for non-maximal orders

  • Regulator

  • Exceptional units, S-units

  • Ray class groups, unit group of ray class rings of absolute maximal orders.

  • p-Selmer groups

5.6.4 Diophantine (and other) Equations

  • Norm equations, relative norm equations (both in the field and the order case, testing for local solubility)

  • Simultaneous norm equations, splitting of 2-cocyles

  • Thue equations

  • Unit equations

  • Index form equations

  • Integral points on Mordell curves

5.6.5 Automorphisms

  • Determination of subfields

  • Automorphism groups of normal and abelian fields

  • Isomorphism of number fields

  • Galois group of number fields (over or an absolute number field) with no degree restriction.

  • Galois correspondence

  • Ramification theory

Consider the extension K of Q by a root of x9 – 57x6 + 165x3 – 6859. The maximal order of K is found in 0.17 seconds, the class group (ℤ/3ℤ) is found unconditionally in 41 seconds (conditionally, under GRH, in 26 seconds, using even smaller bounds it is possible to compute the class group in 4.11 seconds), the unit group (ℤ/2ℤ⊕ℤ⊕ℤ⊕ℤ⊕ℤ) in 3.50 seconds and the Galois group of order 18 in 0.25 seconds. The four subfields of degree 3 are found in 0.10 seconds.

5.6.6 Class Field Theory

  • Computation of defining equations of class fields

  • The norm group of an abelian number field can be computed

  • Norm symbols, Artin-map is available

  • Solvability of norm equations can be tested, extending the Hasse-Norm-Theorem

  • Extension of automorphisms of the base field

  • Second cohomology of the Ray class group

5.6.7 Quadratic Fields

  • All functionality of number fields

  • Division of integral elements of ℚ(√d), for d = -1, – 2, – 3, – 7, – 11,2,3,5,13.

  • Factorization of integral elements of ℚ(√d), for d = -1, – 2, – 3, – 7, – 11.

  • Class number (Shanks' algorithm)

  • Ideal class group (Buchmann's method)

  • Fundamental unit, conductor

  • Solution of norm equations (Cornaccia's algorithm for imaginary fields and Cremona's conics for real quadratic fields)

  • Facilities for binary quadratic forms (see Lattices and Quadratic Forms)

  • 2-class group using the Bosma– Stevenhagen method

5.6.8 Cyclotomic Fields

  • All functionality of number fields

  • Sparse representation for large fields

  • Conductor and cyclotomic order

  • Cyclotomic subfields

  • Creation of roots of unity

  • Minimization of elements into smaller fields

  • Conjugation and complex conjugation

5.7 General Algebraic Function Fields

A general algebraic function field F/k of n variables over a field k is a field extension F of k such that F is a field extension of finite degree of k(x1, .s, xn) for elements xi∈F which are algebraically independent over k.

5.7.1 Rational Function Fields

Given any field k and indeterminates x1,…, xn, the user may form the field of rational functions k(x1,…, xn) as the localization of the polynomial ring k[x1,…, xn] at the prime ideal < x1,…, xn > .

  • Creation of a rational function field of a given rank over a given ring

  • Retrieval of the ring of integers, coefficient ring and rank

  • Ring predicates

  • Arithmetic

  • Numerator and Denominator

  • Degree and weighted degree

  • Evaluation

  • Derivative

  • Partial fraction expansion

  • Partial fraction decomposition (squarefree or full factorization)

5.7.2 Algebraic Function Fields

Within Magma, algebraic function fields of one variable can be created by adjoining a root of an irreducible, separable polynomial in k(x)[y] to the rational function field k(x). If k is a finite field, the function field is said to be global. An algebraic function field can be extended to create fields of the form k(x,a1,…, ar) where each extension occurs by adjoining a root of an irreducible and separable polynomial. Extensions may be formed using several polynomials simultaneously giving a non simple representation.

  • Creation of simple, relative and non simple extensions and mixed towers thereof

  • Creation of extensions of the constant field using bivariate polynomials

  • Retrieval of information defining the field

  • Exact constant field and genus

  • Change of representation from finite degree extensions to infinite and vice versa

  • Change of coefficient field to one lower in the extension tower

  • Computation of basis

  • Computation of subfields and automorphisms

  • Homomorphisms from function fields into any ring by specifying the image of the primitive element and an optional map on the coefficient field

  • Computation of Galois Groups of degree less that 24

  • L-polynomial and ζ-function

  • Construction of a function field with an extended constant field

  • Construction of Artin-Schreier-Witt extensions from finite dimensional Witt-vectors

  • Constructive class field theory using both algebraic and analytic (Drinfeld modules) methods

5.7.3 Orders of Algebraic Function Fields

  • Finite and infinite equation orders

  • Finite and infinite maximal orders using the Round 2 algorithm

  • Creation of orders whose basis is a transformation of an existing order

  • Integral closure

  • Retrieval of information defining the order

  • Basis of the order with the option to have the elements returned in a specified ring

  • Discriminant and also with respect to the bottom coefficient ring of the tower

  • Simplification of an order to a transformation of its equation order

  • Unit Group and unit rank, independent and fundamental units and regulator

  • Ideal class group for maximal orders

  • Ring predicates

  • Basis size reduction for finite, simple, non relative orders

5.7.4 Elements of Algebraic Function Fields and their Orders

Elements of function fields and their orders have 3 different representations. These representations are implemented generally for function field elements and number field elements. Standard elements are represented using coefficients of the basis elements. Elements of orders (and fields) with a power basis are represented using a polynomial representation. Elements of all orders or fields may have a product representation, being thought of as a formal product of a list of elements each to the power of some exponent. This can be a great advantage when the element is prohibitively large when represented using coefficients.

  • Arithmetic and modular arithmetic

  • Predicates

  • Creation of random elements and conversion to and from sequences

  • Norm and trace with respect to any given coefficient ring

  • Representation matrix, minimal and characteristic polynomials

  • Numerators and Denominators with respect to a given order

  • Module generated by a sequence of elements

  • Strong approximation theorem

  • Power series expansion, mapping of elements into completions

5.7.5 Ideals of Orders of Algebraic Function Fields

  • Creation of ideals from generators or a basis

  • Arithmetic

  • Roots of ideals

  • Predicates for integrality, prime, principal zero and one ideals

  • Predicate for prime ideals determining the type of ramification

  • Intersection, GCD and LCM

  • Factorization

  • p-radicals and p-maximal orders

  • Taking valuations of elements and ideals at prime ideals

  • Denominator

  • Retrieving basis and generators

  • Residue class field and the map to and from the order into it

  • Ramification and inertia degree

5.7.6 Places of Algebraic Function Fields

  • Creation of places as zeros and poles of elements of a field

  • Creation from prime ideals

  • Creation of random places of global fields

  • Creation of places of a given degree of global fields

  • Decomposition of places

  • Arithmetic

  • Residue class field, lifting elements out of and evaluating functions into

  • Valuation of elements and expanding elements at a place

  • Completion of fields and orders at places of degree 1 (non-global fields) or places of any degree (global fields).

  • Ramification and inertia degree

  • Retrieval of generators and a uniformizing element

  • Weierstrass places

  • Counting the number of places of a given degree over the exact constant field of global fields

  • The Serre and Ihara bounds on the number of places of degree 1 over the exact constant field of global fields

5.7.7 Divisors of Algebraic Function Fields

  • Creation from places, elements and ideals

  • Canonical and different divisor

  • Arithmetic including GCD and LCM

  • Support and Degree

  • Numerator and Denominator

  • Testing for properties of effective, positive, principal, special and canonical

  • Riemann–Roch space ℒ(D) of a divisor D, given by a k-basis of algebraic functions

  • Reduction of a divisor

  • Index of Speciality

  • Gap numbers, ramification divisors, Wronskian orders and Weierstrass places

  • Parametrization of a field at a divisor

  • Number of smooth divisors of global fields

5.7.8 Differentials of Algebraic Function Fields

  • Creation of a differential space

  • Creation of differentials from field elements

  • Arithmetic

  • Valuation of a differential at a place

  • Divisor of a differential

  • Differential spaces and bases for given divisors

  • Space and basis of holomorphic differentials of a field

  • Differentiations of elements of a function field

  • Residue of a differential at a place of degree one

  • Cartier operator and representation matrix of the Cartier operator (global case)

  • Module generated by a sequence of differentials

5.7.9 Divisor Class Groups of Global Algebraic Function Fields

  • Bounds on the generation of the class group

  • Computation of the class number and approximations to it

  • Construction of the divisor class group, structure of the divisor class group, representation of divisor classes as abelian group elements

  • S-class group, S-units and S-regulator for a finite set of places S

  • Exact sequence

    0→U(S)→F×→Div(S)→Cl(S)→0

  • Image and preimage computation possible for the maps of the exact sequence

  • Similar functionality for the ideal class group of the finite maximal order

  • p-rank of the divisor class group (separate method) and Hasse–Witt invariant

  • Tate–Lichtenbaum pairing

  • Global units

5.7.10 Class Field Theory for Algebraic Function Fields

  • Ray divisor class groups

  • Defining equation for class fields

  • Conductor and norm group

  • Genus, discriminant, number of places of given degree

  • Decomposition type of places of the base field

  • Exact constant field

  • Drinfeld modules of rank 1, rings of twisted polynomials

The development of this module is a joint project with the KANT group.

5.8 Discrete Valuation Rings

Valuation rings are available for the rational field and for rational function fields. For rational function fields, given an arbitrary monic irreducible polynomial p(x)∈K[x], the valuation ring is

Op(x) = { f(x)g(x) : f(x),g(x)∈K[x],p(x) ∤g(x)}.
Valuations corresponding both to an irreducible element and to are allowed.

  • Valuation ring corresponding to the discrete non-Archimedean valuation vp of

  • Valuation ring corresponding to the discrete non-Archimedean valuation vp of a rational function field

  • Valuation ring corresponding to the valuation v of a rational function field

  • Arithmetic

  • Euclidean norm, valuation

  • Greatest common divisor

5.9 The Real and Complex Fields

The real and complex fields are different from most structures in that exact computation in them is almost never possible.

  • Arithmetic

  • Square root, arithmetic-geometric mean

  • Continued fraction expansion of a real number

  • Constants: π, Euler's constant, Catalan's constant

  • Logarithm, dilogarithm, exponential

  • Trigonometric functions, hyperbolic functions and their inverses

  • Bernoulli numbers

  • Γ function, incomplete Γ function, complementary incomplete Γ function, logarithm of Γ function

  • J-Bessel function, K-Bessel function

  • U-confluent hypergeometric function

  • Logarithmic integral, exponential integral

  • Error function, complementary error function

  • Dedekind η function

  • Jacobi sine theta-function and its k-th derivative

  • Log derivative (ψ) function, i.e, Γ'(x)Γ(x)

  • Riemann-ζ function

  • Polylogarithm, Zagier's modifications of the polylogarithm

  • Weber's f-function, Weber's f2-function, j-invariant

  • Integer polynomial having a given real or complex number as an approximate root (Hastad, Lagarias and Schnorr LLL-method)

  • Roots of an exact polynomial to a specified precision (Schönhage splitting circle method)

  • Summation of a series (Euler-Wijngaarden method for alternating series)

  • Numerical integration of a function (Romberg-type methods)

The real and complex fields in Magma are based on the GMP, MPFR and MPC packages. Some of the transcendental functions as well as root finding is based on code developed by Henri Cohen for PARI.

5.10 Newton Polygons

  • Construction of a newton polygon: Compact, infinite or including the origin

  • Construction of newton polygons from different types of data: f∈k[x,y], f∈k < < x > > [y], f∈k[y] and some prime object, a finite set of points, a finite set of faces (weighted dual vectors)

  • Finding faces, vertices and slopes

  • If polygon is derived from a polynomial f, finding restrictions of f to faces

  • Locating a given point relative to a newton polygon

  • Giving the valuations of the roots of a polynomial (with respect to a prime if not implicit)

Newton polygons can be used with polynomials over series rings in order to find roots of the polynomial.

  • Walker's [Wa78] algorithm for computing Puiseux expansions

  • Duval's [Duv89] algorithm for computing Puiseux expansions

5.11 Local Rings and Fields

A p-adic ring arises as the completion of the ring of integers at a prime while a local field arises as the completion at a prime ideal of a number field. Magma supports both fixed and free precision models, allowing the user to trade an increase in speed for automated precision management.

5.11.1 Local Rings: Construction

  • Construction of a p-adic ring or field

  • Unramified extension of a local ring or field

  • Totally ramified extension of a local ring or field

  • Ring of integers of a local field

  • Field of fractions of a local ring

  • Change precision of a ring, field or element

  • Computation of a splitting field of an integral polynomial over an p-adic ring.

  • Enumeration of extensions of a given degree.

A local ring is a finite degree extension of a p-adic ring and may be either ramified or unramified or both. Any arbitrary tower of extensions can be constructed, as long as each step is either ramified or unramified or both.

5.11.2 Local Rings: Arithmetic

  • Arithmetic operations

  • Valuation of an element

  • Norm and trace of an element

  • Logarithm, exponential of an element

  • Square root, n-th root of an element

  • Minimal polynomial of an element over the p-adic subring or field

  • Image of an element under a power of the Frobenius automorphism

  • Linear algebra over local rings and fields

5.11.3 Local Rings: Polynomial Factorization

  • Polynomial algebra over local rings and fields

  • Greatest common divisor of two polynomials

  • Hensel lifting of the factors of a polynomial

  • Hensel lifting of the roots of a polynomial

  • Test a polynomial for irreducibility

  • Roots of a polynomial over a local ring or field

  • Factorization of polynomials over local ring or field

5.11.4 Local Rings: Class field theory

  • Unit group and norm group

  • Defining equations for abelian extensions

5.12 Power, Laurent and Puiseux Series Rings

Magma contains an extensive package for formal power series. The fact that we may only work with a finite number of terms, n say, of a power series, i.e., a truncated power series, is made precise by noting that we are working in the quotient ring R[[x]]/ < xn+1 > , for some n, rather than in the full ring R[[x]]. Provided this is kept in mind, calculations with elements of a power series ring (though not field) are always precise.

Given a field K, a field of Laurent series K((x)) is regarded as the localization of the power series ring K[[x]] at the ideal < 0 > . More simply, it is the field of fractions of K[[x]]. Since elements of such a field are infinite series, calculation is necessarily approximate.

A power series ring R[[x]] is regarded as the completion of the polynomial ring R[x] at the ideal < 0 > .

Puiseux series with arbitrary fractional exponents are also supported (since V2.4).

  • Arithmetic

  • Inversion of units

  • Derivative, integral

  • Square root, valuation

  • Exponentiation, composition, convolution, reversion

  • Power series expansions of transcendental functions

  • R[[x]]/ < xn+1 > as an algebra over R

  • Factorization of polynomials over series rings

  • Unramified and ramified extensions of series rings

5.13 Lazy Power Series Rings

These power series rings contain only series of infinite precision. All coefficients of such series are computable but only finitely many will be known.

  • Creation of rings and elements

  • Arithmetic of elements

  • Retrieval of coefficients

  • Printing some specified terms of a series

  • Simple predicates on series

  • Derivative, integral and evaluation of series

5.14 Algebraically Closed Fields

Algebraically closed fields (ACF's) have the property that they always contain all the roots of any polynomial defined over them.

  • Automatic extension of the field by the roots of any polynomial over the field, and operations on conjugates of roots

  • Basic arithmetic

  • All standard algorithms for rings over generic fields work over such fields

  • Minimal polynomial

  • Simplification of the field

  • Construction of the corresponding absolute field together with the isomorphism

  • Pruning of useless variables and relations

It is not possible to construct explicitly the closure of a field, but the system works by automatically constructing larger and larger algebraic extensions of an original base field as needed during a computation, thus giving the illusion of computing in the algebraic closure of the base field.

A similar system was suggested by D. Duval and others (the D5 system [Duval85]), but this has difficulty with the parallelism which occurs when one must compute with several conjugates of a root of a reducible polynomial, leading to situations where a certain expression evaluated at a root is invertible but evaluated at a conjugate of that root is not invertible.

The system developed for Magma by Allan Steel avoids these problems, and is described in [ACF]. Consequently, ACF's behave in the same way as as any other field implemented in Magma; all standard algorithms implemented for generic fields and which use factorization work without change (for example, the Jordan form of a matrix).

The system avoids factorization over algebraic number fields when possible, and automatically splits the defining polynomials of a field when factors are found. The field may also be simplified and expressed as an absolute field. Especially significant is also the fact that all the Gröbner basis algorithms work well over ACF's. One can now compute the variety of any zero-dimensional multivariate polynomial ideal over the algebraic closure of its base field. Puiseux expansions of polynomials are now also computed using an algebraically closed field.