Opened 8 years ago
Closed 8 years ago
#8283 closed defect (fixed)
A better Carmichael lambda function
Reported by: | wdj | Owned by: | mvngu |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.3.4 |
Component: | cryptography | Keywords: | |
Cc: | Merged in: | sage-4.3.4.alpha1 | |
Authors: | Yann Laigle-Chapuy | Reviewers: | David Joyner, Minh Van Nguyen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Reported by ylchapuy:
Here is another 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)
This is a bit faster than the current implementation and, if you replace lcm with sage.rings.integer.LCM_list, it is even faster.
A bug with the current function is that the output is not always an integer: e.g., carmichael_lambda(16) is of type sage.rings.rational.Rational .
Attachments (2)
Change History (9)
Changed 8 years ago by
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
I don't use sage.rings.integer.LCM_list
because I think it's less readable.
comment:2 follow-up: ↓ 3 Changed 8 years ago by
Applies okay to 10.26.2 mac and passes sage -testall.
Okay with me. Minh, what do you think?
comment:3 in reply to: ↑ 2 Changed 8 years ago by
- Milestone set to sage-4.3.4
- Reviewers set to David Joyner, Minh Van Nguyen
Replying to wdj:
Okay with me. Minh, what do you think?
I agree with Yann's rewrite. It's much more compact than the previous version. However, I have attached the reviewer patch trac_8283-reviewer.patch, whose changes include:
- Remove the import statements
from sage.rings.arith import factor from sage.structure.element import generic_power
These import statements are no longer required due to Yann's rewrite of the Carmichael lambda function. - Move the import statement
import sage.rings.integer
to the module preamble, so that it now readsfrom sage.rings.integer import Integer
This has the effect of importing only what is required, i.e. the classInteger
, instead of importing the whole modulesage.rings.integer
. - Some typo fixes.
- Clean up à la PEP8.
- Removing a redundant
lambda
construct by replacinglambda x: int(x)
with the more compactint
Only my patch needs review by anyone but me. If it's OK, then the whole ticket gets a positive review.
comment:4 follow-up: ↓ 5 Changed 8 years ago by
- Status changed from needs_review to positive_review
I read this over - looks good. I also installed it on top of the previous patch - passed sage -t devel/sage/sage/crypto/util.py. Is that enough, or it sage -testall necessary? If that is okay, positive review from me.
comment:5 in reply to: ↑ 4 Changed 8 years ago by
Replying to wdj:
I read this over - looks good. I also installed it on top of the previous patch - passed sage -t devel/sage/sage/crypto/util.py. Is that enough, or it sage -testall necessary?
Running all doctests in the cryptography module subdirectory would be nice. Something like:
./sage -t -long devel/sage-main/sage/crypto/
The module sage/crypto/util.py
is at least used by the Blum-Goldwasser class under sage/crypto/public_key/
. So naturally one would like to know how the above two patches would affect any other modules under the cryptography subdirectory.
comment:6 Changed 8 years ago by
Done. All tests passed!
comment:7 Changed 8 years ago by
- Merged in set to sage-4.3.4.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
based on 4.3.3