Opened 14 years ago

Closed 14 years ago

#4553 closed enhancement (fixed)

[with patch, with positive review] a few new methods for FiniteFieldElement

Reported by: John Palmieri Owned by: somebody
Priority: major Milestone: sage-3.2.1
Component: algebra Keywords: finite field element
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The attached patch adds a few methods for finite field elements. It seems as though .additive_order() (and therefore .order()) was not implemented before (!), so I've implemented that. I've also implemented pth powers and pth roots, where p is the characteristic of the field.

These are written pretty naively, so they may not be that fast. If anyone has suggestions for improvements, I'm happy to hear them (or to have you implement them).

Attachments (2)

finitefieldelement.patch (2.7 KB) - added by John Palmieri 14 years ago.
finitefieldelement_new.patch (3.3 KB) - added by John Palmieri 14 years ago.
this replaces the other patch

Download all attachments as: .zip

Change History (9)

Changed 14 years ago by John Palmieri

Attachment: finitefieldelement.patch added

comment:1 Changed 14 years ago by John Palmieri

Milestone: sage-3.3sage-3.2.1

comment:2 Changed 14 years ago by John Cremona

That's funny -- in 3.2 I get

sage: a = GF(13^5,'a').gen()
sage: a.order()
13

where the function order() is implemented just as in your patch. But additive_order is not implemented.

I definitely think that this functionality should go in. But surely a.frobenius() should give a^q where q = a.parent().order() and not a^p where p = a.parent().characteristic()? Secondly, you can use a.parent().degree(), there is no need to factor q to get the degree.

Lastly, I think it would be more efficient to compute (and cache) the matrix of frobenius as a linear map, viewing F_q as an F_p-vector space of dimension d where q=p^d. I know an efficient way to do this (similar to tricks used in Berlekamp factorization). Then taking q'th roots would be easy (invert the matrix).

I'm not sure when I'll have time to try doing this!

comment:3 in reply to:  2 Changed 14 years ago by John Palmieri

Replying to cremona:

That's funny -- in 3.2 I get

sage: a = GF(13^5,'a').gen()
sage: a.order()
13

where the function order() is implemented just as in your patch. But additive_order is not implemented.

I'm not sure why I was thinking that order() wasn't implemented. Anyway, in sage/structure/element.pyx, it says something like "don't override order, override additive_order instead" -- this is for instances of the class ModuleElement?, from which FiniteFieldElement? inherits. So I'll produce a new patch that removes order() from finite_field_element.py and has the definition of additive_order() in element.pyx.

I definitely think that this functionality should go in. But surely a.frobenius() should give a^q where q = a.parent().order() and not a^p where p = a.parent().characteristic()?

But then the Frobenius map would always be the identity! Also, for what it's worth, both wikipedia and mathworld describe the Frobenius as being the pth power map, not the p^kth power map.

Secondly, you can use

a.parent().degree(), there is no need to factor q to get the degree.

Good point. I was looking for this sort of thing and hadn't found it. Thanks.

Lastly, I think it would be more efficient to compute (and cache) the matrix of frobenius as a linear map, viewing F_q as an F_p-vector space of dimension d where q=p^d. I know an efficient way to do this (similar to tricks used in Berlekamp factorization). Then taking q'th roots would be easy (invert the matrix).

I'm not sure when I'll have time to try doing this!

Is it worth accepting a patch without this efficiency change, and then adding this in later (as a separate ticket)?

Changed 14 years ago by John Palmieri

this replaces the other patch

comment:4 Changed 14 years ago by John Cremona

Sorry about my silly comment about q'th power against p'th power, I was not thinking.

The linear algebra approach will have to wait until we have a common interface for all finite fields -- currently the functions available depend on q since they differ according to whether we use givaro or NTL or pari. (e.g. an element a in GF(q) sometimes has a._coordinates() but not always. So it's fine to go ahead with this one for now, perhaps with a note that a better implementation might be possible in future.

I hope to review this properly, but Monday morning calls...

comment:5 Changed 14 years ago by John Cremona

Summary: [with patch, needs review] a few new methods for FiniteFieldElement[with patch, with positive review] a few new methods for FiniteFieldElement

The new patch looks good, applies cleanly to 3.2 and the doctests in both the changed files pass.

All tests in sage/structure and sage/rings pass.

I say: go for it!

comment:6 Changed 14 years ago by Michael Abshoff

Hmm, should we deprecate "order" in sage/rings/finite_field_element.py ?

Cheers,

Michael

comment:7 Changed 14 years ago by Michael Abshoff

Resolution: fixed
Status: newclosed

Merged finitefieldelement_new.patch in Sage 3.2.1.alpha1

Note: See TracTickets for help on using tickets.