Opened 15 months ago
Closed 15 months ago
#32842 closed enhancement (fixed)
use PARI's fflog() for binary finite fields
Reported by:  lorenz  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  number theory  Keywords:  
Cc:  tscrim, edgarcosta  Merged in:  
Authors:  Lorenz Panny  Reviewers:  Edgar Costa, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  9ba60e7 (Commits, GitHub, GitLab)  Commit:  9ba60e755b63fce72d58ec18e6b85be152b10217 
Dependencies:  Stopgaps: 
Description (last modified by )
Currently, FiniteField_ntl_gf2eElement
calls genericgroup discrete_log()
to compute logarithms.
The patch instead calls PARI's fflog()
, which uses an indexcalculus algorithm and is dramatically faster in some cases.
Sage 9.4:
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)
This patch:
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)
Examples with highly nonsmooth 2^k1
, such as k=61
, showcase even larger differences. Examples with very smooth 2^k1
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.
The patch does make sure to pass the (at this point, already cached) factorization of 2^k1
to PARI so we don't factor again.
Change History (11)
comment:1 Changed 15 months ago by
Authors:  → Lorenz Panny 

Branch:  → public/use_pari_fflog_for_binary_finite_fields 
Commit:  → f5bdb919debe1f54a313e16940ae36ddc023b052 
Description:  modified (diff) 
Status:  new → needs_review 
comment:2 Changed 15 months ago by
Cc:  tscrim edgarcosta added 

comment:3 Changed 15 months ago by
The code looks good to me. However, I find it odd the comment
Big instances used to take very long before :trac:`32842`::
in the examples block quite odd.
Travis, what do you think?
comment:4 Changed 15 months ago by
Are you referring to the English or the example itself? The English is a bit strange to me, and I would phrase it as
Big instances used to take a very long time before :trac:`32842`::
comment:5 Changed 15 months ago by
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.
comment:6 followup: 8 Changed 15 months ago by
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.
comment:7 Changed 15 months ago by
Commit:  f5bdb919debe1f54a313e16940ae36ddc023b052 → 9ba60e755b63fce72d58ec18e6b85be152b10217 

Branch pushed to git repo; I updated commit sha1. New commits:
9ba60e7  slightly rephrase docstring

comment:8 Changed 15 months ago by
Replying to tscrim:
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.
It does: The 2^61
example is a worstcase input for the generic algorithm (because the unit group order 2^611
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.
comment:9 Changed 15 months ago by
Reviewers:  → Edgar Costa, Travis Scrimshaw 

Status:  needs_review → positive_review 
The patch bot was green before :)
comment:11 Changed 15 months ago by
Branch:  public/use_pari_fflog_for_binary_finite_fields → 9ba60e755b63fce72d58ec18e6b85be152b10217 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
use PARI's fflog for binary finite fields