LiDIA - C++ library for computational number theory
April 13th, 2006 by cplus
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. LiDIA is developed by the LiDIA Group at the Darmstadt University of Technology. LiDIA is free for non-commercial purposes (license) and comes with the full source code. The current release of LiDIA contains the following components:
- Arithmetic Interfaces to cln, gmp, libI, piologie.
- Basic arithmetic over Z, Q, R, C, interval arithmetic, GF(2n), GF(pn).
- Factorization: Integer Factorization (Trial Division, Elliptic Curve Method, Self-Initializing Multipolynomial Quadratic Sieve with Lanczos algorithm), Factorization of Polynomials over finite fields (V. Shoup’s algorithms), Factoring ideals of algebraic number fields.
- Lattice Basis Reduction: various versions of LLL/MLLL (Schnorr-Euchner, Benne de Weger).
-
Linear Algebra over Z: basic operations, normal forms of matrices (G. Havas algorithms)
Number Fields: Quadratic Number Fields including a new implementation of Buchmann’s sub exponential algorithm for computing classgroups using mpqs techniques, Higher-Degree Number Fields arithmetic and maximal order. - Polynomials: template classes for univariate polynomials with special algorithms for different domains.
- Elliptic Curves: elliptic curves over the rational and over finite fields (includes code written by J.Cremona and N. Smart). There is also a package for counting points on elliptic curves as well as a package for generating cryptographically strong curves.
- Primality Proofing: Besides the standard probabilistic primality tests in the base package there is a new elliptic curve based primality proofer in the GEC package.
- Other Generic Data Types: vectors, matrices, power series, and hash tables implemented as templates.
