Here is a terse summary of the new features installed in Magma for release version V2.20 (April 18, 1997).
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:
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:
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:
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 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:
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.