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: |
Description (last modified by )
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 trac11829_factor_too_large.patch to the Sage library.
Attachments (1)
Change History (18)
comment:1 Changed 10 years ago by
- Cc malb SimonKing added
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
- Status changed from new to needs_review
The attached patch throws an error if a factorisation with a modulus > 2^{29 is requested. }
comment:4 Changed 10 years ago by
Martin, just curious: why did next_prime(2^{29}) raise an error and not previous_prime(2^{31})?
Paul, now checking the doctests still pass...
comment:5 Changed 10 years ago by
- Status changed from needs_review to needs_info
Hi Paul,
a multivariate polynomial ring over GF(next_prime(2^{29})) uses libSingular, i.e., Singular via a Cython interface; while a multivariate polynomial ring over GF(previous_prime(2^{31})) uses the generic polynomial implementation in Sage. We followed the Singular manual for the maximum prime allowed (which is 2147483629 < previous_prime(2^{31})), 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^{31}) 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
Martin, I asked Hans Schonemann last week at the MAGIX conference about this limit, and he told about a 2^{28} limit. Thus I'm not sure the Singular developers really know what the real limit is...
Paul
comment:7 Changed 10 years ago by
Paul, there's a limit of 2^{29} for factoring, gcds etc. everything that has to do with factory. There is another limit of ~ 2^{31} for Singular itself: polynomial arithmetic, GBs etc.
comment:8 Changed 10 years ago by
All doctests pass, thus if the limits are ok, I will give a positive review.
Paul
comment:9 Changed 10 years ago by
- Status changed from needs_info to needs_review
Okay, previous_prime(2^{31}) 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: ↓ 15 Changed 10 years ago by
- 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
- 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
comment:12 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:13 Changed 10 years ago by
- 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
- Description modified (diff)
comment:15 in reply to: ↑ 10 Changed 10 years ago by
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
yes I'm on Ubuntu.
Paul
comment:17 Changed 10 years ago by
- Merged in set to sage-4.7.2.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
Looks like we raise a NotImplementedError also in the polydict implementation: