ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 30 Apr 2017 12:39:38 +0200field extension not implementedhttps://ask.sagemath.org/question/37467/field-extension-not-implemented/I'm trying to construct some field extenstions of GF(p), this is what I have
p=5
F=GF(p)
R1.<x> = F['x']
F1.<alpha1> = F.extension(x^p - x - 1)
R2.<x> = F1['x']
F2.<alpha2> = F1.extension(x^p - x - alpha1^(p-1))
R3.<x> = F2['x']
F3.<alpha3> = F2.extension(x^p - x - (alpha1*alpha2)^(p-1))
R4.<x> = F3['x']
F4.<alpha4> = F3.extension(x^p - x - (alpha1*alpha2*alpha3)^(p-1))
It creates F3 like it should but it doesn't create F4. I get a NotImplementedError... What did I do wrong?Sat, 29 Apr 2017 19:39:32 +0200https://ask.sagemath.org/question/37467/field-extension-not-implemented/Answer by B r u n o for <p>I'm trying to construct some field extenstions of GF(p), this is what I have</p>
<pre><code>p=5
F=GF(p)
R1.<x> = F['x']
F1.<alpha1> = F.extension(x^p - x - 1)
R2.<x> = F1['x']
F2.<alpha2> = F1.extension(x^p - x - alpha1^(p-1))
R3.<x> = F2['x']
F3.<alpha3> = F2.extension(x^p - x - (alpha1*alpha2)^(p-1))
R4.<x> = F3['x']
F4.<alpha4> = F3.extension(x^p - x - (alpha1*alpha2*alpha3)^(p-1))
</code></pre>
<p>It creates F3 like it should but it doesn't create F4. I get a NotImplementedError... What did I do wrong?</p>
https://ask.sagemath.org/question/37467/field-extension-not-implemented/?answer=37471#post-id-37471**[tl;dr]** There is a bug, addressed by ticket [#22910](https://trac.sagemath.org/ticket/22910). Note yet that the bug resolution will probably fall short of fully solving the problem, since SageMath will be able to build the requested extensions, but will not recognize them as fields (simply as rings).**[/tl;dr]**
What happens is the following: When you try to build the polynomial ring `R4`, SageMath tries to determine whether the base ring (here `F3`) is a field or not. Since `F3` is defined as the extension of `F2` using the polynomial $x^p-x-(\alpha_1\alpha_2)^{p-1}$, it testes whether this polynomial (with coefficients in `F2`) is irreducible. Here comes the problem: Factorization and irreducibility tests are not defined (in SageMath) for polynomials over `F2`.
The more general problem is that SageMath does not correctly handle towers of fields extensions. One can notice the differences the fields you defines, based on their types:
sage: type(F)
<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>
sage: type(F1)
<class 'sage.rings.finite_rings.finite_field_givaro.FiniteField_givaro_with_category'>
sage: type(F2)
<class 'sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_field_with_category'>
sage: type(F3)
<class 'sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic_with_category'>
As you can read, `F` is known to be a prime finite field, `F1` is a finite field that is implemented behind the scene by the Givaro library ([doc](http://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/finite_field_givaro.html)), `F2` is a field implemented as a quotient ring, and `F3` is simply a quotient ring but SageMath does not know it is a field. In other words, your successive extensions have less and less structure for SageMath. In particular, since `F2` is only known to be a quotient ring defined by an irreducible polynomial (thus a field), SageMath does not provide any factorization algorithm nor irreducibility test for polynomials over `F2`. This explains the exception you get.
Finally, I still see the exception you get while trying to build `R4` as a bug, and I'll open a ticket for this. A simple solution to handle this bug is the following: While building `R4`, SageMath tries to determine whether the modulus of `F3` is irreducible and this raises an exception; a solution is simply to catch the exception and continue the computation as if one would know that the polynomial is not irreducible. Note that it probably won't completely solve your problem since as I mention, SageMath does not know that `F3` is a field, and won't know that the subsequent extensions are fields too. In other words, you'll be able to build these extensions, but SageMath will provide only very basic functionality.
It would be a much better solution of course to implement factorization algorithms over fields extensions and to have a good way of dealing with towers of field extensions, but this is more work! I think that some implementation is available [here](https://github.com/defeo/ffisom) though I do not know if it is easily usable.Sun, 30 Apr 2017 12:39:38 +0200https://ask.sagemath.org/question/37467/field-extension-not-implemented/?answer=37471#post-id-37471