#5112 closed enhancement (fixed)
generic Pollard lambda algorithm
Reported by: | ylchapuy | Owned by: | tbd |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.3 |
Component: | algebra | Keywords: | |
Cc: | mraum | Merged in: | sage-4.3.rc1 |
Authors: | Yann Laigle-Chapuy | Reviewers: | Martin Raum |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Following #5098, here is a generic implementation of Pollard lambda algorithm. There is probably still lots of room for optimization, but it works.
Attachments (3)
Change History (18)
comment:1 Changed 13 years ago by
- Summary changed from generic Pollard lambda algorithm to [with patch, needs review] generic Pollard lambda algorithm
comment:2 Changed 13 years ago by
patch updated. should be applied after #5098 trac-5098-alpha2based.patch
comment:3 Changed 13 years ago by
- Summary changed from [with patch, needs review] generic Pollard lambda algorithm to [with patch, with positive review] generic Pollard lambda algorithm
Patch applies fine to 3.3.alpha2 + (from #5098) trac-5098-alpha2based.patch and tests pass. Code looks good and docstring & doctests are fine.
I think it is excellent to have more of these generic algorithms available. Pass!
comment:4 Changed 13 years ago by
- Summary changed from [with patch, with positive review] generic Pollard lambda algorithm to [with patch, with positive review] generic Pollard lambda algorithm
John,
please make sure not to sneak extra spaces in between positive and review since the reports do not pick up such tickets. The reports should be fixed to ignore extra white space, but until then ....
Cheers,
Michael
Changed 13 years ago by
comment:5 Changed 13 years ago by
- Summary changed from [with patch, with positive review] generic Pollard lambda algorithm to [with patch, needs review] generic Pollard lambda algorithm
patch updated after trac-5098-doctest.patch
comment:6 follow-up: ↓ 7 Changed 13 years ago by
Hi Yann,
how large are the changes? If it is "just" a rebase with no or minimal functional changes (i.e. some exception changed) the positive review can stand.
Cheers,
Michael
comment:7 in reply to: ↑ 6 Changed 13 years ago by
- Summary changed from [with patch, needs review] generic Pollard lambda algorithm to [with patch, with positive review] generic Pollard lambda algorithm
yes, it's indeed strictly a rebase. I just wanted to be sure the patch applies cleanly.
comment:8 Changed 13 years ago by
- Milestone changed from sage-3.4.1 to sage-3.3
This is 3.3 material.
Cheers,
Michael
comment:9 Changed 13 years ago by
- Summary changed from [with patch, with positive review] generic Pollard lambda algorithm to [with patch, needs work] generic Pollard lambda algorithm
SECOND REVIEW:
- Line 1 of docstring: "Pollard Lambda algorithm for computing discrete logarithm."
It should be "Pollard Lambda algorithm for computing discrete logarithms." or "Pollard Lambda algorithm for computing the discrete logarithm."
- The docstring has a typo in line 2: "usefull"
- The sections in the docstring should have space between them (e.g., a blank line before EXAMPLES:). This can be ignored because of the ReST/Sphinx transition, which will probably change that.
- I noticed this line
N = width.isqrt()+1
If width is a Python int then that will fail. This is easy to trigger and will accidentally happen in library code easily:
sage: F.<a> = GF(2^63) sage: g = F.gen() sage: pollard_lambda(g, g^1234567, (1200000,1250000)) 1234567 sage: pollard_lambda(g, g^1234567, (int(1200000), int(1250000))) --------------------------------------------------------------------------- AttributeError Traceback (most recent call last) /space/wstein/sage-3.3.rc0/<ipython console> in <module>() /space/wstein/sage-3.3.rc0/local/lib/python2.5/site-packages/sage/groups/generic.pyc in pollard_lambda(base, a, bounds, ord, operation, hash_function, memory) 649 650 width = ub-lb --> 651 N = width.isqrt()+1 652 653 M = dict() AttributeError: 'int' object has no attribute 'isqrt'
- the doctests are insufficient. The function signature is
def pollard_lambda(base, a, bounds, ord=None, operation='*', hash_function=hash, memory=None):
At a bare minimum, there must be doctests that test use of all the inputs to the function.
comment:10 Changed 13 years ago by
- Milestone changed from sage-3.3 to sage-3.4.1
I am cleaning up the 3.3 milestone. If a patch with positive review is put up to this ticket on time it might make it into 3.3.
Cheers,
Michael
comment:11 Changed 12 years ago by
- Cc mraum added
- Report Upstream set to N/A
- Status changed from needs_work to needs_review
It should be quite similar to #5098.
comment:12 Changed 12 years ago by
- Summary changed from [with patch, needs work] generic Pollard lambda algorithm to generic Pollard lambda algorithm
comment:13 Changed 12 years ago by
- Status changed from needs_review to positive_review
Good point, it is similar.
According to Micheal's comment, I added one doctest, testing the hash_function, too. Now, I think it's good.
Changed 12 years ago by
comment:14 Changed 12 years ago by
- Merged in set to sage-4.3.rc1
- Resolution set to fixed
- Reviewers set to Martin Raum
- Status changed from positive_review to closed
comment:15 Changed 12 years ago by
- Milestone changed from sage-4.3.1 to sage-4.3
patch needs #5098 to be applied first.