It is essential for a general computer algebra system to include good algorithms for the fundamental problems of integer factorisation and primality testing. The latter breaks into two separate problems: (fast) probabilistic primality testing, and primality proving (providing a certificate). All three problems are very frequently needed (for integers of moderate size) in algorithms in all areas of the system. Magma does not aim to be state-of-the-art but to provide fast reliable routines suitable for general purpose use. For record factorisations and so on, one would naturally use custom software.
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 (finally) multiple polynomial quadratic sieve. The implementation of ECM (together with the Pollard methods) is a version of Zimmerman's GMP-ECM which has been installed in Magma. Magma also contains a number field sieve implementation (Contini); this must be called explicitly as it is not incorporared in the automated routine. The quadratic sieve and number field sieve are able to use multiple cores (the user must start the additional processes manually).
The factoristion 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 a < 12 these are mainly from the Cunningham tables (for k up to 1200), while for 13 < a < 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.
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 calling an implementation of elliptic curve primality proving (Morain). A primality certificate can be obtained from the same routine (in terse form, then another function can translate this to 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 calls on Morain's extended (1998) table.
The ring ℤ/Nℤ (for composite N) is a fundamental object which holds some nontrivial (computational) problems. Many algorithms require one to calculate square roots mod N or a primitive root mod N. Efficient algorithms for these tasks are provided in Magma. 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, as well as group theory. Magma contains a well developed package for dealing with Dirichlet characters with all these purposes in mind.
One of the simplest Diophantine equations encounted is Pell's equation: to find integer solutions to x2 – dy2 = 1. The theory is well known; this can be solved by calculating the continued fraction of √d (and Magma can perform standard continued fraction calculations), or it can be solved by calculating units in the ring ℤ[√d].
Another Diophantine problem is to find an integer solution to a conic equation Ax2 + By2 + Cz2 = 0. (Finding one solution yields a parametrisation of all solutions.) As it happens, conics are the most important Diophantine equations from the point of computational algebra generally; solving conics is a necessary step in algorithms for decomposing algebras and constructing group representations. Magma contains a good implementation (by M. Watkins) of Simon's algorithm for solving conics with integer (or rational) coefficients, and also Simon's algorithm for the more general problem of finding an isotropic subspace for a quadratic form in more variables.