Opened 14 years ago
Closed 14 years ago
#2498 closed defect (fixed)
[with patch, with positive review] PARI's is_irreducible being used inappropriately
Reported by: | dmharvey | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | sage-2.11 |
Component: | basic arithmetic | Keywords: | |
Cc: | malb@… | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
PARI's polynomial irreducibility and factoring routines are being used incorrectly for certain base rings. Here is an example:
sage: R.<x> = PolynomialRing(Integers(35)) sage: f = (x^2+2*x+2)*(x^2+3*x+9) sage: f x^4 + 5*x^3 + 17*x^2 + 24*x + 18 sage: factor(f) x^4 + 5*x^3 + 17*x^2 + 24*x + 18 sage: f.is_irreducible() True
The PARI documentation for polisirreducible
says: "Irreducibility is checked over the smallest base field over which pol seems to be defined", whatever that means.
We should put in some checking to make sure this crazy behaviour doesn't happen, or at the very least put in big fat warnings in the documentation.
Attachments (1)
Change History (11)
comment:1 Changed 14 years ago by
- Cc malb@… added
comment:2 Changed 14 years ago by
comment:3 Changed 14 years ago by
- Milestone set to sage-2.11
comment:4 Changed 14 years ago by
Just checking that I understand what we want to see here: suppose we are dealing with a polynomial over Z/nZ with composite n. Then we want that both factor() and is_irreducible() throw a NotImplementedError? instead of calling pari and getting an incorrect answer.
I wanted to make sure before I went and changed this.
comment:5 Changed 14 years ago by
When n is composite in the sense that it has more than one prime factor, I agree with throwing NotImplementedErrror. When n is a prime power we could try to be more clever (if f mod p has a factorization into coprime factors then this would lift uniquely to a factorization over Z/nZ, for example) but for now I suggest again making this NotImplemented.
Changed 14 years ago by
comment:6 Changed 14 years ago by
- Summary changed from PARI's is_irreducible being used inappropriately to [with patch, needs review] PARI's is_irreducible being used inappropriately
Yes, it should be possible to do something smart here. For now, I'm just making factor() and is_irreducible() throw NotImplementedError? so we don't get wrong answers.
See the attached patch.
comment:7 Changed 14 years ago by
- Summary changed from [with patch, needs review] PARI's is_irreducible being used inappropriately to [with patch, with noncommittal review] PARI's is_irreducible being used inappropriately
Instead of explicitly mentioning Z/nZ (for composite n) as not implemented, would it not be more useful to list which rings this _is_ implemented for? (Fields, Z, anything else?)
comment:8 follow-up: ↓ 9 Changed 14 years ago by
Instead of explicitly mentioning Z/nZ (for composite n) as not implemented, would it not be more useful to list which rings this _is_ implemented for? (Fields, Z, anything else?)
It might be more useful now, but it's bound to become out of date, in which case such a list would be wrong, and could turn out to be way *less* useful than nothing.
William
comment:9 in reply to: ↑ 8 Changed 14 years ago by
- Summary changed from [with patch, with noncommittal review] PARI's is_irreducible being used inappropriately to [with patch, with positive review] PARI's is_irreducible being used inappropriately
Replying to was:
Instead of explicitly mentioning Z/nZ (for composite n) as not implemented, would it not be more useful to list which rings this _is_ implemented for? (Fields, Z, anything else?)
It might be more useful now, but it's bound to become out of date, in which case such a list would be wrong, and could turn out to be way *less* useful than nothing.
William
OK then -- the patch gets a thumbs up from me!
comment:10 Changed 14 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in Sage 2.11.alpha2
+1 -- definitely.
-1 -- let's just not allow this crap.
That's the sort of ick that I don't like about PARI.