This highly depends on the size of your integers, and what form you expect them to have. For factors of a few tens of bits (lets say up to something between 50 and 80 bits), ECM should be the best. For smaller factors, naive stuff . For larger factors QS or NFS should be better. We at least have Bill Hart's implem of QS in sage. This is not very constructive but I don't have time to make a longer answer right now.
On Thursday, January 30, 2014 7:35:46 PM UTC+1, Ondřej Čertík wrote: > > Hi, > > What is the state of the art library for factoring integers? > I was under the impression, that it is the GCM-ECM library > (http://ecm.gforge.inria.fr/). > > I've been trying to use ECM and I noticed the following behavior: > > sage: from sage.libs.libecm import ecmfactor > sage: N = 121 > sage: factor(N) > 11^2 > sage: ecmfactor(N, 1) > (True, 121) > sage: ecmfactor(N, 100) > (True, 121) > sage: ecmfactor(N, 200) > (True, 121) > sage: ecmfactor(N, 0) > (True, 121) > sage: ecmfactor(N, 0.) > (True, 11) > > > In other words, it never finds the factor 11, unless you give it B1=0.0 > > Compared to N=122, where it always finds it: > > sage: N = 122 > sage: factor(N) > 2 * 61 > sage: ecmfactor(N, 1) > (True, 2) > sage: ecmfactor(N, 100) > (True, 2) > sage: ecmfactor(N, 200) > (True, 2) > > > I have a few questions: > > * Does this mean that ECM only works sometimes? > * Is there a parameter B1, that always works? > > In the README file of the ecm-6.4.4 package, I found: > > digits D optimal B1 default B2 expected curves > N(B1,B2,D) > -power 1 default > poly > 20 11e3 1.9e6 74 74 > [x^1] > 25 5e4 1.3e7 221 214 > [x^2] > 30 25e4 1.3e8 453 430 > [D(3)] > 35 1e6 1.0e9 984 904 > [D(6)] > 40 3e6 5.7e9 2541 2350 > [D(6)] > 45 11e6 3.5e10 4949 4480 > [D(12)] > 50 43e6 2.4e11 8266 7553 > [D(12)] > 55 11e7 7.8e11 20158 17769 > [D(30)] > 60 26e7 3.2e12 47173 42017 > [D(30)] > 65 85e7 1.6e13 77666 69408 > [D(30)] > > Table 1: optimal B1 and expected number of curves to find a > factor of D digits with GMP-ECM. > > The only documentation about ECM that I found in Sage is this: > > http://www.sagemath.org/doc/bordeaux_2008/integer_factorization.html > http://www.sagemath.org/doc/reference/libs/sage/libs/libecm.html > > But it doesn't answer my questions above. > If the answer is that ECM only works sometimes, but it's not a > reliable way to factor integers, what is the fastest library that > always works? > > Many thanks, > Ondrej > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/groups/opt_out.
