A few number-theoretic trifles

by Garrett A. Wollman

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(6)) from standard input, and lists the actual factors (and any exponents) on standard output.
• 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.)