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 (10n‒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, and 270343 digits.
Then I switched attention to factoring repunits as well as numbers of the form 10n+1. (Note that repunits can be expressed as (10n‒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.
Here are up-to-date factor files:
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.
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.
make. Make sure to pass
configureto point to your newly built GMP. (There is a
--helpoption that lists the available options, and what they do.)
ecmcommand. 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.)
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.
ecmcommand provides a
-voption 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!