Opened 12 years ago

Closed 12 years ago

# A better Carmichael lambda function

Reported by: Owned by: wdj mvngu minor sage-4.3.4 cryptography sage-4.3.4.alpha1 Yann Laigle-Chapuy David Joyner, Minh Van Nguyen N/A

### 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 .

based on 4.3.3

### comment:1 Changed 12 years ago by ylchapuy

• 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 12 years ago by wdj

Applies okay to 10.26.2 mac and passes sage -testall.

Okay with me. Minh, what do you think?

### Changed 12 years ago by mvngu

apply on top of previous one

### comment:3 in reply to: ↑ 2 Changed 12 years ago by mvngu

• Authors set to Yann Laigle-Chapuy
• Milestone set to sage-4.3.4
• Reviewers set to David Joyner, Minh Van Nguyen

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 reads
```from sage.rings.integer import Integer
```
This has the effect of importing only what is required, i.e. the class `Integer`, instead of importing the whole module `sage.rings.integer`.
• Some typo fixes.
• Clean up à la PEP8.
• Removing a redundant `lambda` construct by replacing
```lambda x: int(x)
```
with the more compact
```int
```

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 12 years ago by wdj

• 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 12 years ago by mvngu

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 12 years ago by wdj

Done. All tests passed!

### comment:7 Changed 12 years ago by mhansen

• Merged in set to sage-4.3.4.alpha1
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.