APPENDIX C

Software Tools

This appendix lists software tools of interest to practitioners and educators. The listing is separated into two sections. §C.1 includes research and other tools, most of which are fairly general-purpose and do not necessarily require programming. §C.2 entries are more specialized or contain libraries to be used with programming languages such as C. Generally speaking, §C.1 is of interest to those involved in education and with prototyping, while developers may be primarily interested in §C.2. Researchers have used packages from both sections. The descriptions provided are, for the most part, adapted directly from those given by the package authors.

C.1 General-purpose tools

The entries in this section vary in capability and interface, with bc and calc as fairly basic tools, and Maple, Mathematica, and MuPAD offering sophisticated graphics and advanced user interfaces. Magma is significantly more specialized than tools such as Mathematica, and has excellent support for elliptic curve operations such as point counting. GAP and KANT/KASH can be regarded as the most specialized of the packages in this section.

bc http://www.gnu.org

bc is a language that supports arbitrary precision numbers with interactive execution. There are some similarities in the syntax to the C programming language. bc has the advantage of its wide availability and may be useful as a calculator and in prototyping. Keith Matthews has written several bc programs in number theory, http://www.numbertheory.org/gnubc/.

272 C. Software Tools

Calc http://www.gnu.org

Calc is an interactive calculator providing for easy large numeric calculations. It can also be programmed for difficult or long calculations. Functions are provided for basic modular arithmetic. Calc, developed by David I. Bell and Landon Curt Noll with contributions, is hosted on SourceForge, http://sourceforge.net/ projects/calc/.

GAP http://www.gap-system.org

GAP (Groups, Algorithms and Programming) is a system for computational discrete algebra with particular emphasis on computational group theory. Capabilities include long integer and rational arithmetic, cyclotomic fields, finite fields, residue class rings, p-adic numbers, polynomials, vectors and matrices, various combinatorial functions, elementary number theory, and a wide variety of list operations. GAP was developed at Lehrstuhl D f¨ur Mathematik, RWTH Aachen, Germany beginning in 1986, and then transferred to the University of St. Andrews, Scotland in 1997.

KANT/KASH http://www.math.tu-berlin.de/ kant/kash.html

The Computational Algebraic Number Theory package is designed for sophisticated computations in number fields and in global function fields. KASH is the KAnt SHell, a front-end to KANT. Development is directed by Prof. Dr. M. Pohst at the Technische Universit¨at Berlin.

Magma http://magma.maths.usyd.edu.au

The Magma Computational Algebra System “is a large, well-supported software package designed to solve computationally hard problems in algebra, number theory, geometry and combinatorics. It provides a mathematically rigorous environment for computing with algebraic, number-theoretic, combinatoric and geometric objects.” In particular, there is extensive support for elliptic curve operations.

Magma is produced and distributed by the Computational Algebra Group within the School of Mathematics and Statistics of the University of Sydney. “While Magma is a non-commercial system, we are required to recover all costs arising from its distribution and support.”

Maple http://www.maplesoft.com

Maple is an advanced mathematical problem-solving and programming environment. The University of Waterloo’s Symbolic Computation Group (Waterloo, Canada) initially developed the Maple symbolic technology. Maple is commercial—historically, student and academic licensing has been relatively generous.

C.2. Libraries

273

Mathematica http://www.wolfram.com

Mathematica is a general-purpose technical computing system, combining fast, high-precision numeric and symbolic computation with easy-to-use data visualization and programming capabilities. Wolfram Research, the developer of Mathematica, was founded by Stephen Wolfram in 1987.

MuPAD http://www.mupad.de

MuPAD is a general-purpose computer algebra system for symbolic and numerical computations. Users can view the library code, implement their own routines and data types easily, and can also dynamically link C/C++ compiled modules for raw speed and flexibility.

MuPAD was originally developed by the MuPAD Research Group under direction of Prof. B. Fuchssteiner at the University of Paderborn (Germany). Free licenses are available; commercial versions can be obtained from SciFace Software. Several books on MuPAD have been published, including the paperback MuPAD Tutorial: A version and platform independent introduction, by J. Gerhard, W. Oevel, F. Postel, and S. Wehmeier, Springer-Verlag, 2000.

