Ask Your Question

field extension not implemented

asked 2017-04-29 12:39:32 -0500

gelatine1 gravatar image

I'm trying to construct some field extenstions of GF(p), this is what I have

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?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2017-04-30 05:39:38 -0500

B r u n o gravatar image

updated 2017-05-02 10:19:10 -0500

[tl;dr] There is a bug, addressed by 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), 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 though I do not know if it is easily usable.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2017-04-29 12:39:32 -0500

Seen: 63 times

Last updated: May 02