This section is concerned with fields (mainly local and global arithmetic fields), their rings of integers and valuation rings.
The rational field ℚ and its ring of integers ℤ
Residue class rings of ℤ
Univariate polynomial rings
Finite fields
Number fields and their orders
Rational function fields
Algebraic function fields
Valuation rings
Real and complex fields
Local fields
Power series rings and Laurent series rings
In the case of arithmetic fields, the major facilities include:
Construction of a basis for the maximal order(s)
Decomposition of ideals into prime ideals
Recognition of principal ideals
The class group
Fundamental units
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.
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
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.
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.
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.
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
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
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
Magma employs asymptotically fast algorithms for performing arithmetic with univariate polynomials. 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.
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.
Arithmetic with elements
Construction of ideals and subrings (over K)
Construction of quotient rings
Arithmetic with ideals (over K)
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].
Trace and norm; Relative trace and norm
Order of an element
Characteristic and minimum polynomials
Testing elements for: Normality, primitivity
Construction of primitive and normal elements
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.
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.
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.
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 (up to degree 23) 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.
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
Representation of a number field as a vector space or algebra over a given coefficient field
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
Class group: Conditional (GRH) and unconditional algorithms
Unit group: Conditional (GRH) and unconditional algorithms
Regulator
Exceptional units, S-units
Ray class groups, unit group of ray class rings of absolute maximal orders.
p-Selmer groups
Norm equations, relative norm equations (both in the field and the order case, testing for local solubility)
Thue equations
Unit equations
Index form equations
Integral points on Mordell curves
Determination of subfields
Automorphism groups of normal and abelian fields
Isomorphism of number fields
Galois group of number fields having degree less than 24 (over ℚ or an absolute number field)
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.
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
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)
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.
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)
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
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
Ring predicates
Basis size reduction for finite, simple, non relative 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
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
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
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
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
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
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
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
The development of this module is a joint project with the KANT group.
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
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
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)
Two different models of the real and complex field are available in Magma. The default version is based on semantics developed by Henri Cohen for PARI. In this model, the precision of a real or complex number is determined by the accuracy of the operands and the operation. Whenever a real or complex number is known exactly, it is kept in exact form and only converted to real/complex form when it has to be used as an argument in some operation. Thus, during a calculation, real or complex numbers will appear with varying precisions, where the precision for a particular number is chosen in such a way that all digits should be meaningful. This is achieved through use of a form of interval arithmetic. We call this model of the real or complex field, the free model. Magma implements its free model using a modified version of the PARI code. The PARI code achieves its speed by using assembler for a small number of critical operations and by careful organization. This has been carried over into the Magma version so that the speed of the Magma version is virtually the same as the native PARI code in all but a few instances. The hundred or more real and complex functions implemented in PARI are available in Magma.
A second model of the real field is provided whereby all numbers are stored to a fixed precision. This version is based on Richard Brent's MP package and is known as the truncated model.
These are currently both being replaced by an MPFR-based model, though internal computations still often use PARI.
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.
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.
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
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.
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
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
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
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
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.