Part of my series explaining the RSA Algorithm

The Carmichael function is an important part of number theory. It forms the basis of RSA encryption. We’ll take a look at what the function is exactly, and how we can solve it for various categories of input.

Note

• LCM() is the lowest common multiple of the provided integers.

What is the Carmichael Function?

It takes as input an integer, n. The function is written as a Lambda: 𝝀(n).

It’s output, m, is the lowest value such that every integer coprime to n, between 1 & n, when raised to the power m, and mod n, gives 1. For example:

n = 8
𝝀(8) = ?

> Find all coprimes of n, between 1 & n
1, 3, 5, 7

> We need to find the smallest value of 'm' which satisfies...
1ᵐ ≡ 1 (mod 8)
3ᵐ ≡ 1 (mod 8)
5ᵐ ≡ 1 (mod 8)
7ᵐ ≡ 1 (mod 8)

> for n = 8, m = 2
1² % 8 = 1
3² % 8 = 1
5² % 8 = 1
7² % 8 = 1

𝝀(8) = 2

Note that the value 4 would also work. However the Carmichael Function returns the lowest working value.

We know what the Carmichael Function does. But how do we find m?

How do we know that there is a solution?

To prove that there is a solution, we’ll be applying the rules we looked at in ‘Modular Arithmetic: 4 Important Truths’. If you haven’t covered those, go and read that first. It’s short and will give you everything you need to continue with this.

If you’ve forgotten them already, we can summarise them:

1. If a & b are coprime, AND a|bc, THEN a|c

2. If a & b are coprime, AND ax ≡ ay (mod n), THEN x ≡ y (mod n)

3. If a & b are coprime, THEN there is a positive integer, k such that aᵏ≡ 1 (mod n)

4. If aᵏ ≡ 1 (mod n) AND r is a multiple of k THEN aʳ≡ 1 (mod n)

Rule #3 proves that for any two coprimes, a & n, there is a power k such that aᵏ % n = 1.

If n has v coprimes between 1 & n, then each coprime, aᵢ, must have some power, kᵢ, so that aᵢᵏⁱ ≡ 1 (mod n).

Let k be the product of all kᵢ values: k = k₁ x k₂ x … x kᵥ. k is consequently the product of each kᵢ value.

> We know that
aᵢᵏⁱ ≡ 1 (mod n)

> Rule #4 proves this is true for any multiple of `kᵢ`
> We know `k` is a multiple of `kᵢ`
aᵢᵏ ≡ 1 (mod n)

So for all coprimes of n, we know there will be some value, k that satisfies Carmichael’s Function.

Solving Carmichael’s Function

Solving for non-prime, non-prime power, integers

Let x be a coprime to the product of m & n, mn. x < mn.

We know that x % n is also coprime to n, and that x % m is coprime to m. x shares no factors with mn, so we know it shares no factors with m or n individually.

Let r be an integer which satisfies the following expressions:

xʳ ≡ 1 (mod m)
xʳ ≡ 1 (mod n)

Given this, we can prove also that xʳ ≡ 1 (mod mn).

xʳ ≡ 1 (mod m)
xʳ ≡ 1 (mod n)

> where k₁ & k₂ are positive integers
> rearrange
xʳ - 1 = mk₁
xʳ - 1 = nk₂

> therefore
mk₁ = nk₂ = xʳ - 1

> we've found a common multiple
mk₁ = nk₂ = LCM(m, n)
xʳ - 1 = LCM(m, n)

> because m & n are coprimes
LCM(m, n) = mn
xʳ - 1 = mn

> proving
xʳ ≡ 1 (mod mn)

Now, you may remember that Rule #4 we mentioned above tells us that if xʳ ≡ 1 (mod mn), then the same is true for any multiple of r. For example, picking any integer s, we know xʳˢ ≡ 1 (mod mn).

We can use this to combine solutions to Carmichael’s Function. If aᶠ ≡ 1 (mod m) and aᵍ ≡ 1 (mod n) for all of their respective coprimes, then we know that aᶠᵍ ≡ 1 (mod mn) is true for all coprimes of mn. So if 𝝀(m) = f & 𝝀(n) = g then 𝝀(mn) = LCM(𝝀(m), 𝝀(n)). We use lowest common multiple because we are looking for the lowest working value.

This gives us a recursive formula for finding the Carmichael value. To find the value for a number, first find the value of any two coprime factors, then take the lowest common multiple of those values. As with all recursive functions we need a base case. In this instance, our base is prime numbers, which have no factors besides themselves and 1.

Solving for prime numbers

Fermat’s Little Theorem states:

> Where `p` is prime
aᵖ⁻¹ ≡ 1 (mod p)

If you want to know why this is the case, you can take a deeper look at Fermat’s Little Theorem in this post.

The theorem tells us that if we want to satisfy the Carmichael function for any prime p, the correct value is p - 1. That simple.

This means we can solve the function for primes and for integers which reduce to their prime factors. There are two special cases we still need to look at though.

I would strongly encourage you to take a look at the discussion we had on Fermat’s Little Theorem before you accept the outcome we’ve found reached here. Understanding is a battle to convince yourself of some claim. You cannot understand the Carmichael Function without being sure of the claim that Fermat’s Theorem makes.

Solving for powers of odd primes

