Sage: Ticket #4553: [with patch, with positive review] a few new methods for FiniteFieldElement
https://trac.sagemath.org/ticket/4553
<p>
The attached patch adds a few methods for finite field elements. It seems as though <code>.additive_order()</code> (and therefore <code>.order()</code>) 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.
</p>
<p>
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).
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/4553
Trac 1.2John PalmieriWed, 19 Nov 2008 18:05:19 GMTattachment set
https://trac.sagemath.org/ticket/4553
https://trac.sagemath.org/ticket/4553
<ul>
<li><strong>attachment</strong>
set to <em>finitefieldelement.patch</em>
</li>
</ul>
TicketJohn PalmieriWed, 19 Nov 2008 21:51:09 GMTmilestone changed
https://trac.sagemath.org/ticket/4553#comment:1
https://trac.sagemath.org/ticket/4553#comment:1
<ul>
<li><strong>milestone</strong>
changed from <em>sage-3.3</em> to <em>sage-3.2.1</em>
</li>
</ul>
TicketJohn CremonaSat, 22 Nov 2008 17:33:44 GMT
https://trac.sagemath.org/ticket/4553#comment:2
https://trac.sagemath.org/ticket/4553#comment:2
<p>
That's funny -- in 3.2 I get
</p>
<pre class="wiki">sage: a = GF(13^5,'a').gen()
sage: a.order()
13
</pre><p>
where the function order() is implemented just as in your patch. But additive_order is not implemented.
</p>
<p>
I definitely think that this functionality should go in. But surely a.frobenius() should give <code>a^q</code> where q = a.parent().order() and not <code>a^p</code> where p = a.parent().characteristic()? Secondly, you can use a.parent().degree(), there is no need to factor q to get the degree.
</p>
<p>
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 <code>q=p^d</code>. 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).
</p>
<p>
I'm not sure when I'll have time to try doing this!
</p>
TicketJohn PalmieriMon, 24 Nov 2008 03:25:07 GMT
https://trac.sagemath.org/ticket/4553#comment:3
https://trac.sagemath.org/ticket/4553#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/4553#comment:2" title="Comment 2">cremona</a>:
</p>
<blockquote class="citation">
<p>
That's funny -- in 3.2 I get
</p>
</blockquote>
<pre class="wiki">sage: a = GF(13^5,'a').gen()
sage: a.order()
13
</pre><blockquote class="citation">
<p>
where the function order() is implemented just as in your patch. But additive_order is not implemented.
</p>
</blockquote>
<p>
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 <a class="missing wiki">ModuleElement?</a>, from which <a class="missing wiki">FiniteFieldElement?</a> 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.
</p>
<blockquote class="citation">
<blockquote>
<p>
I definitely think that this functionality should go in. But surely
a.frobenius() should give <code>a^q</code> where q = a.parent().order() and not
<code>a^p</code> where p = a.parent().characteristic()?
</p>
</blockquote>
</blockquote>
<p>
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 <code>p</code>th power map, not the <code>p^k</code>th power map.
</p>
<blockquote class="citation">
<p>
Secondly, you can use
</p>
<blockquote>
<p>
a.parent().degree(), there is no need to factor q to get the degree.
</p>
</blockquote>
</blockquote>
<p>
Good point. I was looking for this sort of thing and hadn't found it. Thanks.
</p>
<blockquote class="citation">
<blockquote>
<p>
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 <code>q=p^d</code>. 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).
</p>
</blockquote>
<blockquote>
<p>
I'm not sure when I'll have time to try doing this!
</p>
</blockquote>
</blockquote>
<p>
Is it worth accepting a patch without this efficiency change, and then adding this in later (as a separate ticket)?
</p>
TicketJohn PalmieriMon, 24 Nov 2008 03:25:50 GMTattachment set
https://trac.sagemath.org/ticket/4553
https://trac.sagemath.org/ticket/4553
<ul>
<li><strong>attachment</strong>
set to <em>finitefieldelement_new.patch</em>
</li>
</ul>
<p>
this replaces the other patch
</p>
TicketJohn CremonaMon, 24 Nov 2008 08:58:04 GMT
https://trac.sagemath.org/ticket/4553#comment:4
https://trac.sagemath.org/ticket/4553#comment:4
<p>
Sorry about my silly comment about q'th power against p'th power, I was not thinking.
</p>
<p>
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.
</p>
<p>
I hope to review this properly, but Monday morning calls...
</p>
TicketJohn CremonaTue, 25 Nov 2008 12:52:12 GMTsummary changed
https://trac.sagemath.org/ticket/4553#comment:5
https://trac.sagemath.org/ticket/4553#comment:5
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] a few new methods for FiniteFieldElement</em> to <em>[with patch, with positive review] a few new methods for FiniteFieldElement</em>
</li>
</ul>
<p>
The new patch looks good, applies cleanly to 3.2 and the doctests in both the changed files pass.
</p>
<p>
All tests in sage/structure and sage/rings pass.
</p>
<p>
I say: go for it!
</p>
TicketMichael AbshoffTue, 25 Nov 2008 13:14:03 GMT
https://trac.sagemath.org/ticket/4553#comment:6
https://trac.sagemath.org/ticket/4553#comment:6
<p>
Hmm, should we deprecate "order" in sage/rings/finite_field_element.py ?
</p>
<p>
Cheers,
</p>
<p>
Michael
</p>
TicketMichael AbshoffTue, 25 Nov 2008 13:41:46 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/4553#comment:7
https://trac.sagemath.org/ticket/4553#comment:7
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
<p>
Merged finitefieldelement_new.patch in Sage 3.2.1.alpha1
</p>
Ticket