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 10^{35}.

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 ~~
Coq now has an implemenation of the theory of eliptic curves. This makes factoring this number no longer necessary for primality checking.`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.