I've been fiddling around with factoring (or proving the
primality of) very large numbers, to teach myself some number
theory and also put some of the computational resources in my
office to good use. I got started with George Woltman's GIMPS (Great
Internet Mersenne Prime Search), a long-running grid-computing
project. Although the source code to the GIMPS programs is
available, it's specific to IA32-architecture machines and to the
particular domain of Mersenne numbers. (Mersenne numbers are
numbers of the form 2^{N}-1; many of the largest known
primes are of this form.)

Woltman's Other Projects page led me to Paul Zimmermann's ECMNET project. Zimmermann provides portable source code for factoring numbers using the Elliptic Curve method. It is not as fast as Woltman's optimized Mersenne code because it is more general. Zimmermann's program uses the GNU Multiple Precision math library (libgmp) to perform the low-level arithmetic operations.

Through ECMNET I found Koide Yousuke's repunit
factoring project. A repunit is a number whose written form
(in whatever base is being used) contains only the digit
`1`; Mersenne numbers are repunits in base 2. His
project concerns only repunits in base 10, but other people are
investigating different bases.

During the course of my self-education, I have put together a number of small demonstration programs which perform a simple, well-defined operation on these large numbers, with the aid of libgmp. Some of these programs and scripts are available below.

`modexp.c`performs modular exponentiation, using the built-in libgmp function for that purpose. It is mostly here as a demonstration of a simple program that performs a libgmp operation and then displays the result. I originally wrote it because I wanted to understand how the SPRP test (see below) worked, and neither of my usual interactive arithmetic tools had a way to do modular exponentiation efficiently.`trial-factor.c`performs simple factoring by trial division. It reads a list of potential factors (which you might generate using`primes`) from standard input, and lists the actual factors (and any exponents) on standard output.*(6)*`sprp.c`performs a single strong probable-prime test à la Caldwell. It takes both the input number*n*and the base*a*as command-line arguments.`check-small-prime`is a shell script that builds on`sprp.c`to perform Jaeschke's primality test for integers less than 10^{14.5}, as described by Caldwell. It would not be too difficult to extend this script to perform Miller's Test.`repunit-factors.c`does trial division of (base-10) repunits by smaller repunits. See also my brief note about why this program isn't particularly useful.

All of these programs will require a system with a recent
installation of libgmp and with the 4.4BSD `err (3)`
family of C library routines. It would not be too hard to replace
the latter, but I do not care to do it. The error-checking of all
the programs is quite poor, so missing or badly-formatted input
may have unexpected results or give unhelpful error messages.

(Post scriptum: the AlphaServer 4100 I was using to do most of this has expired as a result of hardware failure -- although I believe I can resuscitate it. Meanwhile I've been working with much smaller numbers on my home PC, but do not have much to show for the effort at this time.)

wollman@lcs.mit.edu

MIT Laboratory for Computer Science