A team at the German Federal Agency for Information Technology Security has factored a 193-digit number. (Note that this is not a record; in May a 200-digit number was factored. But there’s a cash prize associated with this one.)
The links do a good job explaining the news and giving context.
greg • November 9, 2005 1:20 PM
@Jarrod
No, at this point it does not scale like that. Its still a hard problem. In other words, Blue Gene would struggle to factor a number much larger in any reasonable time frame.
So doubling the time is takes to sign with RSA, will make factoring much harder than double. The trick is that you want signatures to be safe for 20 years. Which means on todays computers you do have to wait a miniute or two for a signature.
denis bider • November 9, 2005 6:18 PM
The weak link in signing is currently the hash. You can sign with a 4096-bit RSA key, but if you’re using something like SHA-1 for the hashing process, you can’t count on two decades of security. I’m not sure we even have a hash function right now we could count on to provide 20 years of security.
greg • November 9, 2005 6:30 PM
@ denis bider
Yes you are totaly correct. There are hash schemes based on fatoring with proofs, i belive. But they really are slow. Real slow, and so no signing schemes uses them as the hash.
I was using this as a example for hard problem of Factoring.
Jim • November 9, 2005 11:14 PM
There is now a fast hash based upon factoring, known as VSH. Do a web search.
Zaphod • November 10, 2005 11:28 PM
@greg
Wasn’t Jarrod asking if something like Blue Gene could factor the same number in a shorter time?….not a larger number in an equivalent time.
Z
Roger • November 11, 2005 1:05 AM
Regarding Blue Gene/L etc:
No you can’t simply scale it. The problem is that the factoring is divided into two phases, only the first of which is primarily compute-bound (and consequently, goes about twice as fast if you have twice as many machines, or the same number with twice the clock rate, etc). The second part of the problem is memory and communication bound. This makes it difficult to make simple comparisons — for one thing, so far as I know the memory capacity of the Opteron cluster hasn’t yet been published, and it also depends on how much is cache vs. DRAM, etc.
Having said that, we can probably guesstimate that the first phase, which took 3 months on the 80 x 2.2GHz Opterons, would have taken the order of an hour and a half on the 280 Tfps Blue Gene/L.
Subscribe to comments on this entry
Sidebar photo of Bruce Schneier by Joe MacInnis.
Jarrod • November 9, 2005 11:57 AM
How well do these kinds of results scale? If an 80-Opteron cluster can do this kind of thing in five months, can something the power of Blue Gene/L do this kind of factoring in a few hours or even minutes? If so, how does this play into the abilities of large entities to break more common encryption routines?