Carmichael Function: A Complete Guide — Number theory

Jan 7 · 8 min read

The Carmichael function is an important theory in the field of Cryptography, as it forms the proof the basis for RSA encryption. Here we’ll take a look at what the function is exactly, and then how the function will operate for various inputs.

What is the Carmichael Function?

The Carmichael function takes as input one integer `n` , and returns a value `m` such that every integer coprime to `n` , between 1 & `n` , when raised to the power `m`, `mod n` , gives 1. Too wordy?

`n = 8Carmichael Function of nWritten 𝝀(n)> Find all coprimes of 8, between 1 and 81, 3, 5, 7> What number, as exponent of each of these, mod n, gives 1?> We need to satisfy:1ᵐ ≡ 1 (mod 8)3ᵐ ≡ 1 (mod 8)5ᵐ ≡ 1 (mod 8)7ᵐ ≡ 1 (mod 8)> where "a" is the smallest value which satisfies all statements> for n = 8 the answer -> m = 21² % 8 = 13² % 8 = 15² % 8 = 17² % 8 = 1𝝀(8) = 2`

Hopefully that clears up what the Carmichael Function does. But how does it find `m` ?

How do we know there is a solution?

First let’s tackle the question of how we can be sure there is a solution, `m` , at all. The proof that there is a solution relies on 4 rules of modular arithmetic. These rules were covered in detail and proved in our discussion of them here.

Here we’ll satisfy ourselves by summarising 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)` (the cancellation rule)
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)`

above proves that for any given coprime to `n`, `aᵢ`, there is an exponent of `aᵢ`, `kᵢ`, that satisfies `aᵢᵏⁱ ≡ 1 (mod n)`.

If `n` has `v` coprimes, define `k` , `k = k₁ x k₂ x ... x kᵥ`.

`k` is a consequently a multiple of all `kᵢ`. Therefore, `aᵢᵏ ≡ 1 (mod n)` , as proven by above. `k` is an integer exponent raised to which all coprimes of `n` smaller than `n` are congruent to 1, satisfying Carmichael’s Function. `k` may not be the smallest solution, but it proves that there is always a solution to Carmichael’s Function.

Solving Carmichael’s Function

For non-prime, non-prime power, integers

If `m` & `n` are coprime, then we know the following:

• If `x` is a coprime of `mn`, less than `mn`, then `x % m` is coprime to `m` , and `x % n` is coprime to `n` . This is because if `x` shares no factors with `mn` then it shares no factors with either `m` or `n` .
• If `xʳ ≡ 1 (mod m)` and `xʳ ≡ 1 (mod n)` then `xʳ ≡ 1 (mod mn)` , because:
`xʳ ≡ 1 (mod m)> can be rewrittenxʳ - 1 = mk₁> ANDxʳ ≡ 1 (mod n)> can be rewrittenxʳ - 1 = nk₂> where k₁ & k₂ are each a positive integer> somk₁ = nk₂ = xʳ - 1> lcm means lowest common multiplemk₁ = nk₂ = lcm(m, n)> thereforexʳ - 1 = lcm(m, n)> m & n are coprimeslcm(m, n) = mnxʳ - 1 = mn> provingxʳ ≡ 1 (mod mn)`

Following this second bullet point then, tells us that if `xʳ ≡ 1 (mod mn)` then we know also that, for any multiple of `r,` say `s`, `xˢ ≡ 1 (mod mn)` also. So if `aᶠ ≡ 1 (mod m)` works for all `m's` coprimes, & `aᵍ ≡ 1 (mod n)` for all `n’s` coprimes, then we know that `aᶠᵍ ≡ 1 (mod mn)` will work for all `mn's` coprimes.

So if we can find the solution to Carmichael’s Function for `m` & `n` , `𝝀(m)` & `𝝀(n)`, then we know that a multiple of these results will work for `𝝀(mn)`. Therefore the smallest number that will work for `𝝀(mn)` will be the lowest common multiple of `𝝀(m)` & `𝝀(n)` .

`𝝀(mn) = lcm(𝝀(m), 𝝀(n))`

We now have a formula for finding the Carmichael value for a given number. We factorise the number, and solve for each of those. Unfortunately the formula is recursive: it references itself. We need a base case, a point at which we no longer rely on the outcome of one Carmichael function to resolve another. That base case is prime numbers, because primes do can’t be factorised into this `mn` format. So how do we solve Carmichael’s Function for prime numbers?

For prime numbers

In a previous article we looked in depth at Fermat’s Little Theorem. You should take a look at that post to understand exactly why this works. Fermat’s Little Theorem states:

`> Where "p" is primeaᵖ⁻¹ ≡ 1 (mod p)`

That tells us enough to apply to Carmichael’s function. If we want to know the Carmichael value of any prime, `p`, we know the answer is `p-1` . For example, `𝝀(7) = 6` , `𝝀(5) = 4`etc.

I would encourage you to take a look at our discussion of Fermat’s Little Theorem to understand exactly why this does work.

We’ve covered Carmichael’s function for primes, and for numbers which reduce to their prime factors. We haven’t touched upon numbers which reduce to powers of primes, or powers of primes themselves, and how in their particular cases we would find the Carmichael’s function value.

For Powers of Odd Primes

The unique issue with prime powers is that they are not primes, so we can’t make use of Fermat’s Little Theorem, however they don’t reduce to unique primes either.

