#4625: improve pth power map for finite fields of characteristic p
-------------------------+--------------------------------------------------
Reporter: jhpalmieri | Owner: somebody
Type: enhancement | Status: new
Priority: minor | Milestone: sage-3.3
Component: algebra | Keywords: field element, frobenius
-------------------------+--------------------------------------------------
The implementation of the pth_power method for FiniteFieldElement is
naive; maybe it can be sped up. cremona had the following suggestion in
the discussion about ticket #4553:
{{{
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).
}}}
{{{
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.
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4625>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