C.2 Libraries

In contrast to most of the entries in §C.1, the packages in this section are more specialized. For example, some are libraries intended for programmers using languages such as C or C++.

The most basic is GNU MP, a library supporting arbitrary-precision arithmetic routines. It is recommended for its performance across many platforms. Crypto++ offers an extensive list of routines for cryptographic use, in an elegant C++ framework. OpenSSL, MIRACL, and cryptlib are similarly ambitious. Developed from SSLeay, OpenSSL is widely used in applications such as the Apache web server and OpenSSH, and has also been used strictly for its big number routines. MIRACL provides executables for elliptic curve point counting.

In addition to integer and polynomial arithmetic, LiDIA and NTL provide sophisticated number-theoretic algorithms. Along with PARI-GP, these tools may be of particular interest to researchers.

cryptlib http://www.cs.auckland.ac.nz/ pgut001/cryptlib/

Although elliptic curve methods are not included, the cryptlib security toolkit from Peter Gutmann is notable for its range of encryption, digital signature, key and certificate management, and message security services, with support for a wide variety of crypto hardware. In particular, cryptlib emphasizes ease of use of high-level services such as SSH, SSL, S/MIME, and PGP. The big number routines are from OpenSSL. The toolkit runs on a wide range of platforms, has a

274 C. Software Tools

dual-license for open source and commercial use, and substantial documentation is available.

Crypto++ http://www.eskimo.com/ weidai/cryptlib.html

Crypto++ is a free C++ library from Wei Dai for cryptography, and includes ciphers, message authentication codes, one-way hash functions, public-key cryptosystems, and key agreement schemes. The project is hosted on SourceForge, http://sourceforge.net/projects/cryptopp/.

GNU MP http://www.swox.com/gmp/

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. It focuses on speed rather than simplicity or elegance.

Libgcrypt http://www.gnu.org/directory/security/libgcrypt.html

Libgcrypt is a general-purpose cryptographic library based on the code from GnuPG (an OpenPGP compliant application). It provides functions for cryptographic building blocks including symmetric ciphers, hash algorithms, MACs, public key algorithms, large integers (using code derived from GNU MP), and random numbers.

LiDIA http://www.informatik.tu-darmstadt.de/TI/LiDIA/

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. In particular, the library contains algorithms for factoring and for point counting on elliptic curves. The developer is the LiDIA Group at the Darmstadt University of Technology (Germany).

MIRACL http://indigo.ie/ mscott/

The Multiprecision Integer and Rational Arithmetic C/C++ Library implements primitives supporting symmetric-key and public-key methods, including elliptic curve methods and point counting. Licensed through Shamus Software Ltd. (Ireland), it is “FREE for non-profit making, educational, or any non-commercial use.”

NTL: A Library for doing Number Theory http://www.shoup.net/ntl/

NTL is a high-performance portable C++ library providing data structures and algorithms for arbitrary length integers; for vectors, matrices, and polynomials over the integers and over finite fields; and for arbitrary precision floating point arithmetic. In particular, the library contains state-of-the-art implementations for lattice basis reduction. NTL is maintained by Victor Shoup.

C.2. Libraries

275

OpenSSL http://www.openssl.org

The OpenSSL Project is a collaborative effort to develop a robust, full-featured, and Open Source toolkit implementing the Secure Sockets Layer (SSL v2/v3) and Transport Layer Security (TLS v1) protocols as well as a general-purpose cryptography library. OpenSSL is based on the SSLeay library developed by Eric A. Young and Tim J. Hudson.

PARI-GP http://www.parigp-home.de

PARI-GP is a computer-aided number theory package, consisting of a C library and the programmable interactive gp calculator. Originally developed at Bordeaux by a team led by Henri Cohen, PARI-GP is now maintained by Karim Belabas at the Universit´ Paris-Sud Orsay with many contributors.

This page intentionally left blank