A better Carmichael lambda function

[wdjoyner]

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 .

Component: cryptography

Author: Yann Laigle-Chapuy

Reviewer: David Joyner, Minh Van Nguyen

Merged: sage-4.3.4.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/8283

[sagetrac-ylchapuy]

based on 4.3.3

[sagetrac-ylchapuy]

comment:1

Attachment: trac_8283-improve_carmichael_lambda.patch.gz

I don't use sage.rings.integer.LCM_list because I think it's less readable.

[wdjoyner]

comment:2

Applies okay to 10.26.2 mac and passes sage -testall.

Okay with me. Minh, what do you think?

[sagetrac-mvngu]

apply on top of previous one

[sagetrac-mvngu]

comment:3

Attachment: trac_8283-reviewer.patch.gz

Replying to @wdjoyner:

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.

[sagetrac-mvngu]

Author: Yann Laigle-Chapuy

[sagetrac-mvngu]

Reviewer: David Joyner, Minh Van Nguyen

[wdjoyner]

comment:4

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.

[sagetrac-mvngu]

comment:5

Replying to @wdjoyner:

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.

[wdjoyner]

comment:6

Done. All tests passed!

[mwhansen]

Merged: sage-4.3.4.alpha1