#23940 closed enhancement (fixed)
implement proper blackbox discrete logarithm for AdditiveAbelianGroupWrapper
Reported by:  Lorenz Panny  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description
This takes care of the
TODO: Implement proper blackbox discrete logarithm (using babystep giantstep).
in the AdditiveAbelianGroupWrapper
class.
The proposed implementation first reduces to the case of pgroups using the Chinese remainder theorem. To solve the problem in pgroups, 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
Status:  new → needs_review 

comment:2 Changed 5 years ago by
Commit:  923edc15766f2c032da9d33c445e8726eff73c89 → 3cf6024a2aa0a8812ffe815136e4a2f788130f66 

comment:3 Changed 5 years ago by
Keywords:  abstract generalized removed 

Milestone:  sage8.1 → sage8.2 
Reviewers:  → Vincent Delecroix 
Status:  needs_review → needs_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
 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.
 You need a linebreak after
EXAMPLES::
 You should provide benchmarks that show that you are not making worse the simple cases.
comment:5 Changed 2 years ago by
Commit:  3cf6024a2aa0a8812ffe815136e4a2f788130f66 → d43a1088db07f42554fe090e2a485c2e1695c779 

Branch pushed to git repo; I updated commit sha1. New commits:
d43a108  Merge branch 'develop' into public/AdditiveAbelianGroupWrapper_discrete_log

comment:6 Changed 2 years ago by
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 babystep giantstep (squareroot complexity) in the cyclic primeorder 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
Milestone:  sage8.2 → sage9.2 

Status:  needs_work → needs_review 
comment:8 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:9 Changed 21 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:10 Changed 19 months ago by
Commit:  d43a1088db07f42554fe090e2a485c2e1695c779 → d652ce4c233a473ad40576873d213bccba475647 

comment:11 Changed 19 months ago by
Reviewers:  Vincent Delecroix → Vincent 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
Status:  needs_review → positive_review 

comment:13 Changed 18 months ago by
Branch:  public/AdditiveAbelianGroupWrapper_discrete_log → d652ce4c233a473ad40576873d213bccba475647 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:14 Changed 11 months ago by
Commit:  d652ce4c233a473ad40576873d213bccba475647 

follow up #33121
Branch pushed to git repo; I updated commit sha1. New commits:
add missing linebreak in docstring