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:

Status badges

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)

2498_factor_pari.patch (3.7 KB) - added by AlexGhitza 14 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 14 years ago by dmharvey

  • Cc malb@… added

comment:2 Changed 14 years ago by was

We should put in some checking to make sure this crazy behaviour doesn't happen,

+1 -- definitely.

or at the very least put in big fat warnings in the documentation.

-1 -- let's just not allow this crap.

"Irreducibility is checked over the smallest base field over which pol seems to be defined"

That's the sort of ick that I don't like about PARI.

comment:3 Changed 14 years ago by gfurnish

  • Milestone set to sage-2.11

comment:4 Changed 14 years ago by AlexGhitza

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 cremona

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 AlexGhitza

comment:6 Changed 14 years ago by AlexGhitza

  • 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 cremona

  • 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: Changed 14 years ago by 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

comment:9 in reply to: ↑ 8 Changed 14 years ago by cremona

  • 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 mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 2.11.alpha2

Note: See TracTickets for help on using tickets.