Given an $n$ bit integer quadratic sieve takes $L(\frac12,1+o(1))$ time and number field sieve takes $L(\frac13,1.922)$ time where $L$ notation is given in https://en.wikipedia.org/wiki/L-notation.

What are the theoretical memory requirements for these two sieving techniques, specifically for the relation collection and the sparse matrix inversion stages?

  • 2
    $\begingroup$ I don't have hard data at hand, but IIRC it's "negligible" as in "only a few GB at most". Hard data: the SNFS required 40GB RAM at the peak step for factoring a 1061-bit number. Apparently factoring RSA-768 required 5TB storage. $\endgroup$ – SEJPM Feb 11 '17 at 13:44
  • $\begingroup$ I am not an expert in this, but it seems that the article by Lenstra et al (now very old) in Asiacrypt 2002 addresses some of the memory complexity issues. To my understanding, the algorithm used for the matrix inversion is mainly the Block Wiedemann algorithm due to Coppersmith. The article is called "Analysis of Bernstein's Factorization Algorithm". $\endgroup$ – kodlu Feb 11 '17 at 22:14
  • 1
    $\begingroup$ The space complexity of the number field sieve should be around $L(1/3, 1.922)^{1/2} = L(1/3, 0.961)$, as that is the size of the matrix you need to solve. $\endgroup$ – Samuel Neves Feb 13 '17 at 5:30

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.