#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):
Sorry to comment that late, but there are a few things in this patch I
dislike:
* Why hard code the first ten values?
* `carmichael_lambda(16)` is of type `sage.rings.rational.Rational`
* why use generic_power to compute the power of an integer?
here's my 2-cents implementation:
{{{
def carmichael_lambda(n):
n = Integer(n)
if n < 1:
raise ValueError("Input n must be a positive integer.")
F = n.factor()
L = []
# first get rid of the even part
if n & 1 == 0:
e = F[0][1]
F = F[1:]
if e < 3:
e = e-1
else:
e = e-2
L.append(1<<e)
# then other prime factors
L += [ p**(k-1)*(p-1) for p,k in F]
# finish the job
return lcm(L)
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8246#comment:4>
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.
