I know factoring numbers is really hard. The security of RSA is based on the difficulty of factoring the product of two prime numbers. However, I didn’t realize that factoring numbers in general was so hard.
The numbers used in RSA are generated to be particularly hard to factor. I figured most numbers were the product of a bunch of small primes. I figured in practice one would easily find several small factors and pretty soon the whole number would be factored. But this apparently isn’t the case.
Consider a somewhat typical number q − 1. If you try and factor it, you quickly find 2, 3851, and 4332967 are factors. Once you have removed all the small factors, then you are left with n, which is the product of big factors. At this point factoring becomes tough, really tough. It seems not likely to have a factor less than 1035.
This all started because I was trying to generate primality certificates to verify primes used in the Oakley groups.
If you want to help me on my insane quest, you can install the gmp-ecm Debian package. Then download the ECMNet 2.7.0 client/server source code, build it, and add your id (email address) and set the server to vacuumcleaner.cs.ru.nl in the ecmclient.cfg file. Alternatively, after installing gmp-ecm, you can download my prepared ECMNet client, and just add your id (email address) to the ecmclient.cfg file, make and run.
Or if you work for the NSA, feel free to anonymously post one of the factors of n as a comment.
Coq now has an implemenation of the theory of eliptic curves. This makes factoring this number no longer necessary for primality checking.