#5098: [with patch, needs review] Pollard rho algorithm for generic discrete
logarithm
-------------------------+--------------------------------------------------
Reporter: ylchapuy | Owner: tbd
Type: enhancement | Status: new
Priority: minor | Milestone: sage-3.3
Component: algebra | Resolution:
Keywords: |
-------------------------+--------------------------------------------------
Changes (by ylchapuy):
* summary: [with patch, with review, needs work] Pollard rho algorithm
for generic discrete logarithm => [with patch,
needs review] Pollard rho algorithm for generic
discrete logarithm
Comment:
a patch is on the way. I also removed to debug printings I forgot and
added my authorship.
Concerning comparison, the benefit of Pollard rho algorithm comes only
with quite big examples and I don't think it's a good idea for doctests.
Here's one example.
{{{
----------------------------------------------------------------------
| Sage Version 3.2.3, Release Date: 2009-01-05 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: yann
sage: get_memory_usage()
113.9765625
sage: F.<a>=GF(2^118)
sage: g=F.multiplicative_generator()
sage: u=g^15726718062461913153073925660344578
sage: time discrete_log(u,g,algorithm="rho")
CPU times: user 56.06 s, sys: 0.20 s, total: 56.26 s
Wall time: 56.39 s
15726718062461913153073925660344578
sage: get_memory_usage()
116.03515625
sage: time discrete_log(u,g,algorithm="bsgs")
CPU times: user 46.74 s, sys: 0.54 s, total: 47.29 s
Wall time: 47.47 s
15726718062461913153073925660344578
sage: get_memory_usage()
392.89453125
}}}
actually, Pollard rho is not so slow :)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5098#comment:6>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
