Opened 8 years ago

Last modified 6 years ago

#11239 closed defect

Incorrect coercion of polynomials over finite fields — at Version 11

Reported by: johanbosman Owned by: robertwb
Priority: major Milestone: sage-6.2
Component: coercion Keywords: finite fields, polynomials, coercion, sd53
Cc: jpflori Merged in:
Authors: pbruin Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8335 Stopgaps:

Description (last modified by pbruin)

Trying to coerce a polynomial over a finite field into a polynomial ring over a bigger field gives a bogus result:

sage: Fq.<a> = GF(5^2)
sage: Fqq.<b> = GF(5^4)
sage: f = Fq['x'].random_element(); f
3*x^2 + (a + 4)*x + 2*a + 4
sage: Fqq['y'](f)
3*y^2 + (b + 4)*y + 2*b + 4

In this example, Sage simply replaces every ‘a’ with ‘b’, but a is not b. If we coerce directly from Fq to Fqq, we get a NotImplementedError, which is unfortunate but in any case not incorrect. ;).

sage: Fqq(a)
…
/usr/local/share/sage/sage/local/lib/python2.6/site-packages/sage/rings/finite_rings/finite_field_givaro.pyc in _coerce_map_from_(self, R)
    348                 elif self.degree() % R.degree() == 0:
    349                     # This is where we *would* do coercion from one nontrivial finite field to another...
--> 350                     raise NotImplementedError
    351 
    352     def gen(self, n=0):

NotImplementedError:

Apply: trac_11239-polynomial_coercion_preliminary.patch, trac_11239-polynomial_zz_pex.patch

Change History (12)

comment:1 Changed 8 years ago by johanbosman

  • Description modified (diff)

comment:2 Changed 8 years ago by fwclarke

  • Description modified (diff)

If we coerce directly from Fq to Fqq, we get a NotImplementedError, which is unfortunate ...

It is, however, difficult to see how this could be done, because there are, in this case, two embeddings of the smaller field in the larger, neither of which can be distinguished from the other:

sage: Fq.<a> = GF(5^2); Fqq.<b> = GF(5^4)
sage: Hom(Fq, Fqq).list()
[
Ring morphism:
  From: Finite Field in a of size 5^2
  To:   Finite Field in b of size 5^4
  Defn: a |--> 4*b^3 + 4*b^2 + 4*b + 3,
Ring morphism:
  From: Finite Field in a of size 5^2
  To:   Finite Field in b of size 5^4
  Defn: a |--> b^3 + b^2 + b + 3
]

since

sage: a.minimal_polynomial().roots(ring=F625, multiplicities=False)
[4*b^3 + 4*b^2 + 4*b + 3, b^3 + b^2 + b + 3]

As for the polynomial coercion, this is seriously damaged. Bogus results are produced even when the characteristics are different. I have tracked the problem down to the following, but haven't been able to get further.

sage: Fq.<a> = GF(2^4); Fqq.<b> = GF(3^7)
sage: PFq.<x> = Fq[]; PFqq.<y> = Fqq[]
sage: f = x^3 + (a^3 + 1)*x
sage: sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX(PFqq, f)
y^3 + (b^3 + 1)*y

comment:3 follow-ups: Changed 8 years ago by dkrenn

  • Status changed from new to needs_info

It seems that everything that can be represented as polynomial is converted in that way. The phenomenon also appears with quotient rings:

sage: R.<x> = ZZ[]
sage: A.<a> = R.quotient(x^3+2); PA.<s> = A[]
sage: B.<b> = R.quotient(x^5+3); PB.<t> = B[]
sage: f = a*s^3 + a^2*s; f
a*s^3 + a^2*s
sage: PB(f)
b*t^3 + b^2*t

One way to solve this problem would be to check whether the coefficients of one polynomial rings can be converted (coerced) to the other...

comment:4 in reply to: ↑ 3 Changed 8 years ago by SimonKing

Replying to dkrenn:

One way to solve this problem would be to check whether the coefficients of one polynomial rings can be converted (coerced) to the other...

I would strongly advice against the attempt to solve it on the level of conversion.

I know that at least some classes of polynomial rings are still following the old coercion model, and am preparing a patch that is supposed to fix that. According to the new model, there should be a method _element_constructor_ that does the conversion, and a separate _coerce_map_from_, that determines whether there is a coercion (not just a conversion).

I think that it is ok to have that bogus conversion - as long as it is not used as a coercion. One could, of course, try to throw an error when doing a conversion in the case that there is no fixed embedding of the base rings. However, testing it repeatedly, that's to say testing it for each individual polynomial to be converted, sounds like a waste of computation time to me.

comment:5 Changed 6 years ago by pbruin

  • Cc pbruin added

comment:6 Changed 6 years ago by pbruin

If in the example in the ticket description, one replaces

sage: Fqq['y'](f)

by

sage: Fqq['y']._coerce_(f)

one at least gets a sensible error:

TypeError: no canonical coercion from Univariate Polynomial Ring in x over Finite Field in a of size 5^2 to Univariate Polynomial Ring in y over Finite Field in b of size 5^4

I tried the same example using the compatible finite fields from #8335. The problem (that the coefficients are converted in the stupid way) persists, both for conversion and for coercion. This is surprising, because in that case there is a coercion map between the finite fields.

comment:7 Changed 6 years ago by pbruin

The problem lies in the NTL implementation of polynomials over finite fields. (Edit: this was already discovered in comment:2 above.) This is the default implementation for polynomials over finite fields, even though the fields themselves are only implemented via NTL in characteristic 2, and via Givaro or PARI otherwise.

The following example demonstrates this (after applying #8335 plus a patch that I will upload shortly):

sage: K.<a> = GF(5^2, conway=True, prefix='z')
sage: L.<b> = GF(5^4, conway=True, prefix='z')
sage: type(K)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: R = PolynomialRing(K, 'x', implementation='NTL')
sage: S = PolynomialRing(L, 'x', implementation='NTL')
sage: f = R.gen() + a; f
x + a
sage: type(f)
<type 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>
sage: S(f)
x + b
sage: R = PolynomialRing(K, 'x', implementation='generic')
sage: S = PolynomialRing(L, 'x', implementation='generic')
sage: f = R.gen() + a; f
x + a
sage: type(f)
<class 'sage.rings.polynomial.polynomial_element_generic.Polynomial_generic_dense_field'>
sage: S(f)
x + b^3 + b^2 + b + 3
Last edited 6 years ago by pbruin (previous) (diff)

comment:8 Changed 6 years ago by pbruin

  • Authors set to pbruin
  • Cc pbruin removed
  • Dependencies set to #8335
  • Description modified (diff)
  • Status changed from needs_info to needs_work

comment:9 Changed 6 years ago by pbruin

At this point there are two possible solutions:

  • either fix the NTL polynomial constructor,
  • or make the generic polynomial constructor coerce the coefficients if necessary, and make the NTL polynomial constructor raise an error if it is given a polynomial over a smaller finite field.

The first solution would be preferable in principle, but certainly harder and maybe even unreasonable, since the NTL polynomial constructor is a lower-level thing that should not have to care about maps between non-trivial finite fields.

comment:10 in reply to: ↑ 3 Changed 6 years ago by pbruin

Replying to dkrenn:

It seems that everything that can be represented as polynomial is converted in that way. The phenomenon also appears with quotient rings:

sage: R.<x> = ZZ[]
sage: A.<a> = R.quotient(x^3+2); PA.<s> = A[]
sage: B.<b> = R.quotient(x^5+3); PB.<t> = B[]
sage: f = a*s^3 + a^2*s; f
a*s^3 + a^2*s
sage: PB(f)
b*t^3 + b^2*t

Debatable as it may seem, this is the behaviour currently described in the documentation of PolynomialQuotientRing_generic._element_constructor_(). Attempting a coercion (PB.coerce(f)) instead of a conversion (PB(f)) does lead to

TypeError: no canonical coercion from Univariate Polynomial Ring in s over Univariate Quotient Polynomial Ring in a over Integer Ring with modulus x^3 + 2 to Univariate Polynomial Ring in t over Univariate Quotient Polynomial Ring in b over Integer Ring with modulus x^5 + 3

as expected.

Changed 6 years ago by pbruin

fix coercion of polynomials over finite fields

comment:11 Changed 6 years ago by pbruin

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Fixing the NTL polynomial constructor turned out to be easy. With the second patch, polynomials over compatible finite fields (#8335) coerce correctly, and trying to convert polynomials over non-compatible finite fields raises a TypeError, as it should.

Note: See TracTickets for help on using tickets.