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.
