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
p-adic Rings and their extensions
General 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
Class group, divisor class group and ray class groups
Fundamental units
Constructive class field theory
Galois theory, subfields and automorphisms
Places and completions
Cohomology of number fields and their completions
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 package for the base classical, Karatsuba and Toom and Schönhage-Strassen FFT-based algorithms (for which GMP is the state of the art).
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.
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
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
Linear algebra
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.
The Dirichlet characters package provides support for computing with the group of homomorphism (ℤ/Nℤ)*→R*, where R is a ring. New functionality also exists for Dirichlet (and Hecke) characters over number fields.
Dirichlet group over a field K as the set of rational characters from (ℤ/Nℤ)* to K*.
Computation of group generators, enumeration of elements, and representatives of Galois-conjugacy classes of characters.
Construction and evaluation of Dirichlet characters.
Invariants of characters, such as their conductor, modulus, and order.
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
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.
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 all local rings and fields
Factorization over ℚ(α): Trager algorithm
Factorization over any finitely generated extension of GF(p) and ℚ
Galois group computation for arbitrary polynomials in ℚ[t]
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 small finite fields to very high degrees (see details in Subsec. 22.3 on page \pagerefff_db)
Special optimized packed arithmetic for fields of characteristic 2 and 3.
Construction of towers of extensions
Construction of subfields
Compatible embedding of subfields
Enumeration of irreducible polynomials
Fast embedding and isomorphism algorithm of E. Rains.
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].
Using the fast algorithm of Rains, embedding the field GF(21000) in GF(22000) now takes 0.3 seconds on a 2.4GHz Opteron, compared to about 20 minutes with the old root finding method.
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
Fast powering via Frobenius map
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 2.4GHz Opteron, 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 in 1300 seconds.
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.