LiDIA : a library for computational number theory
Ingrid Biehl, Johannes A Buchmann, Thomas Papanikolaou · 1995
In this paper we describe LiDIA, a new library for computational number theory. Why do we work on a new library for computational number theory when such powerful tools as Pari [1], Kant [11], Simath [10] already exist? In fact, those systems are very useful for solving problems for which there exist efficient system routines. For example, using Pari or Kant it is possible to compute invariants of algebraic number fields and Simath can be used to find the rank of an elliptic curve over Q. However, building complicated and efficient software on top of existing systems has in our experience turned out to be very difficult. Therefore, the software of our research group is developed independently of other computer algebra systems. Over the past years we have been working on many problems of computational number theory such as factoring integers [5], computing discrete logarithms over finite fields [13], counting the number of points on an elliptic curve over a finite field [8], computing the class number of number fields [2], etc. In those projects software for many basic tasks was needed, for example a multiprecision integer and floating point arithmetic, a polynomial arithmetic, linear algebra routines, etc. However, reusing parts of the software written in one project as modules in other projects was almost impossible. There was not enough documentation, there were no well defined interfaces, in different projects different multiprecision integer arithmetic packages and memory managers were used. Therefore, the same algorithms were implemented many times and not always in the most efficient way. It seems to us that this is a typical situation in scientific computing.