Opened 5 years ago

Closed 18 months ago

Last modified 11 months ago

#23940 closed enhancement (fixed)

implement proper black-box discrete logarithm for AdditiveAbelianGroupWrapper

Reported by: Lorenz Panny Owned by:
Priority: major Milestone: sage-9.4
Component: group theory Keywords: abelian group, discrete logarithm
Cc: Merged in:
Authors: Lorenz Panny Reviewers: Vincent Delecroix, David Roe
Report Upstream: N/A Work issues:
Branch: d652ce4 (Commits, GitHub, GitLab) Commit:
Dependencies: Stopgaps:

Status badges

Description

This takes care of the

TODO: Implement proper black-box discrete logarithm (using baby-step giant-step).

in the AdditiveAbelianGroupWrapper class.

The proposed implementation first reduces to the case of p-groups using the Chinese remainder theorem. To solve the problem in p-groups, a basic version of an algorithm by Sutherland (https://arxiv.org/abs/0809.3413) is used.

Compared to the previous (brute force) implementation, the new code yields huge speedups: For instance, the example

F.<t> = GF(431**2)
E = EllipticCurve(j=316*t+116)
A = E.abelian_group()
print(A._discrete_log(E.random_point()))

takes over two minutes on my machine using sage 8.0, but with the new code it finishes in less than 100 milliseconds on average.

Change History (14)

comment:1 Changed 5 years ago by Lorenz Panny

Status: newneeds_review

comment:2 Changed 5 years ago by git

Commit: 923edc15766f2c032da9d33c445e8726eff73c893cf6024a2aa0a8812ffe815136e4a2f788130f66

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

3cf6024add missing linebreak in docstring

comment:3 Changed 5 years ago by Vincent Delecroix

Keywords: abstract generalized removed
Milestone: sage-8.1sage-8.2
Reviewers: Vincent Delecroix
Status: needs_reviewneeds_work

It looks like a great improvement to the Sage library!

Sadly your commits do not apply on the latest beta. You have to rebase your changes on the top of 8.1.rc4.

Concerning the code

  1. In
    +    def _discrete_log_pgroup(self, p, aa, b):
    +        from sage.arith.misc import valuation
    +        from sage.functions.other import ceil, sqrt
    +        from itertools import product as iproduct
    +        r"""
    
    The 3 import statements have to go after the docstring.
  1. You need a linebreak after EXAMPLES::
  1. You should provide benchmarks that show that you are not making worse the simple cases.

comment:4 Changed 5 years ago by Vincent Delecroix

Sorry, 1. is fixed in your commit 923edc1

comment:5 Changed 2 years ago by git

Commit: 3cf6024a2aa0a8812ffe815136e4a2f788130f66d43a1088db07f42554fe090e2a485c2e1695c779

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

d43a108Merge branch 'develop' into public/AdditiveAbelianGroupWrapper_discrete_log

comment:6 Changed 2 years ago by Lorenz Panny

Thanks for the feedback and sorry for taking almost three years to continue this.

I've rebased the patch onto the current develop branch.

Regarding benchmarks, here's an example on my laptop for a "simple case" (a cyclic group of prime order):

  • Current develop:
    sage: G = AdditiveAbelianGroup([31337])
    sage: A = AdditiveAbelianGroupWrapper(G.0.parent(), G.gens(), [g.order() for g in G.gens()])
    sage: %timeit A._discrete_log(randrange(31337)*G.0)
    1 loop, best of 5: 3.24 s per loop
    
  • Commit d43a1088db07f42554fe090e2a485c2e1695c779:
    sage: G = AdditiveAbelianGroup([31337])
    sage: A = AdditiveAbelianGroupWrapper(G.0.parent(), G.gens(), [g.order() for g in G.gens()])
    sage: %timeit A._discrete_log(randrange(31337)*G.0)
    10 loops, best of 5: 26.2 ms per loop
    

The speedup is extremely significant. This is because the old implementation used naïve brute force (linear complexity) whereas the new algorithm reduces to baby-step giant-step (square-root complexity) in the cyclic prime-order case. This case is in fact the hardest for the new algorithm and the speedup should be even bigger on more "decomposable" group structures.

comment:7 Changed 2 years ago by Lorenz Panny

Milestone: sage-8.2sage-9.2
Status: needs_workneeds_review

comment:8 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:9 Changed 21 months ago by Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:10 Changed 19 months ago by git

Commit: d43a1088db07f42554fe090e2a485c2e1695c779d652ce4c233a473ad40576873d213bccba475647

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

a0ee141Merge branch 'public/AdditiveAbelianGroupWrapper_discrete_log' of git://trac.sagemath.org/sage into t/23940/discrete_log
d652ce4small fixes

comment:11 Changed 19 months ago by David Roe

Reviewers: Vincent DelecroixVincent Delecroix, David Roe

I made some small fixes to make the plugin happy. Positive review if tests pass.

comment:12 Changed 19 months ago by David Roe

Status: needs_reviewpositive_review

comment:13 Changed 18 months ago by Volker Braun

Branch: public/AdditiveAbelianGroupWrapper_discrete_logd652ce4c233a473ad40576873d213bccba475647
Resolution: fixed
Status: positive_reviewclosed

comment:14 Changed 11 months ago by Vincent Delecroix

Commit: d652ce4c233a473ad40576873d213bccba475647

follow up #33121

Note: See TracTickets for help on using tickets.