Add signal handling to libecm.pyx

[jdemeyer]

Add sig_on()/sig_off() in libecm.pyx.

Also add documentation and examples.

Depends on #12757
Depends on #12873

CC: @zimmermann6

Component: factorization

Author: Jeroen Demeyer

Reviewer: Paul Zimmermann

Merged: sage-5.1.beta0

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

[jdemeyer]

Author: Jeroen Demeyer

[jdemeyer]

Dependencies: #12757

[zimmermann6]

comment:5

Jeroen, you changed to "needs work" but did not mention what are the work issues.

Paul

[jdemeyer]

comment:6

I rebased it on top of #12757 (which has positive review).

[zimmermann6]

comment:7

when recompiling Sage with this patch, I got a warning that variables f and n were referenced before assignment. Maybe it happened before this patch.

Some comments on the patch itself:

"The Elliptic Curve Method for Integer Factorization (GMP-ECM)": please replace GMP-ECM by ECM, since GMP-ECM is only one implementation of the ECM algorithm.

"Try to find a factor of a number": it would be better to say "integer", or even "positive integer".

"number to be factored": replace by "integer to be factored"

About the example with the factor from 2¹⁶⁷-1: the B1 bound 1e5 is not enough to ensure
the factor 2349023 will always be found. By Hasse theorem, the group order can be as large
as 2352089, and since GMP-ECM only guarantees a torsion of 12, B1=196003 is needed to ensure
the factor 2349023 is always found, whatever the curve (unfortunately, the current interface
does not allow to specify the chosen curve).

"The following number is a Mersenne prime, so we will not find any factors": this is not
entirely true, it might be that we find the input number itself if we are lucky.

For the example with the two prime factors of 2¹⁷⁹-1, in fact B1=1e4 ensures we will find always both of them, as any value B1 >= 113. I suggest using B1=10 instead.

ecmfactor(N/11, 100, verbose=True): please replace N/11 by N//11.

Paul

[zimmermann6]

Work Issues: cf issues in comment 7

[zimmermann6]

Reviewer: Paul Zimmermann

[jdemeyer]

comment:9

Replying to @zimmermann6:

when recompiling Sage with this patch, I got a warning that variables f and n were referenced before assignment. Maybe it happened before this patch.

It's a spurious warning, the code is obviously fine.

[jdemeyer]

comment:10

Replying to @zimmermann6:

ecmfactor(N/11, 100, verbose=True): please replace N/11 by N//11.

Actually, I did this on purpose as a mild test that the function works with things that aren't Integers but can be converted to Integers.

[jdemeyer]

comment:11

Replying to @zimmermann6:

For the example with the two prime factors of 2¹⁷⁹-1, in fact B1=1e4 ensures we will find always both of them, as any value B1 >= 113.

Depends what you mean. If the ecm_factor() algorithm would be run to the end, then yes. But it's possible the algorithm stops after step 1 when only one factor is found. So you don't always get 359 * 1433 as factor.

[jdemeyer]

comment:12

Replying to @zimmermann6:

About the example with the factor from 2¹⁶⁷-1: the B1 bound 1e5 is not enough to ensure
the factor 2349023 will always be found. By Hasse theorem, the group order can be as large
as 2352089

Isn't it sufficient that 2352089 is below the B2 bound (which is the case)?

[zimmermann6]

comment:13

about comment [comment:11]: I only considered Step 1 in my analysis,
since B1 controls Step 1 only. Thus B1=113 is enough to find both 359
and 1433 in Step 1.

But in some rare cases it can happen that some factor is found during the
initial computation before Step 1 is started. In such a case indeed only
359 or 1433 can be returned. Experimentally this seems to happen in only 1%
of the cases.

Paul

[zimmermann6]

comment:14

Replying to @jdemeyer:

Isn't it sufficient that 2352089 is below the B2 bound (which is the case)?

you are right, but it might be that a future version of GMP-ECM changes the default B2
value for B1=1e5.

Paul

[jdemeyer]

comment:15

Okay, I made the changes you suggested.

I also added a check that the given number is positive.

[zimmermann6]

comment:19

is there any reason the documentation is not built (or only partially) with sage-5.0.beta11?

Paul

[jdemeyer]

comment:20

Replying to @zimmermann6:

is there any reason the documentation is not built (or only partially) with sage-5.0.beta11?

No, I'm guessing something went wrong with your setup. Did you apply any other patches which might have broken the documentation? And what happens when you do make doc from $SAGE_ROOT?

[zimmermann6]

comment:21

after make doc the doctest sagedoc.py passes. I have no idea why it was not done
by make.

Paul

[jdemeyer]

Merged: sage-5.0.beta14

[jdemeyer]

comment:23

On hawk (OpenSolaris 06.2009-32), I regularly get:

sage -t  --long -force_lib devel/sage/sage/libs/libecm.pyx
**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/devel/sage-main/sage/libs/libecm.pyx", line 132:
    sage: ecmfactor(1, 100)
Exception raised:
    Traceback (most recent call last):
      File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[19]>", line 1, in <module>
        ecmfactor(Integer(1), Integer(100))###line 132:
    sage: ecmfactor(1, 100)
      File "libecm.pyx", line 152, in sage.libs.libecm.ecmfactor (sage/libs/libecm.c:1899)
        sig_on()
    RuntimeError: Floating point exception
**********************************************************************

I have not yet investigated what causes this.

[jdemeyer]

Changed merged from sage-5.0.beta14 to none

[zimmermann6]

comment:24

Jeroen, did you get this error before the patch too?

Paul

[jdemeyer]

comment:25

The problem is really with the interrupt test. Disabling that test makes everything pass.

[zimmermann6]

comment:26

do you mean the problem might be related to sage.tests.interrupt.interrupt_after_delay?
If you disable the test, and try to interrupt ecmfactor by hand, does it work ok?

Paul

[jdemeyer]

comment:27

It looks like a bug in Cython. ecmfactor() gets called with B1 = -NaN. This is certainly not the fault of ECM.

[jdemeyer]

comment:28

After the interrupt test, the following doctest:

        sage: n = 100
        sage: float(n)
        100.0

fails with:

**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/devel/sage/sage/libs/libecm.pyx", line 73:
    sage: float(n)
Expected:
    100.0
Got:
    nan
**********************************************************************

[jdemeyer]

comment:29

My current guess is that OpenSolaris's longjmp() doesn't completely restore the x87 FPU state.

[jdemeyer]

comment:30

Confirmed, it's a bug in longjmp(). The FPU tag word isn't restored properly.

[jdemeyer]

comment:31

I opened #12873 for the Solaris issue. Restoring positive_review here, since the bug is unrelated to this ticket.

[jdemeyer]

Changed dependencies from #12757 to #12757, #12873

[zimmermann6]

comment:34

Jeroen, why reschedule to sage-pending and not sage-5.1?

Paul

[jdemeyer]

Merged: sage-5.1.beta0