multivariate factorization over finite fields

[zimmermann6]

As far as I know, Sage calls Singular for multivariate factorization over finite fields. Currently Singular is limited to primes less than
2^29:

sage: R.<x,y> = GF(previous_prime(2^29))[]
sage: factor(x+y+1,proof=False)
x + y + 1
sage: R.<x,y> = GF(next_prime(2^29))[]
sage: factor(x+y+1,proof=False)
...
NotImplementedError: Factorization of multivariate polynomials over prime fields with characteristic > 2^29 is not implemented.

However for larger primes we get:

sage: R.<x,y> = GF(previous_prime(2^31))[]
sage: factor(x+y+1,proof=False)

and this seems to hang (when I hit Ctrl-C, it says
Interrupting Singular)

---

Apply attachment: trac11829_factor_too_large.patch to the Sage library.

CC: @malb @simon-king-jena

Component: factorization

Author: Martin Albrecht

Reviewer: Paul Zimmermann

Merged: sage-4.7.2.alpha3

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

[malb]

comment:2

Looks like we raise a NotImplementedError also in the polydict implementation:

sage -singular                                                                [ 3:32PM]
                     SINGULAR                             /  Development
 A Computer Algebra System for Polynomial Computations   /   version 3-1-1
                                                       0<
     by: G.-M. Greuel, G. Pfister, H. Schoenemann        \   Feb 2010
FB Mathematik der Universitaet, D-67653 Kaiserslautern    \
> ring r = 2147483647,(x,y),dp;
> poly p = x+y+1;
> factorize(p);
   ? characteristic 2147483647 is too large(max is 2^29)
Segmentation fault

[malb]

Author: Martin Albrecht

[malb]

comment:3

The attached patch throws an error if a factorisation with a modulus > 2^29 is requested.

[zimmermann6]

comment:4

Martin, just curious: why did next_prime(2²⁹) raise an error and not previous_prime(2³¹)?

Paul, now checking the doctests still pass...

[malb]

comment:5

Hi Paul,

a multivariate polynomial ring over GF(next_prime(2²⁹)) uses libSingular, i.e., Singular via a Cython interface; while a multivariate polynomial ring over GF(previous_prime(2³¹)) uses the generic polynomial implementation in Sage. We followed the Singular manual for the maximum prime allowed (which is 2147483629 < previous_prime(2³¹)), while we apparently don't follow it when converting generic polynomials to Singular via the pexpect interface.

I think this is actually a bug and the Singular developers meant previous_prime(2³¹) when they chose a limit.

I asked: http://groups.google.com/group/libsingular-devel/browse_thread/thread/885b21e6f8039cc

[zimmermann6]

comment:6

Martin, I asked Hans Schonemann last week at the MAGIX conference about this limit, and he
told about a 2²⁸ limit. Thus I'm not sure the Singular developers really know what the real
limit is...

Paul

[malb]

comment:7

Paul, there's a limit of 2²⁹ for factoring, gcds etc. everything that has to do with factory. There is another limit of ~ 2³¹ for Singular itself: polynomial arithmetic, GBs etc.

[zimmermann6]

comment:8

All doctests pass, thus if the limits are ok, I will give a positive review.

Paul

[malb]

comment:9

Okay, previous_prime(2³¹) is what is correct (confirmed with Hans). Hence, I changed the bound in ring.pyx. This means, that the added check in multi_polynomial_element.py won't be used (by default), but it doesn't harm to have it there regardless.

[zimmermann6]

Reviewer: Paul Zimmermann

[zimmermann6]

comment:10

All doctests pass except the following timeout with sage 4.7.1 (but this timeout also happens
before the patch):

The following tests failed:

        sage -t  devel/sage-11829/sage/sandpiles/sandpile.py # Time out

Thus a positive review for me.

Paul

[malb]

comment:11

argh, I screwed up and didn't upload the most recent patch. Sorry! I'll upload the new patch in a second.

[malb]

comment:12

Attachment: trac11829_factor_too_large.patch.gz

[zimmermann6]

comment:13

All doctests still pass with the new version (with the same timeout).

Paul

[nexttime]

comment:15

Replying to @zimmermann6:

All doctests pass except the following timeout with sage 4.7.1 (but this timeout also happens
before the patch):

The following tests failed:

        sage -t  devel/sage-11829/sage/sandpiles/sandpile.py # Time out

Guess you're on Ubuntu (10.04.3 for example); this is due to a known issue with its kernel and the PExpect interface. (You'll notice that the doctest idles most of the time.)

[zimmermann6]

comment:16

yes I'm on Ubuntu.

Paul

[nexttime]

Merged: sage-4.7.2.alpha3