brainwagon

A few days ago, I mentioned that I was pondering the stages of Simon Singh’s Cipher Challenge that I didn’t complete “back in the day”. I was examining the DES portion, which still seems like it would take a while to solve, so I decided to skip ahead and figure out what the final stage was like. It seems to require the factoring of a 155 digit number. A bit of research reveals that such a number is still a pretty darned hard thing to factor. But while toying around, I downloaded YAFU, and tried to factor some numbers on my AMD machine. It took about an hour and a half to factor this 91 digit product of two primes:

14181042111046838458974412614836094249162520811
22341447307961894892019996002707152857987347 =
411268404095925771725738109950909913561283687 * 3448123407928803465744207062833069247853720181

This corresponds to about a 300 bit RSA key.

It can factor 60 digit products in about 10 seconds.

Breaking Stage 10 of the Challenge requires factoring this 155 digit
monstrosity:

10742 78829 12665 65907 17841 12799 42116 61266 39217 94753 29458
88778 17210 35546 41509 80121 87903 38329 26235 28109 07506 72083
50494 19964 33143 42555 83344 01855 80898 94268 92463

I should learn how this stuff works.