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 lorenz

  • Status changed from new to needs_review

comment:2 Changed 2 years ago by git

  • Commit changed from 923edc15766f2c032da9d33c445e8726eff73c89 to 3cf6024a2aa0a8812ffe815136e4a2f788130f66

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

3cf6024add missing linebreak in docstring

comment:3 Changed 2 years ago by vdelecroix

  • 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

  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 2 years ago by vdelecroix

Sorry, 1. is fixed in your commit 923edc1

Note: See TracTickets for help on using tickets.