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 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.

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

  • 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

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 Dirichlet Characters

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.

5.3 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.3.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.3.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.3.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, number fields or prime characteristic function 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.3.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 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 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.3.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.4 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.5 Finite Fields

5.5.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 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 about 0.2 seconds, compared to several minutes with the naive root finding method.

5.5.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

  • Fast powering via Frobenius map

  • Construction of primitive and normal elements

5.5.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 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.

5.5.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 implementation of Coppersmith's method (for fields GF(pk) for very small p).

  • Database of factor basis logs for Coppersmith's method (for very many fields of type GF(pk) for very small p).

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.5.5 Derived Structures

  • Unit group

  • Additive group

  • Field as an algebra over a subfield