A new fast integer arithmetic package has been developed from scratch.
This provides very substantial speed-ups over the previous integer
package used by Magma. New data structures are employed and many new
(for Magma) algorithms have been introduced. These include specialized
Karatsuba for integer product, an exact divide function and the Weber
accelerated GCD algorithm. Assembler macros are used for critical
operations and 64-bit operations are used in DEC-Alpha machines. On a
Sun Ultra 2, Magma V2.2 multiplies 300 bit integers 4 times faster than
Magma V2.1 and 1500 bit integers 7 times faster.
As part of the upgrade of the integer module, all higher level integer
functions, other than the ECM and QS factorization modules have been
rewritten or heavily revised to improve performance and to remove
memory leaks. Also improved memory management strategies have
contributed to the performance upgrade. Significant functions included
in this revision include the calculation of square roots modulo m
(m not necessarily prime) and the solution of norm equations in
quadratic fields.
A much more efficient strategy for integer factorization has been
introduced. The central idea is to strike the right balance between
the application of ECM and QS. The new strategy runs ECM for about
10% of the expected running time of QS so as to ensure any factors
having fewer than 20 -- 25 digits are discovered (in the case of an 80
digit integer). The new strategy will, in the worst case, factor 70
digit integers in about an hour and 80 digit integers in about 8 hours
using a single processor on a Sun Ultra 2. The average time for
factoring a random 80 digit integer is less than one hour. Using a
small network of workstations, factoring 90--100 digit integers is
routine. Further improvements to the factorization capability are
expected in the near future.
The Elliptic Curve Primality Prover (ECPP) designed and implemented by
Francois Morain at INRIA has been installed in Magma V2.2. 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 an Sun Ultra 2). ECPP is now used by default by the
Magma functions IsPrime and Factorization.
Summary of new features:
New main strategy for function Factorization with control over the
amount of effort expended by each subalgorithm. The parameters have
also been changed.
Independent factorization functions TrialDivision, SQUFOF, PollardRho,
pMinus1, ECM, MPQS with controlling arguments are now provided. (The
function Factor has been removed.)
New verbose flag Factorization.
Primality proving is now performed using Morain's ECPP package
(automatically called by the function IsPrime, etc.). The functions
Primality and PrimeCertificate have been removed. New equivalent
functions will follow soon which will be based on the ECPP package.
An expanded version of the Cunningham database of factorizations of
integers having the form a^n+/-1 compiled by Brent and associates
(containing 199,044 factorizations for all bases less than 1000).
Probabilistic primality testing of integers (function IsProbablePrime).
Functions EulerPhi, CarmichaelLambda, MoebiusMu, and DivisorSigma now
allow a factorized integer as argument.
New functions FactoredEulerPhi and FactoredCarmichaelLambda which
return their results as factored integers.
Changes:
Function InverseMod renamed to Modinv.
Function Order (taking 2 integers) renamed to Modorder.
Rational Field and Rational Function Fields, [HB 26, 31]
Improved algorithms have been introduced for performing arithmetic on
the elements of both the rational field and rational function fields.
This has lead to a substantial speed-up for algorithms that make
extensive use of rational arithmetic. Specialized fraction-free matrix
and polynomial algorithms have also been introduced for these fields.
Summary of new features:
Computation of the (complete) squarefree partial fraction decomposition
of a function field element (function PartialFractionDecomposition).
Finite Fields [HB 27]
Function IsPower to test whether an element of a finite field
is a power and to return the root if so.
Faster arithmetic in very large prime finite fields through use of
the new integer package and the Montgomery modular multiplication
algorithm (further improvements under development).
Univariate Polynomial Rings [HB 28]
New function Round which takes a polynomial over a subring
of the real field and rounds all of the coefficents to the nearest
integer.
New function HasRoot which takes a polynomial and returns a
single root if existent (more efficient particularly over finite
fields than computing all roots).
Multivariate Polynomial Rings [HB 29]
A range of improvements and optimizations have been made to the
Groebner Basis machinery which improves its performance over the
rational field (in particular, careful efficient use of the new integer
package has led to very significant improvements). The Groebner Walk
algorithm has been improved also in light of the new integer package
(constructions with weight vectors). New improved strategies for the
main Buchberger algorithm have been introduced, including (automatic)
homogenization of ideals, and new techniques for reducing the basis
during the computation. A grevlex Groebner basis for the Cyclic-7
roots example takes 930 seconds on a Sun Ultra 2. Many new features
have been added which are related to Invariant Theory.
Summary of new features:
New parameters Homogenize, ReduceInitial, and ReduceByNew for the
procedure Groebner to allow control of strategy.
A more efficient algorithm (the modular method) for computing
univariate and multivariate resultants has been implemented.
Multivariate GCD over Z and Q improved.
Function Reduce to reduce a basis and function
ReduceGroebnerBasis to reduce a (known) Groebner basis.
Groebner basis computation over function fields has been significantly
improved.
Functions HomogeneousComponent and HomogeneousComponents
for construction of homogeneous components of polynomials.
Functions MonomialsOfDegree and MonomialsOfWeightedDegree for
construction of all monomials of a given total degree or weighted
degree.
Function MinimalAlgebraGenerators for the construction of a minimal
generating set of a polynomial subalgebra.
Functions HomogeneousModuleTest and HomogeneousModuleTestBasis
for computing with a submodule over a subalgebra in a polynomial ring.
Multivariate GCD over finite fields fixed (included content in a
particular variable too many times for some inputs).
Invariant Rings of Finite Groups [HB 30]
The first stage of the Magma module for computing with invariant rings
of finite groups was released in V2.1. Magma V2.2 contains the second
stage of our planned invariant theory machinery.
Summary of new features:
The Reynolds operator has been improved significantly for matrix groups
over the rational field (fraction-free methods) and all other
computations over fields of characteristic zero have been sped up
significantly as a consequence of the new integer package.
A new algorithm developed by Gregor Kemper (late 1996) for computing
primary invariants guarantees that the degrees of the invariants
constructed are optimal (with respect to their product and then sum)
(function PrimaryInvariants).
Similarly, a new improved algorithm developed by Gregor Kemper (early
1997) for computing secondary invariants in the modular case has been
implemented (function SecondaryInvariants).
It is now possible to determine the (algebraic) relations between
secondary invariants using the functions Relations and RelationIdeal
(also algebra presentation given by function Algebra).
Irreducible secondary invariants (which generate all secondary
invariants under multiplication) may be accessed (function
IrreducibleSecondaryInvariants).
Function FundamentalInvariants has been vastly improved by using
irreducible secondary invariants and a new minimalization algorithm.
A free resolution of an invariant ring (i.e. of its corresponding module)
may be computed (function FreeResolution).
Depth and homological dimension of an invariant ring computable
(functions HomologicalDimension, Depth).
Construction of Steenrod operations (function SteenrodOperation).
Many attributes of invariant rings may also be set or examined by the user
(using the new user-attribute mechanism).
Known invariants of a particular degree may be set (procedure
SetAllInvariantsOfDegree).
Algebraic Number Fields [HB 33, 34]
The arithmetic for cyclotomic and quadratic fields has been completely
rewritten to take maximum advantage of the new integer package. This
has led to significant speed-ups.
Summary of new features:
New functions GaussianIntegerRing, EisensteinIntegerRing.
Memory leaks in the code for solving norm equations have been fixed.
Bugs occurring on 64-bit machines in class group computation of
quadratic fields have been fixed.
Bugs occurring on 64-bit machines in galois group computations have
been fixed.
Real and Complex Fields [HB 36]
Function Round now takes a Complex number and yields a Gaussian
integer.
Modules and Lattices
A powerful family of LLL algorithms have been developed. These are
based on the FP-LLL algorithms of Schnorr and Euchner. Different
variants on the main algorithm are provided to achieve optimized
performance in different situations. The case for the ring of integers
is specially optimized, particularly when the integers are small. C
double precision floating-point numbers are used for efficiency but
arbitrarily-sized integers are also handled robustly, avoiding overflow
problems. Another version works off the Gram matrix of a basis rather
than the basis itself. This algorithm is automatically used internally
whenever it is more efficient. Further optimizations are under
development.
Vector Spaces [HB 40]
Tensor product of vector spaces and their elements (function
TensorProduct).
Modules Hom(U, V) [HB 42]
LLL algorithms for a lattice defined either by a basis matrix or
a Gram matrix (functions LLL and LLLGram).
Modules over K[x_1, x_2, ..., x_n] [HB 43]
Free resolutions of modules (functions FreeResolution and
MinimalFreeResolution).
Finite Dimensional Algebras (New Category) [HB 44, 45, 46]
Creation of both associative and non-associative algebras
defined by structure constants.
Direct sums.
Creation of subalgebras, ideals, and quotient algebras.
Operations on subalgebras: intersection, products, powers.
Element operations and properties: arithmetic, identity,
unit testing, zero divisors, nilpotency.
Bases: dimension, independence, basis elements, coordinates
(for algebras defined over a field).
Algebra properties: associativity, commutativity, Lie properties.
Ideal structure: maximal and minimal ideals, Jacobson radical,
simplicity, semi-simplicity, composition series.
Operations for associative algebras: centre, centralizer,
idealizer, Lie product, commutator ideal, regular representation.
Group Algebras (New Category) [HB 47]
Creation of group algebras: both vector and term representation
of elements are supported -- allowing calculation in groups of
arbitrary size.
Creation of subalgebras, ideals, and quotient algebras.
Operations on subalgebras: intersection, products, powers.
Element operations and properties: arithmetic, identity,
unit testing, zero divisors, nilpotency, involution, support.
Bases: dimension, independence, basis elements, coordinates
(for algebras defined over a field).
Augmentation ideal, augmentation map.
Algebra and subalgebra properties: commutativity, ideal testing.
Ideal structure: maximal and minimal ideals, Jacobson radical,
simplicity, semi-simplicity, composition series.
Centre, centralizer, idealizer, annihilators, Lie product,
commutator ideal, regular representation.
Matrix Algebras [HB 48]
LLL algorithms for a lattice defined either by a basis matrix or
a Gram matrix (functions LLL and LLLGram).
A new algorithm to efficiently compute large powers of matrices over
finite fields has been installed. The algorithm works by computing the
Jordan form of the matrix, then directly writing down the appropriate
powers of the blocks and finally transforming to obtain the result.
Finite Planes [HB 54]
An improved version of Jeff Leon's algorithm for computing collineation
groups of projective planes has been installed. This is capable of
computing collineation groups of planes having order up to 81.
(Functions CollineationGroup and Isomorphism.)
Error-correcting Codes [HB 55]
Computation of the set of all words of a code having a specific weight
which consist of zeros and ones alone (function ConstantWords).
New version of minimum weight algorithm which allows for an early abort
from a minimum weight computation (function VerifyMinimumWeight).
Function ExtendCode now applies also to non-binary codes.