Cryptography in C and C++

IF THERE BE ANY LINGERING doubt in the mind of the reader as to the attractiveness and utility of algorithmic number theory, a glance at the large number of web sites that treat this topic should bring doubt to any such doubt at once, perhaps even by overwriting the reader's cerebral registers. Just punch the search string "number theory" into your favorite Internet search engine, and up pop thousands of entries, a few of which have already been cited in this book. Many of these web sites contain links to available software packages or enable such packages to be downloaded. Such offers encapsulate a large bandwidth of functions for large-integer arithmetic, algebra, group theory, and number theory, demonstrating the efforts of many able and enthusiastic developers.

An extensive list of sources for such software packages can be found on the Number Theory Web Page, managed by Keith Matthews (University of Queensland, Brisbane, Australia). The web site is located at

• http://www.math.uq.edu.au/~krm/web.html,

with an American mirror site at

• http://www.math.uga.edu/~ntheory/web.html

and a UK mirror site at

• http://www.dpmms.cam.ac.uk/Number-Theory-Web/web.html.

The site also contains links to universities and research institutes as well as pointers to publications on relevant topics. In sum, this site is a veritable treasure trove. The following overview represents a small selection from the list of available software packages:

• ARIBAS is an interpreter that executes arithmetic and number-theoretic functions for large integers. ARIBAS implements the algorithms from [Fors] in Pascal. ARIBAS can be obtained as a supplement to that book, by anonymous ftp, from the directory pub/forster/aribas under ftp.mathematik.uni-muenchen.de or from http://www.mathematik.uni-muenchen.de/ forster.

• CALC, by Keith Matthews, is a calculation program for arbitrarily large integers that takes commands on a command line, executes them, and displays the results. CALC makes available about 60 number-theoretic functions. The package is implemented in ANSI C and uses the parser generator YACC or BISON for parsing the command line. CALC can be obtained from ftp://www.maths.uq.edu.au/pub/krm/calc/.

• GNU MP, or GMP, from the GNU project, is a portable C library for arithmetic with arbitrarily large integers, as well as rational and real numbers. GMP achieves excellent performance due to the use of assembler code for an impressive array of CPUs. GMP can be obtained via ftp from www.gnu.org,prep.ai.mit.edu, as well as GNU mirror sites.

• LiDIA is one of the software libraries developed at the Technical University Darmstadt for number-theoretic calculations. LiDIA contains an extensive collection of highly optimized functions for calculating in , , , , , , as well as for interval arithmetic. Current factorization algorithms are also implemented, such as for lattice base reduction, linear-algebraic algorithms, methods for calculating in number fields, and polynomials. LiDIA supports interfaces to other arithmetic packages, including the GMP package. LiDIA's own interpreted language LC facilitates, through its support of C++, the transition to translated programs. All platforms are supported that permit the use of long file names and for which a suitable C++ compiler is available, such as Linux 2.0.x, Windows NT 4.0, OS/2 Warp 4.0, HPUX-10.20, Sun Solaris 2.5.1/2.6. A port to the Apple Macintosh is also available. LiDIA can be obtained at http://www.informatik.tu-darmstadt.de/TI/LiDIA.

• Numbers, by Ivo Düntsch, is a library of object files that provide basic number-theoretic functions for numbers with up to 150 decimal digits. The functions, written in Pascal, and the interpreter, contained in the package as well, were developed with the goal of providing students with nontrivial examples and experiments in calculation. The source for Numbers is http://archives.math.utk.edu/software/msdos/number.theory/num202d/.html.

• PARI is a number-theoretic package by Henri Cohen et al. that implements the algorithms presented in [Cohe]. PARI can be used as an interpreter and as a function library that can be linked to programs. Through the use of assembler code for various platforms (UNIX, Macintosh, PC, and others) a high level of performance is achieved. PARI can be obtained at www.parigp-home.de.