Opened 9 months ago

Closed 9 months ago

#32842 closed enhancement (fixed)

use PARI's fflog() for binary finite fields

Reported by: lorenz Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by 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.<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 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.

Change History (11)

comment:1 Changed 9 months ago by lorenz

  • Authors set to Lorenz Panny
  • Branch set to public/use_pari_fflog_for_binary_finite_fields
  • Commit set to f5bdb919debe1f54a313e16940ae36ddc023b052
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

f5bdb91use PARI's fflog for binary finite fields

comment:2 Changed 9 months ago by lorenz

  • Cc tscrim edgarcosta added

comment:3 Changed 9 months ago by edgarcosta

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 9 months ago by tscrim

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 9 months ago by edgarcosta

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 follow-up: Changed 9 months ago by 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.

comment:7 Changed 9 months ago by git

  • Commit changed from f5bdb919debe1f54a313e16940ae36ddc023b052 to 9ba60e755b63fce72d58ec18e6b85be152b10217

Branch pushed to git repo; I updated commit sha1. New commits:

9ba60e7slightly rephrase docstring

comment:8 in reply to: ↑ 6 Changed 9 months ago by lorenz

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 k=61 example is really bad with the generic algorithm (because the unit group order 2^61-1 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.

Version 0, edited 9 months ago by lorenz (next)

comment:9 Changed 9 months ago by edgarcosta

  • Reviewers set to Edgar Costa, Travis Scrimshaw
  • Status changed from needs_review to positive_review

The patch bot was green before :)

comment:10 Changed 9 months ago by lorenz

Thank you!

comment:11 Changed 9 months ago by vbraun

  • Branch changed from public/use_pari_fflog_for_binary_finite_fields to 9ba60e755b63fce72d58ec18e6b85be152b10217
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.