Muli Ben-Yehuda's journal

Yesterday Eran Tromer gave a colloqium talk at IBM HRL on Hardware Based Implementations of Factoring Algorithms. Eran’s talk dealt with the improvements leading up to the TWIRL device, which cleverly exploits the inherent parallelism of the Number Field Sieve algorithm via hardware design. The bottom line is that factoring 1024 bit RSA keys in reasonable time, using the hypothetical TWIRL device, will only cost approximately 10,000,000$. Previous estimates were in the trillions of dollars. For perspective, 1024 bit is the recommended RSA key size, and $10e6 is peanuts for a certain Fort Meade agency…. More details are available in the papers on Eran’s Weizmann home page.

After the talk Eran, Oleg, myself and another coworker whose name I don’t recall had lunch at the IBM cafeteria. Topics of discussion during lunch were suitably geeky for the company involved, and much fun was had. Earlier, Eran explained that parameters to one of algorithm’s steps are chosen so that a memory write will always occur to the memory cell preceding a cell we just read (which means a cache hit, which is a good thing). During lunch, I told Eran that it reminded me of the techniques used by Mel, a Real Programmer, and Eran said that he concurs, and must have internalized the story to use the same trick. Inspiration comes from unlikely places…