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