Let exponentiation of polynomial using FLINT nmod type be interrupted

[jpflori]

sage: p = next_prime(2**30)
sage: k = GF(p)
sage: x = polygen(k)
sage: x**p
CTRL+C....

CC: @vbraun @jdemeyer

Component: finite rings

Author: Jean-Pierre Flori

Branch/Commit: 0706674

Reviewer: Jeroen Demeyer

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

[jpflori]

Commit: ef28e27

[jpflori]

Author: Jean-Pierre Flori

[jpflori]

Branch: u/jpflori/ticket/17470

[jpflori]

New commits:

0aed331	Make modular exponentiation of polynomial using FLINT interruptable.
ef28e27	Better fix for exponentiation of polys using FLINT nmod and test.

[jdemeyer]

comment:2

cdefs.pxi should be interrupt.pxi

[jdemeyer]

comment:3

I know it's not the topic of this ticket, but why is this code not implemented as direct calls to either nmod_poly_pow() or nmod_poly_powmod_mpz_binexp()?

[jdemeyer]

comment:4

Also, celement_pow doesn't seem to be documented anywhere...

I do give positive_review to the addition of sig_on() and sig_off() and the doctest changes.

[jdemeyer]

comment:5

Actually,

sage: alarm(1)
sage: x^n

should be

sage: alarm(1); x^n

[jdemeyer]

comment:6

I created #17476 as possible "meta-ticket".

[jpflori]

comment:7

Replying to @jdemeyer:

I know it's not the topic of this ticket, but why is this code not implemented as direct calls to either nmod_poly_pow() or nmod_poly_powmod_mpz_binexp()?

Maybe because the file was written 6 years ago on top of FLINT 1.x :)

[jpflori]

comment:8

As far as old stuff which needs update is concerned, we should also rewrite the NTL wrapping code now that Cython understands C++.

[sagetrac-git]

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

12539c9

Cleanup exponentiation for polynomial over finite fields using FLINT.

[sagetrac-git]

Changed commit from ef28e27 to 12539c9

[jdemeyer]

comment:11

I get

sage -t --long src/sage/libs/flint/nmod_poly_linkage.pxi
**********************************************************************
File "src/sage/libs/flint/nmod_poly_linkage.pxi", line 498, in sage.libs.flint.nmod_poly_linkage.celement_pow
Failed example:
    alarm(1); x^n
Expected:
    Traceback (most recent call last):
    ...
    AlarmInterrupt
Got:
    Exception (FLINT memory_manager). Unable to allocate memory.
    Traceback (most recent call last):
      File "/usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 488, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/local/src/sage-config/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 851, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.libs.flint.nmod_poly_linkage.celement_pow[20]>", line 1, in <module>
        alarm(Integer(1)); x**n
      File "sage/rings/polynomial/polynomial_template.pxi", line 625, in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_template.__pow__ (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:10790)
      File "sage/libs/flint/nmod_poly_linkage.pxi", line 508, in sage.rings.polynomial.polynomial_zmod_flint.celement_pow (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:4815)
      File "sage/ext/c_lib.pyx", line 85, in sage.ext.c_lib.sig_raise_exception (build/cythonized/sage/ext/c_lib.c:971)
    RuntimeError: Aborted
**********************************************************************

[jpflori]

comment:12

Indeed...
Actually I think it will be quite hard to find a test that won't spuriously cause memory errors.

Exponentiation without modular reduction will be either too fast or eat up all the memory.
And modular exponentiation is just fast as well and we can only use longs as exponents right now.

[jdemeyer]

comment:13

Proposal: choose n such that the test passes with 2GB of virtual memory (use ulimit -v 2000000 to test this). If needed, make the alarm time shorter.

[sagetrac-git]

Changed commit from 12539c9 to c781c24

[sagetrac-git]

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

c781c24

Modify FLINT exponentiation test to pass with <= 2Gb of virtual mem.

[jdemeyer]

Changed branch from u/jpflori/ticket/17470 to u/jdemeyer/ticket/17470

[jdemeyer]

Changed commit from c781c24 to 0706674

[jdemeyer]

comment:17

I modified the test slightly. Other than that, the patch looks good.

---

New commits:

0706674

Modify doctest

[jpflori]

Reviewer: Jeroen Demeyer

[jpflori]

comment:18

I assume this means positive review...

[vbraun]

Changed branch from u/jdemeyer/ticket/17470 to 0706674