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 [i]sure[/i]?
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. 
Hey, Ernst, is there much work being done on factoring the (if any) remaining RSA challenge numbers? I was at ISU when the RSA129 team was doing its work. That's when I met Bob and got interested in MPQS and NFS, and eventually the Cunningham Project, which lead me here, to Mersenne's. :)
So, I'm sort of curious if that kind of stuff is still alive. I guess it's nice to have going as it sets a good esitmate of the casual lower bound for key sizes used in RSA. Basically, if a bunch of nuts on the Internet can crack a key that size *for fun*, you probably want to use something bigger for anything more important than your instant messenger traffic. :) 
Hi, Dave:
yes, various collaborations like NFSNet continually work on a variety of NFS factoring challenges (Sam Wagstaff of Purdue U. maintains the NFS "mostwanted" lists). Every few years, their horsepower gets to the point where they try the nextlarger RSA challenge number as a test for their latest algorithms and hardware. Peter Montgomery and Paul Leyland would be the guys to talk to about this, I believe. 
I wouldn't be surprised if NFSnet set a record or two by the end of this summer.
Check out [url]http://www.nfsnet.org/[/url]. Its their official site, and they just posted a public release candidate the other day. I see a few issues in it with seeing if the client is running or not on a Windows gui client, while the client window is hidden. If I set the client window to visible, there's no probs, though. 
Currentely they are doing the remaining C212 of 10^2271 but i've understood there's plenty of room for larger composites when more people help with the sieving.
There isn't really a problem when the client window is not vissible, you only have to be careful when you stop the client. When i want to stop the client, i always make the window vissible, press the stop button and wait until the window disappears. BTW, after Ernst wrote the original message, RSA 160 was cracked! 
Yeah, the client always stops within maybe ten or fifteen seconds on my 2000+, after finishing the current line. I can't imagine how long it would take on say a P3.

All times are UTC. The time now is 16:16. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.