Opened 10 years ago

Closed 10 years ago

#11829 closed defect (fixed)

multivariate factorization over finite fields

Reported by: zimmerma Owned by: tbd
Priority: major Milestone: sage-4.7.2
Component: factorization Keywords:
Cc: malb, SimonKing Merged in: sage-4.7.2.alpha3
Authors: Martin Albrecht Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by leif)

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

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 trac11829_factor_too_large.patch to the Sage library.

Attachments (1)

trac11829_factor_too_large.patch (3.1 KB) - added by malb 10 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 10 years ago by zimmerma

  • Cc malb SimonKing added

comment:2 Changed 10 years ago by malb

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

comment:3 Changed 10 years ago by malb

  • Authors set to Martin Albrecht
  • Status changed from new to needs_review

The attached patch throws an error if a factorisation with a modulus > 229 is requested.

comment:4 Changed 10 years ago by zimmerma

Martin, just curious: why did next_prime(229) raise an error and not previous_prime(231)?

Paul, now checking the doctests still pass...

comment:5 Changed 10 years ago by malb

  • Status changed from needs_review to needs_info

Hi Paul,

a multivariate polynomial ring over GF(next_prime(229)) uses libSingular, i.e., Singular via a Cython interface; while a multivariate polynomial ring over GF(previous_prime(231)) uses the generic polynomial implementation in Sage. We followed the Singular manual for the maximum prime allowed (which is 2147483629 < previous_prime(231)), 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(231) when they chose a limit.

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

comment:6 Changed 10 years ago by zimmerma

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

Paul

comment:7 Changed 10 years ago by malb

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

comment:8 Changed 10 years ago by zimmerma

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

Paul

comment:9 Changed 10 years ago by malb

  • Status changed from needs_info to needs_review

Okay, previous_prime(231) 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.

comment:10 follow-up: Changed 10 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to positive_review

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

comment:11 Changed 10 years ago by malb

  • Status changed from positive_review to needs_work

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

Changed 10 years ago by malb

comment:12 Changed 10 years ago by malb

  • Status changed from needs_work to needs_review

comment:13 Changed 10 years ago by zimmerma

  • Status changed from needs_review to positive_review

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

Paul

comment:14 Changed 10 years ago by leif

  • Description modified (diff)

comment:15 in reply to: ↑ 10 Changed 10 years ago by leif

Replying to zimmerma:

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

comment:16 Changed 10 years ago by zimmerma

yes I'm on Ubuntu.

Paul

comment:17 Changed 10 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.