RSA100 factored!
The RSA challenge numbers have long served as a useful yardstick for our ability to factor generic integers (i.e. those having no special algebraic form.) I remember once asking Bob Silverman (of RSA Labs) whether, when they chose the similarsized primes p and q which are multiplied together to form each RSA number, they checked to make sure that none of p+1 or q+1 was sufficiently smooth so as to make the number vulnerable to the humble p1 or p+1 methods of factorization. He pretty much laughed that one off, saying that for sufficiently large p and q, the odds of p+1 or q+1 being smooth were essentially negligible. True, as the numbers get large the odds of a generically chosen integer being Ksmooth (K some smoothness bound) tend toward zero, but my reasoning was: since it's not difficult to check smoothness of p+1 and q+1, given the importance of the supposed hardtofactor property of the product, why not check and be sure?
Today I was looking at the list of RSA challenge numbers which have been factored, ranging from 100 to 155 digits (the largest of these, the 155digit, 512bit RSA155, was cracked just last year using GNFS), and for nearly all of these, it is indeed true that the p1 or p+1 method would have no chance of factoring the number. Note I said "nearly all." In fact, the smallest RSA challenge number I'm aware of, RSA100, which was cracked in 1991 using the thennew quadratic sieve algorithm, has the factorization
RSA100
Factors: 40094690950920881030683735292761468389214899724061 *
37975227936943673922808872755445627854565536638199
p1 = 2.3167.3613.587546788471.3263521422991.
865417043661324529.
p+1 = 2^3.3.5^2.109.409.20839813.60236089.49147216823.
23011759155976667.
q1 = 2^2.5.41.2119363.602799725049211.
38273186726790856290328531.
q+1 = 2.3.11.59.
10296530804037206222569012658644444886804031773.
Here, p denotes the smaller of the 2 factors and q the larger. Note how smooth p+1 is. That means that the p1 method with (luckily chosen) bounds B1 = 5e10 and B2 = 2.5e16 would find this factorization. To see roughly how long such a p1 run would take, I ran GMPECM in p1 mode to the smaller bounds 5e7 and 2.5e10. Each of these needed slightly less than 2 minutes on a 1GHz Alpha ev6, so to run to the above large bounds would need around 1 CPUday for stage 1 and around 3 CPUyears for stage 2. With a distributed stage 2 (note that stage 2 is perfectly distributable, i.e. each of N machines can work on its own interval with no interprocessor communication needed), the factorization time could be brought down to ~1000/N days. Of course MPQS and NFS could do it much quicker still, but I still found it interesting how much our conception of "impossible" tasks can change in just a decade.
