Proper Carmichael Function

Question

I'm creating all the necessary functions for RSA algorithm. Unfortunately i can't seem to a make proper Carmichael function.

These are the functions that i've written:

def gcd(a, b):  # Greatest Common Divisor Generator (Euclidean Algorithm)
    while b != 0:  # While remainder exists
        t = b  # Initially r[k-1]
        b = a % t  # Initially r[k] = r[k-2] mod r[k-1] (where r[k-2] is a)
        a = t  # Predecessor of remainder (b)
    return a

def phi(n):  # Leonard Euler's Totient Function
    y = 0
    for k in range(1, n + 1):  # Phi(+n) is the number of integers k in the range (1 <= k >= n)...
        if gcd(n, k) == 1:  # for which gcd(n, k) = 1
            y += 1
    return y

def carmichael(n):  # Robert Daniel Carmichael's Function
    y = (phi(n) * 1/2) if (n > 4 and ((n & (n - 1)) == 0)) else phi(n)  # phi(n) * 1/2 if 2^x = n, else phi(n) * 1
    return y

I'm using totient function for number generation. From my knowledge there is a simple rule, If number is power of 2 and it's greater than 4, Amount of it's prime numbers shall be halved, otherwise it's equal to phi(n).

The rule above is perfectly working in my code, For example, if the input value is 8, these are the results:

phi(8) = 4
carmichael(8) = 2

But the problem is, Carmichael function is also halving other numbers for some reason, for example if input is 12, this is what my functions return:

phi(12) = 4
carmichael(12) = 4

But this is how it should look like:

phi(12) = 4
carmichael(12) = 2

Why is this happening? Perhaps non-prime odd numbers should be treated differently? Is there something that i need to add to my function?

Thank you!

Answer 1

First we create the gcd function to calculate greatest common divisor of 2 numbers, we will need it later in lambda function.

 def gcd(a,b):
        while (a>0):
            b=b%a
            (a,b)=(b,a)
        return b    

---

Then we look at how carmichael function works.

Let n be a positive integer. Then λ(n) is defined to be the smallest positive integer k such that
a^k≡1(mod n)
for all a such that gcd(a,n)=1.

Note that we are looking for k, the values of a is determined once we have n.

---

Now we initialize the function with default condition

n=int(n)
k=2
a=1
alist=[]

---

To find all a values we use gcd(a,n)=1 to test whether a and n have the greatest common divisor as 1, which means they are coprime.
If not, a++
if gcd(a,n)==1, we store this value to the list of a and test next a until we test all a<=n

        while not ((gcd(a,n))==1):
            a=a+1

        while ((gcd(a,n))==1) & (a<=n) :
            alist.append(a)
            a=a+1
            while not ((gcd(a,n))==1):
                a=a+1

---

Ok now we have all a in the list alist, look back at definition

the smallest positive integer k such that
a^k≡1(mod n)

First we count the number of a, which is the length of alist
timer=len(alist)
Then we use
if (a**k)%n==1:
to test whether this k makes a^k≡1(mod n) for all a value in alist. We construct a loop

for a in alist:
      if (a**k)%n==1:
           timer=timer-1
              if timer <0:
                  break
              pass
      else:
           timer=len(alist)
           k=k+1 

to test all k number from 2, if it doesnot meet requirement, we do k=k+1

---

Now we have the whole function as following

    def carmichael(n):
        n=int(n)
        k=2
        a=1
        alist=[]

        while not ((gcd(a,n))==1):
            a=a+1

        while ((gcd(a,n))==1) & (a<=n) :
            alist.append(a)
            a=a+1
            while not ((gcd(a,n))==1):
                a=a+1

        timer=len(alist)
        while timer>=0:
            for a in alist:
                if (a**k)%n==1:
                    timer=timer-1
                    if timer <0:
                        break
                    pass
                else:
                    timer=len(alist)
                    k=k+1
        return k