Iterating over finite extension fields.

[D. Monarres]

Hello All,

First off, I would like to say that Sage is great and all of the hard
work that the developers have put forth definitely shows.

I am writing a tutorial for using Sage in undergraduate mathematics
courses at a public 4 year university and am running into a few
issues. I would appreciate any help and if these are indeed bugs than
I wouldn't mind being pointed toward where I can go to help fix them.


So right now I am going through constructing finite fields in a couple
of different ways. One using the build in GF command with different
moduli and the other is by constructing a prime field and then
extending it using the root of a irreducible polynomial of specified
degree. As there is not any "all irreducible polynomials of a certain
degree command in Sage" I just constructed all polynomials of that
degree and then filtered the list using the is_reducible() method.

For example, to construct all degree two polynomials over GF(5) I did

sage: F5 = GF(5)
sage: P.<x> = PolynomialRing(F5, 'x')
sage: AP = [ a1 + a2*x + a3*x^2 for (a1,a2,a3) in F5^3 if a3 !=
F5(0) ]

then I filter like this

sage: IR = [ p for p in AP if p.is_irreducible() ]
sage: PR = [ p for p in AP if p.is_primitive() ]

Then I construct F_{5^2}

sage: F25.<a> = F5.extension( PR[0], 'a')


and everything works great. The problem arises when I want to extend
this field. When I try to construct my polynomial over F25 I get an
error that F25 does not allow for iteration.

Is there a better way to construct a list of irreducible and/or
primitive polynomials in Sage? Do you think that
PolynomialQuotientRing_field can be extended to support iteration as
long as it is finite? I would be willing to make an attempt at doing
this if somebody could give me some tips as to where to begin?

Thank you all for your hard work,

David Monarres

[D. Monarres]

Hello all,

Don't mean to reply to my own question. I guess what I am wondering is
why the finite extension of a finite field isn't a finite field. By
having the results being a polynomial ring over the prime field it
seems as if a lot is lost. Is there room to alter this behavior, or
was there a conscious design decision made when choosing this? Once
again thank you for all of your hard work.

David

[zsharon]

I'm no expert, but it seems to me that when you make your list
manually, you're throwing away all of the structure. When you form a
subset of a field (or group, ring, etc), sage doesn't necessarily keep
track of the fact that you are making a subfield (ring, group, etc).

For example, if G is a group, and I want a specific subgroup, picking
out the elements I want and listing them isn't enough (even if they
*do* form a subgroup). I need to fist make the list, say H, then use
G.subgroup(H), which will form the subgroup of G generated by the
elements listed in H.

I don't have a whole lot of experience with this, but I hope this has
helped.

Zach

[Nils Bruin]

On May 25, 12:26 pm, "D. Monarres" <dmmonar...@gmail.com> wrote:
> Then I construct F_{5^2}
>
> sage: F25.<a>   = F5.extension( PR[0], 'a')
>
> and everything works great. The problem arises when  I want to extend
> this field. When I try to construct my polynomial over F25 I get an
> error that F25 does not allow for iteration.

You are hitting a generic implementation here. The same code would get
called for other base rings as well. If you want a finite field, you
can use the "modulus=" keyword with GF. See "GF?" for more
information.

> Do you think that
> PolynomialQuotientRing_field can be extended to support iteration as
> long as it is finite?

It could, but it might be the wrong place to do it. The fact that the
result was going to be finite was already known when F5.extension got
called, so the obvious place to effect a changed behaviour would be by
specializing the "extension" method on finite fields. If the modulus
is irreducible (and even the generic code seems to check for that), it
could specialize to the required GF(...,modulus=,,,) call.

One might want to check that all the generic methods available on the
result of F5.extension are also available on the result of GF,
otherwise the change would break code that depends on the current
behaviour (if any).

The reason why F5.extension doesn't produce a "finite field" is
probably because there is another way of doing that and the original
authors didn't bother specializing F5.extension to it (the very
existence of F5.extension might postdate the GF(...modulus=...) call
and only appear on finite fields due to inheritance).

[D. M. Monarres]

Thank you all,

I hope that I didn't seem annoyed by the current way of doing things.
I have been charged with translating some examples for an
undergraduate algebra course which use Magma where this is a valid
construction.

The whole goal of the example was to have the students do the
extension over the non-prime field, but since this isn't possible, and
may be very difficult to do in general, I will find a way around this.
Thank you for all of the help!

Regards,

David M. Monarres
<dmmon...@gmail.com>

P.S. If anybody has any literature which outlines the algorithms
required to implement the more general construction it would be great.
I have time over the summer and would love to contribute what I can.

> --
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org
>