Links

Free systems and libraries for doing number theory and computer algebra

• GMP is GNU Multiple Precision Arithmetic Library. It supports arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. GMP is carefully designed to be as fast as possible, both for small operands and for huge operands. The speed is achieved by using fullwords as the basic arithmetic type, by using fast algorithms, with highly optimized assembly code for the most common inner loops for a lot of CPUs, and by a general emphasis on speed. Probably it is the fastest bignum library.

• Arjen K. Lenstra's LIP package. Lenstra's LIP is portable and not slow arbitrary precision integer C library. It supports basic arithmetic, bit manipulation, modular arithmetic, small prime generation, prime testing, factorization and others.

• Victor Shoup's NTL: A Library for doing Number Theory. NTL provides high quality implementations of state-of-the-art algorithms for:
  • arbitrary length integer arithmetic and arbitrary precision floating point arithmetic; NTL can be used in conjunction with GMP (the GNU Multi-Precision library) for enhanced performance;
  • polynomial arithmetic over the integers and finite fields including basic arithmetic, polynomial factorization, irreducibility testing, computation of minimal polynomials, traces, norms, and more;
  • lattice basis reduction, including very robust and fast implementations of Schnorr-Euchner, block Korkin-Zolotarev reduction, and the new Schnorr-Horner pruning heuristic for block Korkin-Zolotarev;
  • basic linear algebra over the integers, finite fields, and arbitrary precision floating point numbers.

• PARI/GP is a widely used computer algebra system designed for fast computations in number theory (factorizations, algebraic number theory, elliptic curves...), but also contains a large number of other useful functions to compute with mathematical entities such as matrices, polynomials, power series, algebraic numbers, etc., and a lot of transcendental functions. PARI is also available as a C library to allow for faster computations.

• Maxima is a computer algebra system based on DOE Macsyma. The source code is available. It has abilities such as symbolic integration, 3D plotting, and an ODE solver, but there is a lot of work yet to be done in terms of bug fixing, cleanup, and documentation.

• Axiom is an extremely powerful computer algebra system with a slightly different philosophy than Maxima. It is useful for research and development of mathematical algorithms. It defines a strongly typed, mathematically correct type hierarchy. It has a programming language and a built-in compiler.

• GNU bc is an arbitrary precision numeric processing language. Its syntax is similar to C, but differs in many substantial areas. It supports interactive execution of statements.

• Yuji Kida's UBASIC is a BASIC-like environment which is suitable for number theoretic investigations. UBASIC has the high precision integer, real and complex arithmetic, exact rational arithmetic and arithmetic of polynomials with complex, rational, or modulo p coefficients, as well as string handling and limited list handling capabilities. It runs under MS-DOS and is written in assembly language. It is really very nice and powerfull language. See UBASIC Home (Much in Japanese). See also Google UBASIC directory.

• ARIBAS is an interactive interpreter for big integer arithmetic and multi-precision floating point arithmetic with a Pascal/Modula like syntax.

• Givaro: a C++ library for arithmetic and algebraic computations. Its main features are implementations of the basic arithmetic of many mathematical entities: Primes fields, Extensions Fields, Finite Fields, Finite Rings, Polynomials, Algebraic numbers, Arbitrary precision integers and rationals (C++ wrappers over gmp) It also provides data-structures and templated classes for the manipulation of basic algebraic objects, such as vectors, matrices (dense, sparse, structured), univariate polynomials (and therefore recursive multivariate).

• LiDIA is a C++ library for computational number theory which provides a collection of highly optimized implementations of various multiprecision data types and time-intensive algorithms. The current release contains: Arithmetic Interfaces to cln, gmp, libI, piologie; Basic arithmetic over Z, Q, R, C, interval arithmetic, GF(2^n), GF(p^n); Factorization: Integer Factorization (Trial Division, Elliptic Curve Method, Quadratic Sieve with Lanczos algorithm), Factorization of Polynomials over finite fields, Factoring ideals of algebraic number fields; Lattice Basis Reduction; Linear Algebra over Z; Number Fields; Polynomials (template classes for univariate polynomials); Elliptic Curves (over the rationals and over finite fields, counting points on elliptic curves, generating cryptographically strong curves); Primality Proofing (probabilistic primality tests, new elliptic curve based primality proofer); Other Generic Data Types (vectors, matrices, power series, and hash tables implemented as templates).

• Project LINBOX is a collaborative effort among researchers at a number of locations. The goals are to produce algorithms and software for symbolic linear algebra, particularly using black box matrix methods, i.e. iterative methods requiring only the linear transform property of the matrix (that one can compute Ax --> y). No stable releases at present.

• See also SymbolicNet, It is a very good starting point to learn about symbolic computation and computer algebra systems.

• A lot of others links see at Keith Matthews's Number theory pages.

• AlgLib Multilingual library of algorithms by Sergey Bochkanov and Vladimir Bystritsky.