#8246: Carmichael lambda function for the Blum-Blum-Shub pseudorandom bit
generator
-------------------------------+--------------------------------------------
Reporter: mvngu | Owner: mvngu
Type: enhancement | Status: closed
Priority: major | Milestone: sage-4.3.3
Component: cryptography | Resolution: fixed
Keywords: | Author: Mike Hogan, David Joyner, Minh
Van Nguyen
Upstream: N/A | Reviewer: David Joyner
Merged: sage-4.3.3.alpha1 | Work_issues:
-------------------------------+--------------------------------------------
Comment(by ylchapuy):
Replying to [comment:5 wdj]:
> Replying to [comment:4 ylchapuy]:
> > Sorry to comment that late, but there are a few things in this patch I
dislike:
> > ...
>
> Did you test to see if your implementation was faster than the current
one. If so, what were the results?
Except if n<=10, timings are very similar, mine being slightly faster.
To obtain an even faster version one can replace the final lcm with
`sage.rings.integer.LCM_list(L)`.
e.g.
{{{
sage: %timeit carmichael_lambda(1000) # Minh's version
625 loops, best of 3: 270 µs per loop
sage: %timeit my_carmichael_lambda(1000) # mine with lcm
625 loops, best of 3: 244 µs per loop
sage: %timeit my_carmichael_lambda2(1000) # mine with
sage.rings.integer.LCM_list
625 loops, best of 3: 214 µs per loop
sage: %timeit factor(1000) # just to compare
625 loops, best of 3: 177 µs per loop
}}}
we can see that most of the time is spent factoring.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8246#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
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.
