Sage: Ticket #32842: use PARI's fflog() for binary finite fields
https://trac.sagemath.org/ticket/32842
<p>
Currently, <code>FiniteField_ntl_gf2eElement</code> calls generic-group <code>discrete_log()</code> to compute logarithms.
</p>
<p>
The patch instead calls PARI's <code>fflog()</code>, which uses an index-calculus algorithm and is dramatically faster in some cases.
</p>
<p>
Sage 9.4:
</p>
<pre class="wiki">sage: F.<a> = GF(2^67)
sage: %timeit F.random_element().log(a)
2.78 s ± 270 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
</pre><p>
This patch:
</p>
<pre class="wiki">sage: F.<a> = GF(2^67)
sage: %timeit F.random_element().log(a)
359 ms ± 71.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
</pre><p>
Examples with highly non-smooth <code>2^k-1</code>, such as <code>k=61</code>, showcase even larger differences. Examples with very smooth <code>2^k-1</code> are occasionally a little bit faster using the naïve code, but after playing around with this for a while I concluded that figuring out which algorithm to use ahead of time is no less costly than just letting PARI deal with it.
</p>
<p>
The patch does make sure to pass the (at this point, already cached) factorization of <code>2^k-1</code> to PARI so we don't factor again.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/32842
Trac 1.1.6lorenzWed, 10 Nov 2021 02:42:05 GMTstatus, description changed; commit, branch, author set
https://trac.sagemath.org/ticket/32842#comment:1
https://trac.sagemath.org/ticket/32842#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>f5bdb919debe1f54a313e16940ae36ddc023b052</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/32842?action=diff&version=1">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>public/use_pari_fflog_for_binary_finite_fields</em>
</li>
<li><strong>author</strong>
set to <em>Lorenz Panny</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=f5bdb919debe1f54a313e16940ae36ddc023b052"><span class="icon"></span>f5bdb91</a></td><td><code>use PARI's fflog for binary finite fields</code>
</td></tr></table>
TicketlorenzWed, 10 Nov 2021 07:40:46 GMTcc set
https://trac.sagemath.org/ticket/32842#comment:2
https://trac.sagemath.org/ticket/32842#comment:2
<ul>
<li><strong>cc</strong>
<em>tscrim</em> <em>edgarcosta</em> added
</li>
</ul>
TicketedgarcostaWed, 10 Nov 2021 09:36:44 GMT
https://trac.sagemath.org/ticket/32842#comment:3
https://trac.sagemath.org/ticket/32842#comment:3
<p>
The code looks good to me.
However, I find it odd the comment
</p>
<pre class="wiki">Big instances used to take very long before :trac:`32842`::
</pre><p>
in the examples block quite odd.
</p>
<p>
Travis, what do you think?
</p>
TickettscrimWed, 10 Nov 2021 09:51:16 GMT
https://trac.sagemath.org/ticket/32842#comment:4
https://trac.sagemath.org/ticket/32842#comment:4
<p>
Are you referring to the English or the example itself? The English is a bit strange to me, and I would phrase it as
</p>
<pre class="wiki">Big instances used to take a very long time before :trac:`32842`::
</pre>
TicketedgarcostaWed, 10 Nov 2021 09:54:44 GMT
https://trac.sagemath.org/ticket/32842#comment:5
https://trac.sagemath.org/ticket/32842#comment:5
<p>
The example, as I usually only see trac tickets mentioned under tests referring to a bug that has been fixed.
This is only a minor thing, and if you think it's alright, we can give it a positive review.
</p>
TickettscrimWed, 10 Nov 2021 10:01:21 GMT
https://trac.sagemath.org/ticket/32842#comment:6
https://trac.sagemath.org/ticket/32842#comment:6
<p>
I think the example is fine, although it could be made better by having something that takes a really long time (>10s, even better >30s) prior but finishes within 1 second now.
</p>
TicketgitWed, 10 Nov 2021 10:09:00 GMTcommit changed
https://trac.sagemath.org/ticket/32842#comment:7
https://trac.sagemath.org/ticket/32842#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>f5bdb919debe1f54a313e16940ae36ddc023b052</em> to <em>9ba60e755b63fce72d58ec18e6b85be152b10217</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=9ba60e755b63fce72d58ec18e6b85be152b10217"><span class="icon"></span>9ba60e7</a></td><td><code>slightly rephrase docstring</code>
</td></tr></table>
TicketlorenzWed, 10 Nov 2021 10:11:02 GMT
https://trac.sagemath.org/ticket/32842#comment:8
https://trac.sagemath.org/ticket/32842#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/32842#comment:6" title="Comment 6">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I think the example is fine, although it could be made better by having something that takes a really long time (>10s, even better >30s) prior but finishes within 1 second now.
</p>
</blockquote>
<p>
It does: The <code>2^61</code> example is a worst-case input for the generic algorithm (because the unit group order <code>2^61-1</code> is prime). On my laptop, it eats all my RAM and dies after a couple of minutes. With the patch, it finishes successfully within a few hundred milliseconds.
</p>
TicketedgarcostaWed, 10 Nov 2021 11:38:40 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/32842#comment:9
https://trac.sagemath.org/ticket/32842#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Edgar Costa, Travis Scrimshaw</em>
</li>
</ul>
<p>
The patch bot was green before :)
</p>
TicketlorenzWed, 10 Nov 2021 13:58:28 GMT
https://trac.sagemath.org/ticket/32842#comment:10
https://trac.sagemath.org/ticket/32842#comment:10
<p>
Thank you!
</p>
TicketvbraunSun, 14 Nov 2021 17:05:10 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/32842#comment:11
https://trac.sagemath.org/ticket/32842#comment:11
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/use_pari_fflog_for_binary_finite_fields</em> to <em>9ba60e755b63fce72d58ec18e6b85be152b10217</em>
</li>
</ul>
Ticket