I am trying to factor few integers that are each between 115 and 135 digits long. I was wondering if anyone knew of any efficient methods or any programs that I could use to find the two primes $p$ and $q$ for $n=pq$.

I was thinking of using quadratic sieve but I don't know if there is any other way. Plus I don't know how I would write the algorithm on any program. Any input is much appreciated.

  • $\begingroup$ Are you trying to learn how to factor these numbers, or find their factorisation? Try the General Number Field Sieve. Haven't tried any of them but google throws up some options. $\endgroup$ Nov 3, 2013 at 10:33
  • $\begingroup$ A quick calculation in my head tells me that that would generate an $n$ between 770 and 900 bits in size... Is that feasible? $\endgroup$
    – Maarten Bodewes
    Nov 3, 2013 at 11:39
  • $\begingroup$ A quick calculation not in my head gives an $n$ of from 382 to 448 bits (assuming that the "between 115 and 135 digits long" was referring to the size of $n$). Factoring numbers of this size is known to be feasible (if not easy). IIRC, quadratic sieve is about the optimal algorithm for numbers this size (assuming, of course, you know apriori that neither factor is small; if you don't know that, some time with ECM would be warranted). $\endgroup$
    – poncho
    Nov 3, 2013 at 12:24
  • $\begingroup$ Oh, ok, I see where my thought process went wrong, with couple of big ints you don't mean $p$ and $q$ but a few $n$'s, in that case the numbers should be sufficiently small. @poncho yeah, that would be the exact half :) $\endgroup$
    – Maarten Bodewes
    Nov 3, 2013 at 17:44
  • 1
    $\begingroup$ I'm voting to close this question as off-topic because it's about software recommendations for factoring numbers. $\endgroup$
    – otus
    Jun 28, 2015 at 6:54

1 Answer 1


As for the algorithm, you have two choices: The quadratic sieve and the general number field sieve.

If you want to implement the factorization yourself you want to use the quadratic sieve, as a good implementation of the GNFS is really hard.

However, if you're willing to use pre-made tools using GGNFS and msieve (together) is your best option. Msieve provides good polynomial selection (first step) and GGNFS provides the efficient second step, while msieve takes over the last step, you may want to refer to this guide for the exact how-to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.