Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#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:

Status badges

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)

trac-5112.patch (3.3 KB) - added by ylchapuy 13 years ago.
trac-5112-rebased.patch (3.4 KB) - added by ylchapuy 13 years ago.
based on 4.3.alpha1 + #5098
trac-5112-pollard_review.patch (3.3 KB) - added by mraum 13 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 13 years ago by ylchapuy

  • Summary changed from generic Pollard lambda algorithm to [with patch, needs review] generic Pollard lambda algorithm

patch needs #5098 to be applied first.

comment:2 Changed 13 years ago by ylchapuy

patch updated. should be applied after #5098 trac-5098-alpha2based.patch

comment:3 Changed 13 years ago by cremona

  • 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 mabshoff

  • 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 ylchapuy

comment:5 Changed 13 years ago by ylchapuy

  • 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: Changed 13 years ago by mabshoff

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 ylchapuy

  • 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 mabshoff

  • 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 was

  • 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 mabshoff

  • 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 13 years ago by ylchapuy

  • Authors set to Yann Laigle-Chapuy
  • 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 13 years ago by ylchapuy

  • Summary changed from [with patch, needs work] generic Pollard lambda algorithm to generic Pollard lambda algorithm

Changed 13 years ago by ylchapuy

based on 4.3.alpha1 + #5098

comment:13 Changed 13 years ago by mraum

  • 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 13 years ago by mraum

comment:14 Changed 13 years ago by mhansen

  • 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 13 years ago by mhansen

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.