Powers of odd primes fall into a special category. This means we cannot use either method we’ve seen so far for solving Carmichael’s function. They are not themselves primes, yet they do not have coprime pairs of factors either. This prevents us from using the 𝝀(mn) = LCM(𝝀(m), 𝝀(n)) trick.

For example 3² = 9. 9 has only 2 factor pairs. We cannot use the pair 9 x 1 because it includes 9 itself, creating an infinite loop: 𝝀(9) = LCM(𝝀(9), 𝝀(1)). The other pair, 3 x 3, are evidently not coprime. The formula 𝝀(mn) = LCM(𝝀(m), 𝝀(n)) requires m & n to be coprime, as shown in the proof.

To solve the function in this case, we need to use Euler’s Theorem. Euler’s Theorem is closely related to Fermat’s Little Theorem, and we’ve got a post on both. We’ll also be using Euler’s Totient Function. If you aren’t familiar with Euler’s Totient Function, we covered that in a separate post too. As I said earlier, I encourage you to learn & understand those theorems in order to get a full appreciation of this one.

Phi (𝛗(n)) is used to represent Euler’s Totient function. It returns the number of n’s coprimes less than n. Euler’s Theorem says:

> When 'n' & 'a' are coprime
aᵠ⁽ⁿ⁾ ≡ 1 (mod n)

We can use Euler’s Theorem to solve Carmichael’s function for prime powers.

> For 9, a prime power
𝛗(9) = 6

> coprimes of 9
2, 4, 5, 7, 8

2⁶ % 9 = 1
4⁶ % 9 = 1
5⁶ % 9 = 1
7⁶ % 9 = 1
8⁶ % 9 = 1

𝝀(9) = 𝛗(9) = 6

So for prime powers, Carmichael’s Function is the same as Euler’s Totient Function. In fact this is true for many other types of number too. However, in many cases Euler’s Totient Function offers a workable, but not smallest, solution. For prime powers though, it can be relied upon to solve Carmichael’s Function.

Solving for powers of 2

Powers of 2 represent the final class of number for which we need to solve Carmichael’s function. None of the methods seen so far will suit. Powers of 2 have no coprime factor pairs, they are not themselves prime, and Euler’s Totient does not apply. Powers of odd primes use Euler’s Totient to find the value for Carmichael’s Function. The totient 8, 𝛗(8) = 4. This is a workable, but not smallest, solution to Carmichael’s Function. In fact, 𝞴(8) = 2.

All odd numbers are coprime to 2 & its powers. All odd numbers fit the formula a = 1 + 2h, where the variable h can be any integer. The Carmichael Function we need to solve for any power of 2 would be: (1 + 2h)ᵐ ≡ 1 (mod 2ᵏ). m is the number we’re looking to find. k can be any power of 2.

It can be proven that for any power of 2, 2ᵏ, the Carmichael Function solution is 2ᵏ⁻² Let’s take the example of k = 3.

k = 3
2ᵏ = 2³ = 8
k - 2 = 1
m = 2ᵏ⁻² = 2¹ = 2

> Using (1 + 2h)ᵐ ≡ 1 (mod 2ᵏ)
(1 + 2h)² ≡ 1 (mod 8)
4h² + 4h + 1 ≡ 1 (mod 8)

> factorise and rearrange
1 + 4h(h + 1) ≡ 1 (mod 8)

We know that 4h(h + 1) will divide by 4.

We also know that h(h + 1) will divide by 2, because:

• If h is odd, h + 1 = even, and odd x even = even.

• If h is even, h + 1 = odd, and even x odd = even .

Therefore we know 4h(h + 1) will divide by 8.

So we know that 1 + 4h(h + 1) % 8 = 1.

This demonstrates that 𝞴(8) = 𝞴(2³) = 2¹ and by induction that 𝞴(2ᵏ) = 2ᵏ⁻².

BUT only where k > 2. 2¹ = 2, 2ᵏ⁻² = 2⁻¹ = 1/2, not an integer. For 2² = 4, 2ᵏ⁻² = 2⁰ = 1 it doesn’t work either. For example, 3¹ % 4 != 1. Where k < 3, the smallest solution to Carmichael’s Function is 2ᵏ⁻¹ for powers of 2.

Solving Carmichael’s Function: An Example

We’ve seen how to solve Carmichael’s for all classes of numbers. Now let’s have a go at an example problem:

𝞴(135) ?

> factorise 135
135 = 27 * 5
𝞴(135) = lcm(𝞴(27), 𝞴(5))

> 5 is a prime
𝞴(5) = 4 (5-1)

> 27 is a prime power
27 = 3³

> So we apply the totient function
𝞴(27) = 𝛗(27)

> Coprimes of 27
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26

> I count 18

You don’t need to count these manually. You can learn an easier method for finding total coprimes here.

𝞴(27) = 𝛗(27) = 18
𝞴(5) = 4

> Now working back up
𝞴(135) = lcm(𝞴(27), 𝞴(5))

lcm(𝞴(27), 𝞴(5)) = lcm(18, 4)
lcm(18, 4) = 36

𝞴(135) = 36

That’s Everything

That should just about cover the Carmichael Function. We’ve seen how to solve it in any scenario. The Carmichael Function is used often in cryptography, and pulls together a number of other ideas in Number Theory. You’ll see us put it to work soon when we take a deep dive into RSA encryption.