id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
32842,use PARI's fflog() for binary finite fields,lorenz,,"Currently, `FiniteField_ntl_gf2eElement` calls generic-group `discrete_log()` to compute logarithms.
The patch instead calls PARI's `fflog()`, which uses an index-calculus algorithm and is dramatically faster in some cases.
Sage 9.4:
{{{
sage: F. = 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. = 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 non-smooth `2^k-1`, such as `k=61`, showcase even larger differences. Examples with very smooth `2^k-1` 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^k-1` to PARI so we don't factor again.",enhancement,closed,major,sage-9.5,number theory,fixed,,tscrim edgarcosta,,Lorenz Panny,"Edgar Costa, Travis Scrimshaw",N/A,,9ba60e755b63fce72d58ec18e6b85be152b10217,9ba60e755b63fce72d58ec18e6b85be152b10217,,