| 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. |
