From john@maths.usyd.edu.au Sat Jun 14 17:47:09 1997 Date: Sat, 14 Jun 1997 12:28:09 -0400 From: John Cannon To: NMBRTHRY@LISTSERV.NODAK.EDU Subject: Number Theory in Magma V2.2 ------------------------------ | NUMBER THEORY IN MAGMA V2.2 | ------------------------------ Magma is a Computer Algebra system designed specifically for computation in all branches of algebra, number theory and geometry (and for other areas that are heavily algebraic in nature). Features of its philosophy include: ALGEBRAIC DESIGN PHILOSOPHY: The design principles underpinning both the user language and system architecture are based on ideas from universal algebra and category theory. The language attempts to approximate as closely as possible, the usual mathematical modes of thought and notation. In particular, the principal constructs in the user language are set, (algebraic) structure and morphism. UNIVERSALITY: In-depth coverage of all the major branches of algebra, number theory, algebraic geometry and finite incidence geometry. INTEGRATION: The facilities for each area are designed in a similar manner using generic constructors wherever possible. The uniform design makes it a simple matter to program calculations that span different classes of mathematical structures or which involve the interaction of structures. PERFORMANCE: The intention is that Magma provide the best possible performance both in terms of the algorithms used and their implementation. The design philosophy permits the kernel implementor to choose optimal data structures at the machine level. Most of major algorithms currently installed in the Magma kernel are state-of-the-art and give performance similar to, or better than, specialized programs. ------------------ | SUMMARY OF AREAS | ------------------ The mathematical structures implemented in the Magma kernel may be loosely grouped into eight areas: * Semigroups, monoids, automata, rewriting systems. * Groups: Finitely-presented groups, fg abelian groups, black-box groups, permutation groups, matrix groups, soluble groups. * Commutative rings: Ring of integers, polynomial rings, power series rings, orders, valuation rings, ring of group invariants. * Fields: Finite fields, number fields, function fields, local fields, fields of Laurent series, real and complex fields. * Modules: Vector spaces, R-modules over fields, R-modules over EDs, R-modules over K[x_1, ..., x_n], KG-modules, Hom(M, n), lattices. * Algebras: General finite-dimensional (fd) algebras, fd associative algebras, fd Lie algebras, matrix algebras, group algebras, finitely-presented associative algebras. * Algebraic geometry: Elliptic curves, curves of genus greater than 1, algebraic varieties. * Combinatorics: Counting theory, directed and undirected graphs, incidence structures, designs, planes, codes. ----------------------------------- | NUMBER THEORY FACILITIES IN MAGMA | ----------------------------------- Our goal is to provide state-of-the-art algorithms across all branches of number theory embedded in a general system. This is achieved in no small part through the generous cooperation and assistance of many people working in computational number theory. We are particularly indebited to Henri Cohen and his associates in Bordeaux, John Cremona, Francois Morain, Arjen Lenstra and especially Michael Pohst and the KANT group. Magma V1 was released in December 1993. Since then it has undergone enormous expansion and many original modules have been rewritten. This document gives a terse summary of the scope and capabilities of areas of interest to number theorists in the current release V2.2 (some information is included about the the October, 1997 release (V2.3)). Timing data refers to Magma running on a SUN Ultra 2 with a 200 MHz processor. The Magma home page http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html provides a much more complete listing of facilities together with numerous examples. ------------------- | COMMUTATIVE RINGS | ------------------- ________________________________________________________________________ Ring of integers Polynomial rings Rings of invariants Orders of fields Valuation rings Power series rings ________________________________________________________________________ INTEGERS: A new fast integer arithmetic package was released in V2.2. Among many highlights, it employs the Karatsuba algorithm for products, an exact divide function and the Weber accelerated GCD algorithm. Assembler macros are used for critical operations. Integer multiplication is 25-40% faster than GNU gmp: the multiplication of two 10,000 bit integers takes 0.005 seconds. Integer factorization is performed using versions of the ECM and MPQS algorithms developed by Arjen Lenstra. An 80-digit integer that is the product of two 40-digit primes may be factored in about 10 hours. Francois Morain's ECPP program is used for proving primality, taking about 800 seconds to prove a 200-digit integer prime. UNIVARIATE POLYNOMIALS: An extensive module for computing in polynomial rings over commutative rings is provided, and includes very fast imple- mentations of factorization algorithms over finite fields, integers and p-adics. Algorithms are also provided for factorization over number fields and function fields. Magma factors the first challenge polynomial of Zimmermann (degree 156, 78 digit coefficients over Z) in 6 seconds. (See http://www.loria.fr/~zimmerma/mupad). MULTIVARIATE POLYNOMIALS: Included are algorithms for GCDs and factor- ization over F_q, Z, Q, number fields and rational function fields (over F_q and Q); factorization over F_q, Z and rational function fields (over F_q and Q). A comprehensive Groebner basis (GB) package is provided which, in addition to a very fast implementation of the standard GB algorithm includes both a Groebner Walk and a Hilbert-driven GB algorithm. All the standard constructions associated with ideals: variety, radical, dimension, primary decomposition and Hilbert series are provided. Sample timings of the Magma GB include: - Katsura-5 problem (lex order) -- 4.5 seconds; - Cyclic 6-th roots problem (grevlex order) -- 2.5 seconds; - Cyclic 7-th roots problem (grevlex order) -- 1200 seconds. All examples are from the POSSO test suite (posso@dm.unipi.it). -------- | FIELDS | -------- ________________________________________________________________________ Rational field Finite fields Number fields Quadratic fields Cyclotomic fields Function fields Real & complex fields Local fields Laurent series fields ________________________________________________________________________ FINITE FIELDS: Finite field arithmetic is optimized through use of specialized representations for fields GF(p^n), depending upon the characteristic p and exponent n. Of particular note, is the ability to efficiently solve the compatibility problem for embedded subfields. In particular, if a field extension if constructed in two different ways, a compatible embedding in an appropriate overfield is constructed. NUMBER FIELDS: Facilities for general number fields are provided by the KANT package. The core consists of facilities 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 and Galois group (up to degree 12). A very fast algorithm is available for determining subfields. Algorithms for solving norm equations, relative norm equations, Thue equations and unit equations are included. The extension of Q by a root of x^9 - 57*x^6 + 165*x^3 - 6859 is shown to have class group Z/3Z and unit group Z/2Z + Z + Z + Z + Z in 143 seconds. The Galois group (of order 18) is found in 1 second. QUADRATIC FIELDS: Magma contains special code for quadratic fields, based on code from the PARI package. In particular, a subexponential algorithm for computing the class number is used. Binary quadratic forms with the usual reduction and composition operations provide a convenient means of computing in class groups. FUNCTION FIELDS: Fields of rational functions are available in V2.2. The first release of the KANT facility for global function fields (i.e., finite degree extensions of F_q(x)) will appear in V2.3. A fundamental operation is the construction of the integral closures (maximal orders) of F_q[x] and the valuation ring at the infinite place. Reduced integral bases may be found using a reduction algorithm of Pohst and Schoernig. Ideals of orders may be defined and a complete set of arithmetic operations on these ideals are implemented. In particular, the factorization of an ideal may be obtained. Important invariants of a field such as its genus may be found. Finally, independent and fundamental units may be constructed. COMPLEX FIELD: Real and complex arithmetic is provided by the PARI package. This package includes a huge number of functions of interest to number theorists including logarithmic and polylogarithmic functions, elliptic and modular functions, Gamma and Bessel functions and, the Riemann zeta-function. Xavier Gourdon's implementation of the Schoenhage splitting circle method for computing the roots of an exact polynomial to a specified precision is included. As an example, Magma takes 930 seconds to determine the zeros of the degree 100 Laguerre polynomial to an accuracy of 100 decimal digits. LOCAL FIELDS: p-adic rings and fields are available in V2.2. General finite extensions of p-adic rings (fields) will appear in V2.3. Apart from arithmetic, the facilities include Hensel lifting, automorphisms, factorization of polynomials and linear algebra over local fields. ---------------------- | MODULES AND LATTICES | ---------------------- ________________________________________________________________________ R-modules K[G]-modules Hom modules Lattices ________________________________________________________________________ LATTICES: A powerful family of LLL algorithms based on the FP-LLL algorithms of Schnorr and Euchner are included. Different variants on the main algorithm are provided to achieve optimization across a wide range of situations with particular attention being given to Z-lattices. Notable algorithms include enumeration of shortest vectors, automorphism groups and isomorphism testing. Given the 24-dimensional Leech lattice, Magma enumerates the 98,280 (normalized) shortest vectors in 6.8 seconds and finds its automorphism group in 175 seconds. The LLL algorithm can find difficult Z-linear dependencies among the rows of matrices having dimensions well over 500. ---------- | ALGEBRAS | ---------- ________________________________________________________________________ Finite dimensional algebras Finite dimensional associative algebras Matrix algebras Group algebras Lie algebras (V2.3) Finitely presented associative algebras ________________________________________________________________________ STRUCTURE CONSTANT ALGEBRAS: A general finite dimensional algebra may be defined by taking a free module over a field or Euclidean Domain (ED) and giving a rule for multiplying basis elements (SC algebra). Subagebras as well as left, right and two-sided ideals may be defined. The standard arithmetic operations with ideals (membership, sum, intersection, product etc) are available. In the case of an algebra defined over a field $K$, quotient algebras, composition series, the composition factors and the Jacobson radical may be constructed. If, in addition, $K$ is finite the maximal and minimal left (right, two-sided) ideals, etc., may also be found. ASSOCIATIVE ALGEBRAS: If a SC algebra is associative, additional operations are available. These include centre, commutator ideal, centralizer, idealizer, left and right annihilators, and the construction of matrix representations. MATRIX ALGEBRAS: While a matrix algebra may be defined over any ring R, most non-trivial computations require R to be an ED. If R is a field, a new fast algorithm due to Allan Steel is used to construct the various matrix canonical forms: Jordan, generalized Jordan, rational, primary rational etc, while if R is an ED, recent algorithms of Havas and others are used to compute characteristic polynomials and the Hermite and Smith normal forms. Given a 100 x 100 matrix over Z with random one-digit entries, Magma finds its Smith form in 40 seconds and its characteristic polynomial in 270 seconds. The order of a unit over a finite field is found using the very efficient algorithm of Leedham-Green. All of the operations listed for associative algebras also apply to matrix algebras. ----------------- | ELLIPTIC CURVES | ----------------- ________________________________________________________________________ Elliptic curves over a field or Z ________________________________________________________________________ ELLIPTIC CURVES: Elliptic curves may be defined over any field or Z. Standard models are provided together with heights and invariants. For curves with integer coefficients, invariants such as conductor, regulator, and local information (Tate's algorithm) are available. For curves over Q, the Mordell-Weil rank and group is computed using code based on John Cremona's MWRANK program. Magma takes 280 seconds to determine that the curve y^2 + x*y = x^3 - 215*x + 1192 has group Z_2 x Z x Z, and 100 seconds to determine that the curve y^2 = x^3 + 36861504658225*x^2 + 1807580157674409809510400*x has rank 13. -------------- | GROUP THEORY | -------------- ________________________________________________________________________ Finitely-presented groups Automatic groups Abelian groups Blackbox groups Soluble groups Permutation groups Matrix groups Representations Cohomology ________________________________________________________________________ ---------------------- | INCIDENCE STRUCTURES | ---------------------- ________________________________________________________________________ Enumerative combinatorics Graphs Incidence structures Near-linear spaces Linear spaces t-designs Projective planes Affine planes Linear codes ________________________________________________________________________ ________________________________________________________________________ MAGMA HOMEPAGE: The reader is referred to the Magma home page for a more detailed listing of facilities together with numerous examples. http://www.maths.usyd.edu.au:8000/comp/magma/Overview.html GETTING MAGMA: For more information, or to order the system, contact: Email: magma@maths.su.oz.au Telephone: +61 2 9351 3338 Fax: +61 2 9351 4534 Smail: Mathematics, University of Sydney, NSW 2006, Australia --------------------------------------------------------------------------