Opened 2 years ago
Last modified 2 years ago
#23940 needs_work enhancement
implement proper black-box discrete logarithm for AdditiveAbelianGroupWrapper
Reported by: | lorenz | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.2 |
Component: | group theory | Keywords: | abelian group, discrete logarithm |
Cc: | Merged in: | ||
Authors: | Lorenz Panny | Reviewers: | Vincent Delecroix |
Report Upstream: | N/A | Work issues: | |
Branch: | public/AdditiveAbelianGroupWrapper_discrete_log (Commits) | Commit: | 3cf6024a2aa0a8812ffe815136e4a2f788130f66 |
Dependencies: | Stopgaps: |
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 (4)
comment:1 Changed 2 years ago by
- Status changed from new to needs_review
comment:2 Changed 2 years ago by
- Commit changed from 923edc15766f2c032da9d33c445e8726eff73c89 to 3cf6024a2aa0a8812ffe815136e4a2f788130f66
comment:3 Changed 2 years ago by
- Keywords abstract generalized removed
- Milestone changed from sage-8.1 to sage-8.2
- Reviewers set to Vincent Delecroix
- Status changed from needs_review to 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:4 Changed 2 years ago by
Sorry, 1. is fixed in your commit 923edc1
Branch pushed to git repo; I updated commit sha1. New commits:
add missing linebreak in docstring