20030314, 23:59  #1 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
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. 
20030513, 14:48  #2 
Aug 2002
60_{10} Posts 
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. :) 
20030513, 16:31  #3 
∂^{2}ω=0
Sep 2002
República de California
11,743 Posts 
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. 
20030514, 07:38  #4 
Aug 2002
371_{8} Posts 
I wouldn't be surprised if NFSnet set a record or two by the end of this summer.
Check out http://www.nfsnet.org/. 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. 
20030514, 09:37  #5 
"Sander"
Oct 2002
52.345322,5.52471
4A5_{16} Posts 
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! 
20030514, 15:08  #6 
Aug 2002
3×83 Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
RSA220 factored  ixfd64  Factoring  2  20160524 16:01 
RSA210 factored  ryanp  Factoring  6  20131126 09:33 
Factored vs. Completely factored  aketilander  Factoring  4  20120808 18:09 
F22 factored!  unconnected  Factoring  31  20100626 04:07 
F33 is factored !!  Raman  Factoring  4  20100401 13:57 