Opened 8 years ago
Last modified 6 years ago
#11239 closed defect
Incorrect coercion of polynomials over finite fields — at Version 8
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:
Change History (8)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 follow-up: ↓ 4 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
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.