#11239: Incorrect coercion of polynomials over finite fields
---------------------------+------------------------------------------------
Reporter: johanbosman | Owner: robertwb
Type: defect | Status: new
Priority: major | Milestone: sage-4.7
Component: coercion | Keywords: finite fields, polynomials,
coercion
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
---------------------------+------------------------------------------------
Old description:
> 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:
> }}}
New description:
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:
}}}
--
Comment(by fwclarke):
> 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
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11239#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
