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)

trac_8283-improve_carmichael_lambda.patch (2.8 KB) - added by ylchapuy 8 years ago.
based on 4.3.3
trac_8283-reviewer.patch (2.8 KB) - added by mvngu 8 years ago.
apply on top of previous one

Download all attachments as: .zip

Change History (9)

Changed 8 years ago by ylchapuy

based on 4.3.3

comment:1 Changed 8 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: Changed 8 years ago by wdj

Applies okay to 10.26.2 mac and passes sage -testall.

Okay with me. Minh, what do you think?

Changed 8 years ago by mvngu

apply on top of previous one

comment:3 in reply to: ↑ 2 Changed 8 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

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 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: Changed 8 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 8 years ago by mvngu

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 wdj

Done. All tests passed!

comment:7 Changed 8 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.