infinite loop in ECM

[zimmermann6]

[this was reported to me by Emmanuel Thomé]

The following never returns with Sage 8.5:

sage: n=16262093986406371
sage: f=ECM()
sage: f.factor(n,B1=10)

Note that n factors as 1009^2 * 1733 * 3023 * 3049, with a square.

The top-level ECM.factor seems correct, and deals with exact powers.

But for some reason, the B1=10 argument is not passed to find_factors, which uses B1=2000. This is too large, and with all seeds sigma, all factors are found simultaneously, and the loop which calls find_factors loops indefinitely.

It is important to remove all small factors before calling ECM (and not only consider the size of the input).

As a rule of thumb, when using ECM with say B1=2000, all factors below B1 should have been removed.

Component: interfaces

Author: Paul Zimmermann

Branch/Commit: 00a69d4

Reviewer: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/27199

[emmanuelthome]

comment:1

There seem to be places where B1 is actually overridden in the glue code.

The intended semantics of e.g. ECM(1000).factor(n, 2000) are not very clear to me.

[zimmermann6]

comment:2

another issue reported by Emmanuel:

sage: ECM().one_curve(3808350204649, B1=400000, sigma=42)
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-65-febc9e60bbf8> in <module>()
----> 1 ECM().one_curve(Integer(3808350204649), B1=Integer(400000), sigma=Integ\
er(42))

/home/SageMath/local/lib/python2.7/site-packages/sage/interfaces/ecm.pyc in one\
_curve(self, n, factor_digits, B1, algorithm, **kwds)
    476         try:
    477             factors = self._parse_output(n, out)
--> 478             return [factors[0][0], factors[1][0]]
    479         except ValueError:
    480             # output does not end in factorization

IndexError: list index out of range

In this case, all prime factors are hit by the ECM curve, thus the input number is found. The code should be modified so that if factors contains only one element, it should return [ZZ(1), n] like in the ValueError case.

[zimmermann6]

comment:3

another issue (still from Emmanuel):

sage: n=1308301*10^499+200170053
sage: ECM(B1=600).one_curve(n,B1=600,c=1,sigma=10)
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-10-c8d90b5ccb23> in <module>()
----> 1 ECM(B1=Integer(600)).one_curve(n,B1=Integer(600),c=Integer(1),sigma=Integer(10))

/usr/local/SageMath/local/lib/python2.7/site-packages/sage/interfaces/ecm.py in one_curve(self, n, factor_digits, B1, algorithm, **kwds)
    476         out = self._run_ecm(cmd, n)
    477         try:
--> 478             factors = self._parse_output(n, out)
    479             return [factors[0][0], factors[1][0]]
    480         except ValueError:

/usr/local/SageMath/local/lib/python2.7/site-packages/sage/interfaces/ecm.py in _parse_output(self, n, out)
    413                 cofactor = m.group('cofactor')
    414                 primality = m.group('primality')
--> 415                 assert primality in ['Prime', 'Composite']
    416                 result += [(ZZ(cofactor), primality == 'Prime')]
    417                 # assert len(result) == 2

AssertionError: 

The fix is easy: add 'Probable prime' in the list.

[zimmermann6]

comment:4

those issues are addressed in the following patch:

commit 0dfccfb2d1952a70e813cb4211ce1711ef96cfc1 (HEAD -> 27199)
Author: Paul Zimmermann <Paul.Zimmermann@inria.fr>
Date:   Mon Feb 11 15:58:07 2019 +0100

    address issues from #27199

diff --git a/src/sage/interfaces/ecm.py b/src/sage/interfaces/ecm.py
index 8bdeb513df..13fedda258 100644
--- a/src/sage/interfaces/ecm.py
+++ b/src/sage/interfaces/ecm.py
@@ -404,15 +404,15 @@ class ECM(SageObject):
             if m is not None:
                 factor = m.group('factor')
                 primality = m.group('primality')
-                assert primality in ['prime', 'composite']
-                result += [(ZZ(factor), primality == 'prime')]
+                assert primality in ['prime', 'composite', 'probable prime']
+                result += [(ZZ(factor), primality != 'composite')]
                 continue  # cofactor on the next line
             m = self._found_cofactor_re.match(line)
             if m is not None:
                 cofactor = m.group('cofactor')
                 primality = m.group('primality')
-                assert primality in ['Prime', 'Composite']
-                result += [(ZZ(cofactor), primality == 'Prime')]
+                assert primality in ['Prime', 'Composite', 'Probable prime']
+                result += [(ZZ(cofactor), primality != 'Composite')]
                 # assert len(result) == 2
                 return result
         raise ValueError('failed to parse ECM output')
@@ -476,8 +476,9 @@ class ECM(SageObject):
         try:
             factors = self._parse_output(n, out)
             return [factors[0][0], factors[1][0]]
-        except ValueError:
-            # output does not end in factorization
+        except (ValueError, IndexError):
+            # output does not end in factorization (ValueError)
+            # or factors has only one element above (IndexError)
             return [ZZ(1), n]

     def _find_factor(self, n, factor_digits, B1, **kwds):
@@ -656,7 +657,7 @@ class ECM(SageObject):
             # Step 3: Call find_factor until a factorization is found
             n_factorization = [n]
             while len(n_factorization) == 1:
-                n_factorization = self.find_factor(n)
+                n_factorization = self.find_factor(n,B1=B1)
             factors.extend(n_factorization)

         return sorted(probable_prime_factors)

[zimmermann6]

Author: Paul Zimmermann

[zimmermann6]

comment:6

note: another interface to GMP-ECM exists in sage.libs.libecm:

sage: import sage.libs.libecm
sage: from sage.libs.libecm import ecmfactor
sage: N = 2^167 - 1
sage: ecmfactor(N, 100)
(False, None)
sage: ecmfactor(N, 100)
(True, 2349023, 17020317862377366332)

Maybe one could remove the one at the top-level (which uses a text interface I believe) and keep only the one in sage.libs.libecm (which uses a Cython interface). Comments welcome.

[zimmermann6]

comment:7

note that the old text interface is advertised from the factor command:

sage: factor?
...
   The qsieve and ecm commands give access to highly optimized
   implementations of algorithms for doing certain integer
   factorization problems. These implementations are not used by the
   generic factor command, which currently just calls PARI (note that
   PARI also implements sieve and ecm algorithms, but they aren't as
   optimized). Thus you might consider using them instead for certain
   numbers.

If one removes the old text interface, one should point to sage.libs.libecm instead here.

[embray]

comment:8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

[embray]

comment:9

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[embray]

comment:10

Ticket retargeted after milestone closed

[videlec]

comment:11

I made a git branch from your patch. I will also incorporate proper doctests.

---

New commits:

d31bd41

address issues from #27199

[videlec]

Commit: d31bd41

[videlec]

Branch: public/27199

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d31bd41 to 00a69d4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

00a69d4

add doctests for #27199

[videlec]

comment:13

For unifying the interfaces, it deserves a distinct ticket and I opened #29207.

[videlec]

Reviewer: Vincent Delecroix

[zimmermann6]

comment:15

thank you Vincent!

[vbraun]

Changed branch from public/27199 to 00a69d4