Factoring Repunits

A friend asked me about prime numbers with only ones in their decimal representation, numbers such as 11, 1111111111111111111, and 11111111111111111111111. Such numbers are known as prime repunits, and can be expressed as (10ⁿ‒1)/9. I wrote a program using GMP for looking for such primes and then ran it for numbers with up to 45000 digits. It took a while, and I didn't find any new prime repunit. The currently known prime repunits have 2, 19, 23, 317, 1031, 49081, 86453, 109297, 270343, 5794777, and 8177207 digits.

Then I switched attention to factoring repunits as well as numbers of the form 10ⁿ+1. (Note that repunits can be expressed as (10ⁿ‒1)/9 and are thus of a similar algebraic form.) Paul Zimmermann had just implemented his GMP-ECM program for the ECMNET project, so I started to run that program on a number of Alpha computers. So far the program has helped me to find thousands of previously unknown factors.

Factor files:

Factors of 10ⁿ‒1, n < 1000 (updated irregularly)
Factors of 10ⁿ+1, n < 1000 (updated irregularly)
New factors of 10ⁿ‒1, n < 10000 (updated daily)
New factors of 10ⁿ+1, n < 10000 (updated daily)

Please note that algebraic factors are not included in these tables. Intrinsic factors are however included.

Additional factors for numbers with exponents larger than 1000 can be found elsewhere.

Countless people have contributed factors to these tables over several decades, among them R. Brent, R. Silverman, P. L. Montgomery, S. Wagstaff, A. K. Lenstra, F. Morain, H. Dubner, B. Dodson, Baillie, Yousuke Koide, Atkin and Rickert, Davis and Holdridge, Paul Zimmermann.

Running GMP-ECM efficiently (last updated 2011-02-01)

If you want to maximize the outcome of your factoring work, you need to spend some time on understanding how to run GMP-ECM efficiently. This is a non-trivial task, but the result might be that you find many more factors without using more processor cycles.

Start with a recent GMP release.
When building GMP-ECM, run make tune between configure and make. Make sure to pass --with-gmp-blabla to configure to point to your newly built GMP. (There is a --help option that lists the available options, and what they do.)
Consider passing -no-ntt to the ecm command. I've yet to see an example where GMP-ECM's NTT code wins over the GMP multiplication code. (When you compare the speed, be aware of that the B2 bounds are rounded differently with and without NTT.)
If you run GMP-ECM on a multiprocessor of some sort, it is important to tune GMP-ECM's memory access patterns. While stage 1 is cache friendly, stage 2 requires memory that is a function of the B2 bound, which might be hundreds of megabytes. Access to this memory also has poor locality, as GMP-ECM and GMP are currently implemented.
I've written a C program for running GMP-ECM on multiprocessors. It requires that cofactors are stored in separate files, and that a directory ../cracked exist for storing factorization reports. The idea of the program is to run as few parallel stage 2 as possible. For some additional usage instructions, see the output of -help from the program. Or mail me at the address below and ask.
The default B2 is usually too small, in particular when using -no-ntt with a recent GMP release. The ecm command provides a -v option that gives various output, among them a useful estimate of the required time to find a certain factor size. Use that for tuning B2 on your machine!