Carmichael Function: A Complete Guide — Number theory

Sam.
Sam.
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.

Some numbers & letters!

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 = 8
Carmichael Function of n
Written 𝝀(n)
> Find all coprimes of 8, between 1 and 8
1, 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 = 2
1² % 8 = 1
3² % 8 = 1
5² % 8 = 1
7² % 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 rewritten
xʳ - 1 = mk
> AND
xʳ ≡ 1 (mod n)
> can be rewritten
xʳ - 1 = nk
> where k₁ & k₂ are each a positive integer> so
mk₁ = nk₂ = xʳ - 1
> lcm means lowest common multiple
mk₁ = nk₂ = lcm(m, n)
> therefore
xʳ - 1 = lcm(m, n)
> m & n are coprimes
lcm(m, n) = mn
xʳ - 1 = mn> proving
≡ 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 prime
aᵖ⁻¹ ≡ 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) = 4etc.

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 a
a 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 power
9 = 3²
U = ϕ(9) = 6

(You can learn how we find the value of Euler’s totient function in our article on it, here.)

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 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 . This means we will need to show that (1 + 2h)² ≡ 1 (mod 8).

(1 + 2h)²> Expand
4h² + 4h + 1
> Factorise
1 + 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ᵏ⁻² would give 2⁻¹, 1/2, a fraction rather than an integer. For , 2ᵏ⁻² gives 2⁰, which is 1, a result that can be shown incorrect for its coprime 3. For & , 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 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 (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!

curiositypapers

How the world works. Science, maths & technology applied.

Sam.

Written by

Sam.

Technology & Programming, one breakpoint at a time.

curiositypapers

How the world works. Science, maths & technology applied.

More From Medium

More on Number Theory from curiositypapers

More on Number Theory from curiositypapers

A Complete Explanation of RSA Asymmetric Encryption

Sam.
Feb 15 · 20 min read

More on Encryption from curiositypapers

More on Encryption from curiositypapers

Asymmetric Encryption Part 1: What is that?

Sam.
Feb 15 · 5 min read

More on Mathematics from curiositypapers

More on Mathematics from curiositypapers

Fermat & Euler: 2 Important Theorems — Number Theory

Sam.
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