Best library for integer factorization (ecmfactor and the B1 parameter)

[Ondřej Čertík]

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

[Jean-Pierre Flori]

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.

[Thilina Rathnayake]

Hi,

I got following strange results working with ecmfactor in sage.

https://cloud.sagemath.com/projects/88eea618-4a6a-4eb1-9897-75b4b44a1f8c/files/2014-01-30-235001.term

I encountered the same behaviour with `ecm`, command line tool of gmp-ecm.

[Jean-Pierre Flori]

On Thursday, January 30, 2014 7:54:45 PM UTC+1, Jean-Pierre Flori wrote:

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)

And I guess your problem here is also that 121 is a perfect power of a prime number, whence the discrepancy with 120.
FYI its really easy and cheap to detect such perfect powers without using factorization of any kind.

[Volker Braun]

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

[Thilina Rathnayake]

Since the link I posted before can not be accessed here is a copy and paste
version of the sage terminal session.

sage: from sage.libs.libecm import ecmfactor

sage: ecmfactor(121, 1.0)

(True, 121)

sage: ecmfactor(121, 1)

(True, 121)

sage: ecmfactor(121, 1.0)

(True, 11)

sage: ecmfactor(121, 1.0)

(True, 121)

sage: ecmfactor(121, 0)

(True, 121)

sage: ecmfactor(121, 0.0)

(True, 11)

sage: ecmfactor(121, 0.0)

(True, 11)

sage: ecmfactor(121, 0.0)

(True, 121)

On Friday, January 31, 2014 12:05:46 AM UTC+5:30, Ondřej Čertík wrote:

[Ondřej Čertík]

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

> --
> 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+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.

[Marco Streng]

2014-01-30 Ondřej Čertík <ondrej...@gmail.com>

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.

Step 1+1/3: Determine if N is a perfect power (N.is_perfect_power()).

Step 1+2/3: Do trial division to remove small prime factors, and maybe some other factorization algorithms that perform well on small ranges. This all depends on the kind of number you are trying to factor.

 

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.

"eventually" can take a long time. So after a while, you may want to switch to the quadratic sieve or the number field sieve (say cado-nfs) if you still don't get your factors.