Changes between Initial Version and Version 1 of Ticket #32842


Ignore:
Timestamp:
11/10/21 02:42:05 (9 months ago)
Author:
lorenz
Comment:

New commits:

f5bdb91use PARI's fflog for binary finite fields

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #32842

    • Property Status changed from new to needs_review
    • Property Commit changed from to f5bdb919debe1f54a313e16940ae36ddc023b052
    • Property Branch changed from to public/use_pari_fflog_for_binary_finite_fields
    • Property Authors changed from to Lorenz Panny
  • Ticket #32842 – Description

    initial v1  
    11Currently, `FiniteField_ntl_gf2eElement` calls generic-group `discrete_log()` to compute logarithms.
    22
    3 We should instead call PARI's `fflog()`, which uses an index-calculus algorithm and is dramatically faster in some cases.
     3The patch instead calls PARI's `fflog()`, which uses an index-calculus algorithm and is dramatically faster in some cases.
     4
     5Sage 9.4:
     6{{{
     7sage: F.<a> = GF(2^67)
     8sage: %timeit F.random_element().log(a)
     92.78 s ± 270 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     10}}}
     11
     12This patch:
     13{{{
     14sage: F.<a> = GF(2^67)
     15sage: %timeit F.random_element().log(a)
     16359 ms ± 71.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
     17}}}
     18
     19Examples 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.
     20
     21The 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.