Add signal handling to libecm.pyx

[jdemeyer]

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

Also add documentation and examples.

[zimmerma]

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

Paul

[jdemeyer]

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

[zimmerma]

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

[jdemeyer]

Replying to zimmerma:

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]

Replying to zimmerma:

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]

Replying to zimmerma:

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]

Replying to zimmerma:

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)?

[zimmerma]

about 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

[zimmerma]

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]

Okay, I made the changes you suggested.

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

[zimmerma]

the new patch seems ok to me. I will run the doctests with #12757 and this patch, and I will give a "positive review" if all doctests pass. If the patchbot is faster, feel free to tick "positive review" for me.

Paul

[zimmerma]

one doctest fails:

tarte% ./sage -t  devel/sage-12777/sage/misc/sagedoc.py
sage -t  "devel/sage-12777/sage/misc/sagedoc.py"            
**********************************************************************
File "/localdisk/tmp/sage-5.0.beta11/devel/sage-12777/sage/misc/sagedoc.py", line 566:
    sage: 'abvar/homology' in _search_src_or_doc('doc', 'homology', 'variety', interact=False)
Expected:
    True
Got:
    Warning, the following Sage documentation hasn't been built,
    so documentation search results may be incomplete:
    <BLANKLINE>
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/de/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/faq
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/constructions
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/bordeaux_2008
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/a_tour_of_sage
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/reference
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/developer
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/installation
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/numerical_sage
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/website
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/thematic_tutorials
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/fr/a_tour_of_sage
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/fr/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/ru/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/tr/a_tour_of_sage
    <BLANKLINE>
    You can build these with 'sage -docbuild DOCUMENT html',
    where DOCUMENT is one of 'de/tutorial', 'faq', 'constructions', 'bordeaux_2008', 'a_tour_of_sage', 'reference', 'developer', 'installation', 'tutorial', 'numerical_sage', 'website', 'thematic_tutorials', 'fr/a_tour_of_sage', 'fr/tutorial', 'ru/tutorial', 'tr/a_tour_of_sage', 
    or you can use 'sage -docbuild all html' to build all of the missing documentation.
    False
**********************************************************************
1 items had failures:
   1 of   7 in __main__.example_8
***Test Failed*** 1 failures.
For whitespace errors, see the file /users/caramel/zimmerma/.sage//tmp/sagedoc_29685.py
         [20.6 s]

but it fails without the two patches, thus I give a positive review.

Paul

[jdemeyer]

Replying to zimmerma:

one doctest fails:

This is the failure you get when the documentation hasn't been built (or built partially).

[zimmerma]

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

Paul

[jdemeyer]

Replying to zimmerma:

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?

[zimmerma]

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

Paul

[jdemeyer]

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.

[zimmerma]

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

Paul

[jdemeyer]

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

[zimmerma]

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]

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

[jdemeyer]

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]

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

[jdemeyer]

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

[jdemeyer]

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

[zimmerma]

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

Paul