4
$\begingroup$

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite them over-sieving, meaning they spent longer on the sieving so that the matrix step would be easier.

When the factorization of RSA-220 was announced in May 2016: the sieving was done from May to September 2014 (5 months), but the authors say code developments were done between October 2014 and January 2016 to make the matrix step easier. After that they only spent 48 hours on the $\texttt{lingen}$ part of the matrix step, and a few days in the program $\texttt{mksol}$.

These dates, timings, and program names come from here. But the specific code developments that were made between 2014 to 2016 remain a mystery to me. Has there been a bottleneck surpassed in the matrix step, or is it still considered the most cumbersome part of the factorization process?

A related question, regarding the precise cost of the matrix step, which doesn't seem to be given anywhere, can be found here.

$\endgroup$
  • $\begingroup$ It was my first question ever, so if it's better suited for a different stack exchange such as Mathematics or Computer Science, please rather than voting down I would prefer if you helped me get the question moved to the right place. $\endgroup$ – user1271772 May 23 '18 at 1:38
  • 3
    $\begingroup$ Algorithmically, nothing changed. But the implementation of the lingen program was not good enough to handle problems of that size at the time. It needed to be parallelized. You can see this commit for details. $\endgroup$ – Samuel Neves May 23 '18 at 5:18
  • $\begingroup$ Interesting, and funny commit! How did you know about it? You don't seem to be a co-author on the RSA-220 paper. $\endgroup$ – user1271772 May 23 '18 at 6:13
  • $\begingroup$ @Samuel Neves: was the former lingen (or something with the same apparently blatant lack of performance optimisation) used and a bottleneck for RSA-768? If yes, what about slightly expanding your comment into an answer? $\endgroup$ – fgrieu May 23 '18 at 11:34
  • $\begingroup$ RSA-768 was factored using an entirely distinct toolchain; CADO-NFS was still very much in its infancy at the time. $\endgroup$ – Samuel Neves May 23 '18 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.