In this case we make use of a theory closely related to Fermat’s Little Theorem, called Euler’s Theorem. We covered Euler’s Theorem in the same article as Fermat’s Little Theorem, and you can read about them both here.

Euler’s Theorem states:

`> Where U = ϕ(n), because notation support on medium is weak> And where n is coprime to aaᵁ ≡ 1 (mod n)`

`ϕ(n)` represents Euler’s Totient function. It returns the number of coprimes to `n`, less than `n`. You can learn more about exactly how Euler’s Totient Function works in our recent post about it.

We can apply Euler’s Theorem to solve Carmichael’s function for prime powers. Importantly, Euler’s theorem doesn’t require `n` to be prime. The theorem tells us that for:

`> For 𝝀(9), a prime power9 = 3²U = ϕ(9) = 6`

So for prime powers, Carmichael’s function is the same as Euler’s totient function. In fact, this is true for many numbers. However there are a variety of cases where Euler’s totient differs from Carmichael’s function, where the totient is a “workable” solution, but not the smallest workable solution to Carmichael’s function.

For powers of 2

One example of where the Euler totient & Euler theorem method doesn’t provide the correct result is for powers of 2. For example `ɸ(8)= 4` . For all coprimes to 8, `a⁴ ≡ 1 (mod 8)`, so it does “work”, but 4 is not the lowest value which “works”, & remember that Carmichael’s Function returns the lowest such value. Indeed, `𝞴(8) = 2` .

2 is a prime number, so its powers suffer the same difficulty we face for odd powers, in that we cannot apply the lowest common multiple method, nor can we apply the method reserved for prime numbers. We need another method then, a fourth way of solving Carmichael’s function, for powers of 2.

Firstly, we can observe that where `p = 2`, the formula we used for odd primes, `pᵏ — pᵏ⁻¹` simplifies `pᵏ⁻¹`, because `pᵏ⁻¹` is always going to be half of `pᵏ`. Literally, `pᵏ⁻¹ x 2 = pᵏ` . For `k = 3` , `pᵏ — pᵏ⁻¹ = 8 — 4 = 4`. 4 is still a power of 2.

Unlike powers of odd primes, the result of `pᵏ — pᵏ⁻¹` does not satisfy the form `pʰ` for any integer `h` . Where `p = 3` & `k = 3`, `pᵏ — pᵏ⁻¹ = 27 — 9 = 18`. 18 is not a power of 3. We’ve introduced other factors. This is a hint at the difference between odd prime powers and powers of 2, with respect to Carmichael’s function.

All odd numbers are coprimes to powers of 2. All even numbers share the factor `2`, so are not coprime. We can represent all odd numbers, that is all coprimes to powers of 2 as: `a = 1 + 2h` where `h` is any integer ≥ 0.

To find the solution for any power of 2, `𝞴(2ᵏ)`, we need to satisfy `(1 + 2h)ˣ ≡ 1 (mod 8)` where `x` is the result of Carmichael’s function. We can show that, for powers of 2 greater than 2, Carmichael’s Function gives `2ᵏ⁻²`.

For `k = 2`, `𝞴(8) = 𝞴(2³)`, we assert that the result, `k — 2`, will be `2¹`. This means we will need to show that `(1 + 2h)² ≡ 1 (mod 8)`.

`(1 + 2h)²> Expand4h² + 4h + 1> Factorise1 + 4h(h + 1)`

To prove that `1 + 4h(h + 1) ≡ 1 (mod 8)` we need to show that `4h(h + 1) ≡ 0 (mod 8)`. We can clearly see that it divides by 4, giving `h(h + 1)`. We can prove that `h(h + 1)` divides by 2.

• 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)` divides by 8, proving `1 + 4h(h + 1) ≡ 1 (mod 8)`. We’ve shown that `𝞴(8) = 𝞴(2³) = 2¹`, and by induction that `𝞴(2ᵏ) = 2ᵏ⁻²` .

However, for a fairly evident reason, this is only true for powers of 2 greater than 2. For `2¹` `2ᵏ⁻²` would give `2⁻¹`, `1/2`, a fraction rather than an integer. For `2²` , `2ᵏ⁻²` gives `2⁰`, which is 1, a result that can be shown incorrect for its coprime 3. For `2¹` & `2²` , we use `pᵏ⁻¹`.

Solving Carmichael’s Function: An Example

We now have everything we need to solve Carmichael’s Function for a given number. So let’s try it out.

`𝞴(135) ?> factorise 135135 = 27 * 5𝞴(135) = lcm(𝞴(27), 𝞴(5))> 5 is a prime𝞴(5) = 4 (5-1)> 27 is a prime power27 = 3³> So we apply the totient function𝞴(27) = ϕ(27)> Coprimes of 271, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26> I count 18 (there is an easier way than counting -> here)𝞴(27) = ϕ(27) = 18> Work backwards𝞴(135) = lcm(𝞴(27), 𝞴(5))lcm(𝞴(27), 𝞴(5)) = lcm(18, 4)lcm(18, 4) = 36𝞴(135) = 36`

And that’s all

I think that should cover just about every case. We now have the means to solve Carmichael’s function for any and all numbers!

Written by

More From Medium

A Complete Explanation of RSA Asymmetric Encryption

Feb 15 · 20 min read

Asymmetric Encryption Part 1: What is that?

Feb 15 · 5 min read

Fermat & Euler: 2 Important Theorems — Number Theory

Jan 7 · 4 min read
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade