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 )
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
- Description modified (diff)
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 follow-ups: ↓ 4 ↓ 10 Changed 8 years ago by
- 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
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
- Cc pbruin added
comment:6 Changed 6 years ago by
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
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
comment:8 Changed 6 years ago by
- 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
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
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.
comment:11 Changed 6 years ago by
- 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.
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:
since
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.