#8246: Carmichael lambda function for the Blum-Blum-Shub pseudorandom bit
generator
---------------------------------------------------------+------------------
Reporter: mvngu | Owner: mvngu
Type: enhancement | Status:
needs_review
Priority: major | Milestone:
sage-4.3.3
Component: cryptography | Keywords:
Author: Mike Hogan, David Joyner, Minh Van Nguyen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------------------------------------+------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Mike Hogan, David Joyner, Minh Van Nguyen
Comment:
The attachment
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/trac_8246-carmichael.patch
trac_8246-carmichael.patch] provides a non-recursive implementation of the
Carmichael function. This is in contrast to the recursive implementation
as contained in
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/BBScrypto.sage
BBScrypto.sage]. I have provided some timing comparison to justify the
non-recursive implementation. Say
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/BBScrypto.sage
BBScrypto.sage] is at `/home/mvngu/BBScrypto.sage` and
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/trac_8246-carmichael.patch
trac_8246-carmichael.patch] has been applied to Sage 4.3.2. The following
generates some timing statistics for both Hogan & Joyner's implementation,
and the non-recursive implementation. Here are some timing statistics for
the recursive implementation, where the timing results (in microseconds)
are saved to
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/carmichael.old
carmichael.old]:
{{{
sage: load("/home/mvngu/BBScrypto.sage")
sage: T = []
sage: for n in xrange(1, 1001):
....: t = %timeit carmichael(n)
....: T.append(t.stats[3])
....:
sage: f = open("/home/mvngu/carmichael.old", "w")
sage: for t in T:
....: f.write(str(t) + "\n")
....:
sage: f.close()
}}}
The following are some timing statistics for the non-recursive
implementation. Timing results (in microseconds) are saved to
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/carmichael.new
carmichael.new]:
{{{
sage: from sage.crypto.util import carmichael_lambda
sage: T = []
sage: for n in xrange(1, 1001):
....: t = %timeit carmichael_lambda(n)
....: T.append(t.stats[3])
....:
sage: # First 10 elements of T are timings in nanoseconds.
sage: # So convert them to microseconds.
sage: for i in xrange(10):
....: T[i] = T[i] / 1000
....:
sage: f = open("/home/mvngu/carmichael.new", "w")
sage: for t in T:
....: f.write(str(t) + "\n")
....:
sage: f.close()
}}}
Now plot the timing results. The plot in blue is for the recursive
implementation, while the plot in red is for the non-recursive
implementation. The horizontal axis is for integer values of `n` starting
from 1, up to and including 1000. The vertical axis is for the values of
the Carmichael function of `n`. The resulting combined plot is contained
in [http://trac.sagemath.org/sage_trac/attachment/ticket/8246/benchmark-
carmichael.png benchmark-carmichael.png]. Timing statistics were obtained
using the machine `sage.math`.
{{{
sage: X = [1..1000]
sage: Yold = []
sage: f = open("/home/mvngu/carmichael.old", "r")
sage: for t in f:
....: Yold.append(RR(t.strip()))
....:
sage: f.close()
sage: Ynew = []
sage: f = open("/home/mvngu/carmichael.new", "r")
sage: for t in f:
....: Ynew.append(RR(t.strip()))
....:
sage: f.close()
sage: Pold = line2d(zip(X, Yold), color="blue", thickness=1)
sage: Pnew = line2d(zip(X, Ynew), color="red", thickness=1)
sage: Pold + Pnew
}}}
First apply #7746 and then
[http://trac.sagemath.org/sage_trac/attachment/ticket/8246/trac_8246-carmichael.patch
trac_8246-carmichael.patch].
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8246#comment:1>
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.
