From: strauch@emmy.mathematik.uni-dortmund.de (Michael Strauch) Newsgroups: sci.math Subject: Re: Help->Large numbers C lib? Date: 26 Jan 1995 08:08:39 GMT Pechus (a900423@zipi.fi.upm.es) wrote: > I need C libraries for handing with enormous numbers, say a hundred or > two of hexadecimals. If someone could giveme an adress for ftp or anything I > would be able to continue with my program for large primes. > I suppose I'm not the first one asking for this ( and won't be the > last) but, come on, a little effort will help me a lot. I append a copy of a previous post that will surely help you. From the list I have only tested the "Integer" class from GNU-C++; this one worked fine for me, but perhaps you don't want to use GNU or C++. - Michael - strauch@emmy.mathematik.uni-dortmund ------------------ cut here ----------------------------------------------------------- Path: Chemietechnik.Uni-Dortmund.DE!Informatik.Uni-Dortmund.DE!Germany.EU.net!EU.net!howland.reston.ans.net!agate!msuinfo!scss3.cl.msu.edu!mrr From: mrr@scss3.cl.msu.edu (Mark Riordan) Newsgroups: sci.math Subject: List of Arbitrary Precision C packages Date: 27 Jan 1994 16:06:01 GMT Organization: Michigan State University Lines: 368 Message-ID: <2i8op9$tca@msuinfo.cl.msu.edu> NNTP-Posting-Host: scss3.cl.msu.edu Summary: Free packages via FTP X-Newsreader: TIN [version 1.2 PL1] This is the file BIGNUMS.TXT from ripem.msu.edu, last updated January 1994. In response to Email requests, I have assembled this list of large-integer arithmetic packages of which I have heard. Most of these are C function libraries, available in source form. A few also deal with floating point numbers. For your convenience, I have placed copies of some of these on ripem.msu.edu (35.8.1.178). They are available for anonymous FTP in the directory "pub/bignum". However, what I have may not be the most current version in all cases. Here they are, in no particular order: mp Multiple Precision package that comes with some Unixes Multiple precision package accessed via -lmp flag on your compiler. Provides +, -, *, /, gcd, exponentiation, sqrt. Comes with SunOS, NeXT Mach, BBN Mach 1000, and probably a few others. See "man 3 mp". Object code only, of course. PARI Henri Cohen, et al., Universite Bordeaux I, Paris, FRANCE Multiple precision desk calculator and library routines. Contains optimized assembly code for Motorola 68020, semi-optimized code for SPARC, and apparently rather slow generic C version. Does both integers and reals. Does vectors and matrices as well as scalars. Contains a number of advanced functions, some of which I've never heard of. ("Weber's function"?) Has a factorization function, primality test, & other related stuff. Plenty of TEX documentation. Public domain, but you can't distribute modified versions. Available via anonymous FTP from ftp.inria.fr:lang/ and math.ucla.edu. The ucla site has Mac, MSDOS, OS/2, and NeXT-specific versions there in addition to: Filename: pari-1.37.tar.Z (There are now more recent versions) Arithmetic in Global Fields (Arith) Kevin R. Coombes, David R. Grant Package of routines for arbitrary precision integers or polynomials over finite fields. Includes basic +, -, *, / and a few others like gcd. Source code in C. Distributed under the terms of the GNU public license. Includes man pages and TEX documentation. Filename: arith.tar.Z Arbitrary Precision Math Library Lloyd Zusman Los Gatos, CA C package which supports basic +, -, *, /. Provides for radix points (i.e., non-integers). Not as polished as the others here. Posted to comp.sources.misc in October 1988. Filename: apml.tar.Z BigNum J. Vuillemin, INRIA, FRANCE, and others. Distributed by Digital Equipment Paris Research Lab (DECPRL) A "portable and efficient arbitrary-precision integer" package. C code, with generic C "kernel", plus assembly "kernels" for MC680x0, Intel i960, MIPS, NS32032, Pyramid, and of course VAX. This is probably one of the better-known packages of this type. Implements +, -, *, /, mod, plus logical operations OR, AND, XOR. Both signed and unsigned arithmetic available. Available via email from librarian@decprl.dec.com. You will receive 5 shell archives. Give your postal address and you will also receive printed documentation from France. Package includes TEX documentation. Publicly available for non-commercial use. I removed this from my archive when I heard a rumor that PRL doesn't like others to distribute it. However, BIGNUM *is* distributed as part of ecpp (see below). Lenstra's LIP package Arjen Lenstra Bellcore Portable unsigned integer package written entirely in C. Includes +, -, *, /, exponentiation, mod, primality testing, sqrt, random number generator, and a few others. An earlier version of this package is the only of these packages I have actually used. It works well and is very portable. I haven't done any benchmarks against the others, but the code looks clever & Lenstra is an accomplished number theorist. LIP replaces lenstra-3.1.c. The package now includes encrypted source code; to obtain the decryption key, you must send a signed license agreement to Bellcore. See the documentation. Filename: lenstra-LIP-package.tar This is a collection of all the files in flash.bellcore.com:/pub/lenstra bmp (Brent's Multiple Precision?) R. P. Brent 1981 vintage FORTRAN code to do extended precision floating & fixed point arithmetic. Includes most of the mathematical functions you'd find in a FORTRAN run-time library. This code is an ACM algorithm, number 524. To obtain, send a mail message to netlib@ornl.gov containing the line "send mp.f from bmp" or better yet, perhaps just start with "help". SPX Kannan Alagappan & Joseph Tardo, DEC This is a huge prototype public key authentication system based on RSA. I mention it here because those who have heard of SPX have probably correctly guessed that it contains a large integer package and I want to inform you that the large integer package it contains is indeed DEC's BigNum from France. You can get a beta test copy of SPX from crl.dec.com (192.58.206.2). Use it only for testing, as it "may" expire on a certain date. (I don't know whether this has expired yet.) amp (Antti's Multiple Precision?) Antti Louko alo@kampi.hut.fi Multiple precision integer package in C. Includes +, -, *, /, %, pow, mod, 1/x mod y, random, sqrt, gcd. Available for non-commercial use. The package includes "share-secret", a public key system based on the Diffie-Hellman algorithm. This is normally part of the well-known "des-dist.tar.Z", but I have removed the DES part to avoid having to deal with cryptographic export laws, and have named the result: Filename: amp.tar.Z gennum Per Bothner U of Wisconsin-Madison C++ routines and classes to do generic arithmetic, both integer and rational. Part of the "Q" programming system. Distributed under the terms of the GNU public license. Obtained from cygnus.com. Filename: gennum.tar.Z MIRACL (Shamus Software, Dublin, Ireland) Integer and fractional multiple precision package. MIRACL is a portable C library. Full C/C++ source code included (In-line assembly support for 80x86). Number theoretic primitives needed to support PK Cryptography are supplied. C++ classes for Multiprecision Integers, Modular arithmetic, and Chinese Remainder Thereom. Implementation in C/C++ of all modern methods of Integer Factorisation, viz Brent-pollard, p-1, p+1, Elliptic Curve, MPQS. Includes TEX manual and some DOS .EXEs. Not public domain, but free for academic and non-commercial use. Obtained from ftp.compapp.dcu.ie. Filename: /pub/crypt/other/miracl-3.23.zip and miracl.tar.Z (older) precision Dave Barrett barrettd@tigger.colorado.edu Multiple precision integer package in C with +,-,*,/, sqrt, rand, mod, pow, log. Simple vector support. Does dynamic allocation of memory. Free as long as you don't sell it or any program that uses it. Filename: precision.tar.Z UBASIC Prof. Yuji Kida, Rikkyo University, Nishi-Ikebukuro 3, Tokyo 171, Japan kida@rkmath.rikkyo.ac.jp Multiple-precision version of the BASIC programming language, for MS-DOS. Includes floating point. Said (by Keith Briggs) to be pretty fast. Object only, I think. ervin@morekypr.bitnet says: "This is the best package that I know of for fast arithmetic. Has a version optimized for 386 machines. Includes routines to do MPQS, the fastest currently known general factoring algorithm. An additional file is at both sites to allow MPQS to use hard drives so that it can factor up to 80 digits. Many number theoretical functions are included in UBASIC. It allows over 2500 digits of precision." Available via anonymous FTP from shape.mps.ohio-state.edu, or simtel20.army.mil, or wuarchive.wustl.edu. calc_v22 Unknown MS-DOS C-like language that allows "infinite" precision. Nice intrinsic functions. ervin@morekypr.bitnet reports problems when changing precision on the fly. See simtel20 or wuarchive. briggs_arith Keith Briggs (kbriggs@maths.adelaide.edu.au) Turbo Pascal 5 source for routines that do multiple-precision +, -, *, /, sqrt, gcd, factoring, rand for integers; also includes +, -, *, / and rand for rational numbers. Filename: briggs_arith.pas Institute fur Experimentelle Mathematik Dr Gerhard Schneider (?) Fast C multiple-precision subroutine library. I don't know anything about it; sl25@ely.cl.cam.ac.uk says to contact MAT420@DE0HRZ1A.BITNET for more info. Postal Address: Institute fur Experimentelle Mathematik EllernStr 29 D4300 Essen-12 GERMANY LongInt Markus Mueller (mueller@komsys.tik.ethz.ch) "Multi precision arithmetic written in MODULA-2, with the most time critical parts written in Assembler. Includes basic arithmetics (+, -, *, /, %) as well as arithmetics MODULO a number. An additional module provides a collection of procedures for primality testing, gcd, multiplicative inverse and more. The package is part of a Privacy Enhanced Mail (PEM) package which includes a PEM mailer, RSA key generator and Certificate generation tools." Source is in Modula-2, C, and assembler for Sun 3. LongInt has also been ported to MS-DOS under Logitech Modula-2 and Turbo Assembler. Availability: free for university use (research and education); otherwise, a source license is required. To obtain, write or email to: Markus Mueller Bertastrasse 7 CH-8953 Dietikon Switzerland email: mueller@komsys.tik.ethz.ch bignum-1.2 Henrik.Johansson@Nexus.Comm.SE Bignum package written in portable C. Will in the future conform to the Common Lisp functions that handles integers. Currently includes +, -, *, /, exponentiation, "exptmod", comparison, random numbers, and gcd. Filename: bignum-1.2 ACM algorithm 567 D.W. LOZIER and J.M. SMITH FORTRAN subroutines to do extended-precision floating point and normalized Legendre polynomials. ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 7,1 (MARCH, 1981) Obtained from research.att.com:netlib/toms/567.Z Filename: acm-algorithm-567-floating-point.fortran.Z range O. Aberth and M. J. Schaefer C++ package to do extended-precision floating point arithmetic with programmer-defined precision. Uses decimal representations internally. Contains basic +, -, *, /, relational operators, ++, and a few functions like sin, cos, sqrt, log. Documentation a trifle confusing. Obtained from math.tamu.edu:pub/range/range.tar.Z Filename: range.tar.Z bsint Author unknown. Pre-alpha release of C++ big integer package. Implements basic math operators, exponentiation, and modular exponentiation. Very skimpy documentation. See milton.u.washington.edu:/pub/user-supported/tzs/bsint.tar.Z GNU Multiple Precision (GMP) GNU (Free Software Foundation) multiple precision package. I haven't looked at it yet. This is current as of April 1992, but there may be a more recent version by the time you read this. This package is very widely available on FTP sites. Filename: gmp-1.3.2.tar.Z libg++ - GNU's C++ class library Free Software Foundation Includes Integer and Rational classes. Integer provides the usual C++ operators, plus exponentiation, gcd, lcm. Limited functionality, but documentation is better than most. Look for libg++-2.4.tar.gz on an FTP server near you. Elliptic Curve Primality Proving Francois Morain, France. Large package to prove the primality of any prime. Includes Inria's BIGNUM package. Obtained from ftp.inria.fr (128.93.1.26). Filename: ecpp.V3.4.1.tar.Z PGP (Pretty Good Privacy) Philip Zimmermann prz@sage.cgd.ucar.EDU Crypto package that includes bignum routines in C. Assembly implementations available for several processors; said to be quite fast for numbers around 1000 bits in size. The crypto package violates RSA patents, but the bignum routines can be used without fear of legal repercussions. Bell's Arbitrary Precision Calculator David I. Bell, Australia (dbell@pdact.pd.necisa.oz.au) Arbitrary-precision calculator with good online help, C-like language, many builtin functions, support for integers, rational numbers (they work like floating point), complex numbers, matrices, strings, lists, files, "objects". Includes gcd, primality testing, even trig functions. Recommended. (Large package, though.) Obtained from comp.sources.unix. Filename: calc-1.24.7.tar.Z Calc for GNU Emacs Dave Gillespie (daveg@synaptics.com) Advanced calculator written in Emacs Lisp. Includes arbitrary precision integers and floating point, bitwise operations, log and trig functions, financial functions, number theoretic functions including prime factorization, symbolic calculus, and an interface to GNUPLOT. Filename: calc-2.02a.tar.Z MPFUN: A Multiple Precision Floating Point Computation Package David H. Bailey (dbailey@nas.nasa.gov) Package of Fortran subroutines to perform multiprecision floating point arithmetic. Also includes a program that can automatically convert ordinary Fortran-77 code into code that calls the MPFUN routines. Keith Briggs says: "It's a masterpiece, and the state of the art as far as Fortran goes." Documentation in TeX format. Unrestricted distribution allowed at no cost. Filenames: mpfun_fortran.tar.Z & mpfun_tex_papers.tar.Z MPQS Mark S. Manasse (msm@src.dec.com) and Arjen Lenstra C program to factor numbers on a distributed network of heterogeneous machines. June 1993 version. Filename: mpqs-distributed-factoring.shar GNU bc Author: Philip A. Nelson (phil@cs.wwu.edu) GNU bc is an interactive algebraic language with arbitrary precision. GNU bc is almost the same as bc & dc in some Unixes. Filename: bc-1.02.tar.z (for example, in GNU prep.ai.mit.edu:pub/gnu/) bc & dc bc is an interactive processor for an arbitrary precision arithmetic language or just compiler/preprocessor for dc calculator with arbitrary precision; they comes with some Unixes. Built-in support in other languages Various Multiple precision arithmetic is available in a number of programming languages, such as Lisp and ABC (cf. mcsun.eu.net). Version 8 of the programming language Icon (Griswold's successor to SNOBOL4 available from cs.arizona.edu) has large integers. Perl (by Larry Wall, available from devvax.jpl.nasa.gov) includes source, in Perl, for such a package, but it's probably not suitable for serious use. For some of these, source code may be available. This list is long enough, so I'm not going to pursue it aggressively. Thanks to Keith Briggs and several others who contributed to this list. See also other sites, such as nic.funet.fi:pub/sci/math/multiplePrecision/. Mark Riordan mrr@ripem.msu.edu