The Magma tools for working with the integers are based on very fast integer arithmetic. Basic arithmetic is performed mainly by Magma code developed by A. Steel in 1995, with GMP (The GNU Multiple Precision Arithmetic Library) linked in and used for some base cases of multiplication, division, and GCD. The algorithms used are all asympotically fast.
The other key tasks when computing with the integers are to be able to factor integers, including large numbers, and also to establish that an integer is a prime. The latter breaks up into two separate problems: fast probabilistic primality testing and primality proving (where a certificate is provided). All three problems arise frequently (often for reasonably large integers) in algorithms in all areas of the system.
Primality testing/proving is hard coded for reasonably small integers (it has been established by brute force computation that a certain procedure suffices). For other integers, the default probabilistic test consists of twenty iterations of the Miller–Rabin test. When a proof is desired, the probabilistic test is followed by invoking an implementation by Morain of the elliptic curve primality proving (ECPP) method. A primality certificate can be obtained from the same routine in terse form, and then another function can be used to translate this into a human-readable mathematical proof. An ingredient in the ECPP algorithm is a table of precomputed “Weber” polynomials related to modular curves. The Magma routine uses Morain's 1998 extended table.
Suppose n is a square-free integer whose factorisation is sought. The algorithms for integer factorisation in Magma fall into two families. The first family is characterised by the fact that the runtime (for extracting one factor) depends upon the size of the smallest prime factor so given a large n they are used to quickly locate small factors. The algorithms of this type available in Magma are trial division, table-driven factorisation of integers of the form bk±1, Pollard's rho and p – 1 algorithms, Shanks' SQUFOF algorithm, and Lenstra's elliptic curve method (ECM). The second group comprises algorithms whose running time depends solely on the size of n. The Multiple Polynomial Quadratic Sieve (MPQS) and the Number Field Sieve (NFS) are the representatives of this family installed in Magma.
Magma's automated factorisation routine, by default, uses the following techniques controlled by parameters depending on the size of the input: trial division, checking for Cunningham factors, SQUFOF, Pollard methods, elliptic curve factorisation, and, lastly, the multiple polynomial quadratic sieve. Zimmerman's GMP-ECM code provides an implementation of the ECM and the Pollard methods. The MPQS code was designed and implemented by A. Lenstra. The number field sieve in Magma was implemented by S. Contini (Magma). Both of these sieves are able to exploit multiple cores.
Factorisation of integers of the form n = bk±1, where b and k are not too big, uses R. Brent's factor algorithm, which employs a combination of table lookups and attempts at “algebraic” factorisation (Aurifeuillian techniques). The tables contain 385,251 factors f of numbers bk±1, where b < 10000, k < 10000, and f > 109. For b ≤ 12 these are mainly from the Cunningham tables (for k up to 1200) while for 13 ≤ b ≤ 99 they are mainly from the Brent–Montgomery–te Riele extension of the Cunningham tables. For more information consult Richard Brent's website. The ability to factor integers of the form bk – 1 is of considerable importance when working with the multiplicative group of a finite field. For instance, it allows much faster computation of the order of a non-zero element of the field.
The ring ℤ/Nℤ (for composite N) is a fundamental structure which is the basis for some nontrivial (computational) problems. Many algorithms require the calculation of square roots modulo N or a primitive root mod N and Magma has very efficient algorithms for these tasks. Dirichlet characters modulo N are essentially characters on the multiplicative group of ℤ/Nℤ. They are basic objects used in constructions in all areas of number theory, from elementary problems to complicated objects such as L-functions and modular forms. Magma contains a well-developed package for working with Dirichlet characters.
One of the simplest Diophantine equations encountered is Pell's equation, where it is desired to find integer solutions of the equation x2 – dy2 = 1. It is well known that Pell's equation can be solved by calculating the continued fraction of √d and Magma can perform the necessary continued fraction calculations. Alternatively, it can be solved by calculating units in the ring ℤ[√d] as discussed in the section on Algebraic Number Theory. Another Diophantine problem is to find an integer solution to the conic equation Ax2 + By2 + Cz2 = 0. Note that finding one solution yields a parametrisation of all solutions.
As it happens, conics are particularly important Diophantine equations from the point of computational algebra generally. For example, solving conics is a necessary step in some algorithms for decomposing algebras and constructing group representations. Simon's algorithm for solving conics with integer or rational coefficients has been implemented by M. Watkins (Magma), as has Simon's algorithm for the more general problem of finding an isotropic subspace for a quadratic form in more variables. Conics over number fields require a different algorithm, which is discussed in the section on Algebraic Number Theory.