Opened 6 months ago

Closed 4 months ago

#33112 closed enhancement (fixed)

some speedups in AdditiveAbelianGroupWrapper.discrete_log()

Reported by: lorenz Owned by:
Priority: major Milestone: sage-9.6
Component: group theory Keywords:
Cc: vdelecroix Merged in:
Authors: Lorenz Panny Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: b8f4127 (Commits, GitHub, GitLab) Commit: b8f4127228cca2dd74c7bde5e092f6ed51a8d9c7
Dependencies: #32384 Stopgaps:

Status badges

Description (last modified by lorenz)

Currently, the .discrete_log() method for AdditiveAbelianGroupWrappers contains several unnecessary calls to .order() for the underlying group elements. In some cases (e.g., elliptic curves over large finite fields), these calls incur significant overhead. We eliminate them and also apply some smaller performance tweaks while we're at it (such as using the exponent instead of the order and isqrt instead of sqrt).

Example:

sage: p = 4*prod(primes(3,117))-1
sage: E = EllipticCurve(GF(p^2),[1,0])
sage: A = E.abelian_group()
sage: %timeit A.discrete_log(E.random_point())

Result before this patch:

22.6 s ± 765 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Result after this patch:

3.74 s ± 78.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Changes not including the dependency: https://git.sagemath.org/sage.git/diff/?id=c64156e2cfd95a1b7f5b9b431dad4b80ff757ac0&id2=41983ca059b4c5ed6ab6a76b2ca0934a29834079

Change History (8)

comment:1 Changed 6 months ago by lorenz

  • Cc vdelecroix added
  • Status changed from new to needs_review

comment:2 Changed 5 months ago by git

  • Commit changed from 43c03e5cd3e5b17b68d875d1aad80a8dc1bce74c to c64156e2cfd95a1b7f5b9b431dad4b80ff757ac0

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

294f5bdadd missing copyright comment
41983caMerge tag '9.5' into public/some_AdditiveAbelianGroupWrapper_discrete_log_speedups
636c927some optimizations in AdditiveAbelianGroupWrapper.discrete_log()
c64156emake type conversions slightly more robust

comment:3 Changed 5 months ago by lorenz

  • Description modified (diff)

comment:4 Changed 5 months ago by tscrim

I think the list comprehension is faster (in python) than using map with a lambda function.

I would make _discrete_log_pgroup into its own function rather than a @staticmethod. This can make it easier if you decide you want to Cythonize it too.

comment:5 Changed 5 months ago by git

  • Commit changed from c64156e2cfd95a1b7f5b9b431dad4b80ff757ac0 to b8f4127228cca2dd74c7bde5e092f6ed51a8d9c7

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

10ac2e8Merge tag '9.6.beta1' into public/some_AdditiveAbelianGroupWrapper_discrete_log_speedups
b8f4127use list comprehension instead of lambda; move _discrete_log_pgroup outside class

comment:6 Changed 5 months ago by lorenz

Thank you, done.

comment:7 Changed 4 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Thank you. LGTM.

comment:8 Changed 4 months ago by vbraun

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