Hi Volker, I see. So is my understanding correct, that the proper usage of the ECM is as follows:
1. Determine if N is prime, using pari(N).ispseudoprime(). The standard conjecture is that there exist infinitely many counterexamples, even though no single one is known. 2. If N is not prime, lookup the proper B1 using the table I posted. 3. Keep calling ecmfactor() until it gives you a factor. It must give you a factor eventually. ? Ondrej On Thu, Jan 30, 2014 at 12:04 PM, Volker Braun <vbraun.n...@gmail.com> wrote: > Just calling ecmfactor from the innards of the ecm library is just trying > one elliptic curve (see the docs). This is not going to be really useful by > itself. > > sage: ecm.factor(121) > [11, 11] > > Relevant discussion at http://trac.sagemath.org/ticket/15443 > > > > > On Thursday, January 30, 2014 6:35:46 PM UTC, 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. -- 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.
