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 2N-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.

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.)

MIT Laboratory for Computer Science